Lección
La teoría — Visualizador de algoritmos de búsqueda de caminos
Tres de los cuatro algoritmos del menú desplegable son el mismo algoritmo. Todos ellos clasifican las celdas a la espera de ser exploradas con una misma expresión, f(n) = g(n) + h(n) —el coste hasta ahora más el coste estimado restante— y solo se diferencian en cuál de los dos términos conservan. Elimina h y obtendrás Dijkstra. Ignora g y obtendrás Greedy Best-First. El cuarto, la búsqueda en anchura, es en lo que se convierte Dijkstra cuando cada paso cuesta lo mismo.
Qué significa cada símbolo
g(n)- el coste de la ruta más barata encontrada hasta ahora desde el inicio hasta la celda n. Un paso lateral o vertical cuesta
1; uno diagonal cuesta√2, porque el paso se mide como una longitud en lugar de contarse como un solo movimiento. h(n)- la estimación del coste que aún queda por recorrer. Para Dijkstra y la búsqueda en anchura no es que simplemente no se use: es cero, y eso es precisamente lo que los convierte en la misma expresión a la que le falta un término.
f(n)- la clave de clasificación: la celda con el
fmás pequeño es la siguiente en explorarse. Se muestra encima de la cuadrícula sustituyendo los propios números de la celda actual, de modo que la elección que acaba de hacer el algoritmo es visible en lugar de presunta. frontier- las celdas ámbar: descubiertas, pero aún no exploradas. Nodos expandidos cuenta lo que ha salido de este conjunto, lo que lo convierte en una medida del trabajo realizado, no de la calidad de la respuesta.
De dónde viene la fórmula
- Fija qué significa "más corto" antes de elegir un algoritmo. El coste de un camino es la suma de las longitudes de sus pasos:
1para un movimiento lateral o vertical,√2para uno diagonal. No se cuentan las celdas; se suman las distancias. - Ahora el bucle, que es idéntico para los cuatro: saca una celda de la frontera, márcala como explorada y ofrece cada vecina transitable a la frontera con un
gactualizado. Fíjate en lo que este bucle nunca menciona: una heurística, la dirección hacia la meta o qué algoritmo has elegido. - Así que la única decisión que queda es cuál celda sacar, y se reduce a una sola expresión. Clasifica por
g + hy tendrás A*. Estableceh = 0y la clasificación se basa solo en el coste acumulado; ese es Dijkstra, expandiéndose hacia afuera en anillos porque no tiene idea de dónde está la meta. Ignoragen su lugar y la clasificación dependerá solo de la estimación: Greedy Best-First, corriendo hacia la meta y aceptando cualquier ruta por la que haya llegado. - La búsqueda en anchura no clasifica en absoluto: primero en entrar, primero en salir. Con Permitir diagonales desactivado, cada paso cuesta exactamente
1, por lo que el orden en que llegan las celdas es el orden degcreciente —y, por lo tanto, la búsqueda en anchura explora precisamente lo mismo que explora Dijkstra. Puedes confirmarlo sin volver a generar la cuadrícula: conmuta entre los dos y Nodos expandidos no se moverá ni un ápice. Activa las diagonales y el argumento cae con ello, porque una diagonal cuesta√2en lugar de1y el orden de llegada deja de seguir el coste.
Cómo leer lo que ves
La puntuación de prioridad se sitúa encima de la cuadrícula con los valores de g y h de la propia celda actual completados, para que puedas leer la clasificación que produjo la última elección. Debajo hay dos contadores: Nodos expandidos y Longitud del camino. El ámbar representa la frontera y el índigo lo ya explorado. Cambiar de algoritmo no genera una cuadrícula nueva, y eso es lo que le da valor a la comparación: en la misma distribución de cuatro vías, los Nodos expandidos de Dijkstra nunca son menos que los de A*, y los de Greedy Best-First son una pequeña fracción de cualquiera de los dos.
- Supone
- Costes de paso que nunca son negativos y una cuadrícula que no cambia mientras la búsqueda se ejecuta. El inicio es siempre la celda superior izquierda y la meta la inferior derecha. Cerrar una celda es definitivo —el bucle nunca reconsidera una— y esto solo es seguro porque ninguna ruta posterior puede llegar de forma más barata cuando cada paso añade una cantidad no negativa.
- Falla cuando
- Nodos expandidos es la cifra que varía de forma más drástica, y no es una medida de calidad. Elige Greedy Best-First: en la misma cuadrícula explora una pequeña fracción de lo que explora A*, y en la mayoría de las distribuciones devuelve una Longitud del camino mayor. Genera unas cuantas cuadrículas nuevas y observa cómo los dos contadores se mueven en direcciones opuestas. Examinar menos celdas es una afirmación sobre cuán duro trabajó el algoritmo, nunca sobre lo buena que fue su respuesta.
Ruta de aprendizaje
Contar trabajo, no segundos
Referencias (3)
- Where A*, the f = g + h scoring and the admissibility condition were introduced: P. E. Hart, N. J. Nilsson & B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4, 100–107, 1968.
- And the algorithm A* generalises, for comparison in the dropdown: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
- The fourth option in the dropdown, and the wavefront it spreads: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.