Extendí mi ejercicio de A* para que además busque la solución utilizando Avara y las compare gráficamente.
Avara es otro algoritmo de búsqueda, pero a diferencia de A* no es ni óptimo ni completo. Ambos utilizan una heurística para estimar el costo de un estado n al estado objetivo y por esto se dice que son métodos informados.
La diferencia radica en cómo seleccionan nodos para su expansión: mientras que A* siempre elije el nodo que minimice la función camino recorrido + estimación al objetivo, Avara simplemente elije el nodo con menor estimación al objetivo (no tiene en cuenta el camino previo).
Hay escenarios en los que ambas estrategias encontrarán el mismo camino:
Pero hay otros en los que no:
Instalación y uso
Similar al ejemplo anterior. Teniendo Python y PyGame instalados, obtener el código fuente:
svn co http://svn.juanjoconti.com.ar/astar/tags/astar-vs-avara/ astar-vs-avara
y dentro de la carpeta astar-vs-avara ejecutar gui.py:
cd astar-vs-avara
python gui.py
