¿Qué es una explicación intuitiva de la búsqueda A *?

Imagínese en una ciudad como Chicago o Nueva York, con distintas cuadras de la ciudad, algunos edificios muy altos, pero por lo demás una geografía plana. De hecho, Taipei funcionaría mejor.

El desafío : debes llegar del punto A (ubicación actual) al punto B (la torre Taipei 101) lo más rápido posible, pero solo puedes caminar a una velocidad constante. Por lo tanto, se trata de encontrar una ruta más corta (una de varias posibles, o potencialmente una ruta única). No tiene un mapa, y ni siquiera tiene la dirección del punto B, pero una vez que esté allí, reconocerá la torre porque es muy única. Además, tiene un recuerdo perfecto del área que ha visitado desde el comienzo de su búsqueda.

Una solución simple : explore el área alrededor de su ubicación actual, expandiéndose gradualmente en todas las direcciones. Esto corresponde a Breadth-First Search en gráficos no ponderados y la búsqueda de la ruta más corta de una sola fuente (SSSP) de Dijkstra en gráficos ponderados . En particular, uno mantiene una lista de nuevas ubicaciones accesibles en un paso (una cuadra de la ciudad) desde cualquier (alguna) ubicación visitada, y selecciona repetidamente una ubicación que proporcionará una ruta más corta desde la fuente (comparando las longitudes de ruta con diferentes potenciales nuevos ubicaciones). Después de seleccionar una ubicación, las prioridades de las ubicaciones adyacentes deben actualizarse. Para cuando se alcance el punto B, la búsqueda habrá explorado una gran cantidad de áreas innecesarias, incluso en la dirección alejada de B. Entonces, ¿cómo se evita perder el tiempo en la búsqueda?

Información clave : si el edificio alto en el punto B se puede ver desde su ubicación inicial (punto A), entonces la búsqueda puede avanzar hacia el punto B, explorando otras direcciones solo lo necesario para posibles desvíos.

Detalles : el problema es que las manzanas de la ciudad no te permitirán moverte en línea recta. Entonces, A * -search es una pequeña modificación del algoritmo de Dijkstra que agrega algo a la prioridad utilizada para dar el siguiente paso. Específicamente, puede agregar la distancia en línea recta desde la próxima ubicación potencial a la meta (punto B). Se demuestra un teorema que garantiza la búsqueda de caminos más cortos si el término agregado no es mayor que la distancia más corta real (por ejemplo, puede ser la mitad de la distancia). Este término se llama función admisible . La suma de la longitud del camino hasta ahora (A-> X) y la función admisible para su punto final intermedio (X-> B) no excede la longitud real del camino (A-> X-> B) e incluso la longitud del camino más corto (A-> B).

Para resumir , desde la perspectiva de la implementación, A * -search es solo el algoritmo de ruta más corta de Dijkstra con un pequeño ajuste. Se puede aplicar en gráficos explícitos en, por ejemplo, juegos de computadora y navegación basada en GPS. Aún más efectivamente, puede conducir a una aceleración exponencial en gráficos implícitos . Por ejemplo, si desea resolver el rompecabezas de 15, A * -search es el camino a seguir. Una buena función admisible sería la suma de las distancias que cada baldosa necesita recorrer desde la posición actual hasta la posición final. Para casos de más desafíos, como el rompecabezas 24, hay funciones admisibles mucho más elegantes (R.Korf trabajó en este tema durante muchos años y es un placer leer sus documentos). Por lo tanto, es muy posible que la mayor parte de su programa calcule una función admisible que se utilizará en el procedimiento de búsqueda basado en gráficos, que de otro modo sería sencillo.

Para comprender A *, primero debe comprender el algoritmo de Dijkstra.

El algoritmo de Dijkstra se basa en la idea de que si visita vértices en orden creciente de distancia desde la fuente, en cualquier momento dado siempre podrá determinar correctamente la distancia al siguiente vértice que visite. Entonces, en cualquier momento, tiene un conjunto S de vértices que ya ha visitado, y sabe que todos los vértices no visitados (llame a este conjunto T) están más lejos que todos los vértices en S. Ahora puede seleccionar el vértice más cercano en T, al considerar todos los bordes fuera de S y dentro de T. (No hay forma de que el vértice más cercano en T requiera dos o más bordes fuera de S, porque entonces el punto final del primer borde fuera de S estaría más cerca. Tenga en cuenta que esto requiere borde longitudes para que no sean negativas.) Luego mueva este vértice a S y repita hasta que visite su vértice de destino. Ahora sabemos la distancia correcta al destino.

Usamos A * para aplicaciones donde no tiene sentido visitar vértices en orden creciente de distancia desde la fuente, porque simplemente hay demasiados vértices que tendrían que ser visitados antes de que pudiéramos visitar el destino, y también tomaría mucho tiempo y usamos demasiada memoria, y solo nos importa el destino, no ninguno de los otros vértices. Así que tratamos de adivinar qué vértice debemos visitar a continuación para que nos acerque más al destino. En particular, suponemos la distancia desde el vértice hasta el destino. La suposición es una función llamada heurística . A * visita los vértices en orden creciente de (distancia desde la fuente) + heurística. Si elige tomar una ruta desde el origen hasta el destino que atraviesa algún vértice V, entonces, intuitivamente, la longitud total de esa ruta que espera es (distancia desde la fuente hasta V) + (distancia desde V hasta el destino). Cuanto más pequeño es este valor, “mejor” es el vértice, en el sentido de que pasar por ese vértice se predice que dará como resultado una ruta más óptima. Si nuestras suposiciones son bastante buenas, entonces básicamente podemos ignorar la mayoría de los vértices que no se encuentran en el camino más corto y encontrar rápidamente el camino más corto hacia el destino.

De hecho, suponiendo que su heurística nunca sobreestime la distancia al destino, se garantiza que A * encontrará la ruta más corta correcta desde el origen hasta el destino (es decir, en el instante en que visita el destino, conoce la distancia correcta). Intuitivamente, esto se debe a que si la heurística sobreestima, puede ignorar un vértice que debería estar en el camino más corto. Pero siempre que la heurística no se sobreestime, incluso si inicialmente pasa por encima de un vértice que debería estar en el camino más corto (porque subestimó algún otro vértice aún más), eventualmente tendrá que volver a él porque todos los otros caminos explorar primero resultará ser más largo. Por supuesto, si subestimas demasiado, entonces la búsqueda no hace un buen trabajo al explorar buenos caminos desde el principio, y la búsqueda se vuelve muy ineficiente. Cuanto más cerca esté su estimación, más eficiente será la búsqueda. (La última subestimación, el caso donde la heurística siempre devuelve cero, se reduce al algoritmo de Dijkstra).

Grandes respuestas aquí, pero en su mayoría son bastante profundas. Quería intentar dejar una respuesta mucho más simplificada (específicamente con gráficos ponderados).

Supongamos que tiene un mapa con un montón de destinos. Usted asigna “pesos” a cada conexión (entre puntos). Esto podría ser simplemente la distancia, o también podría incluir cosas como la altura y el tipo de terreno. Puede ser cualquier cosa que necesites que sea.

Ahora, cuando desee encontrar el camino más corto desde su ubicación hasta un destino, simplemente obtendrá el camino con el menor peso. A * hace esto pero también calcula una heurística para hacerlo más eficiente. Para simplificar la explicación de este proceso, esencialmente dibuja una línea directamente al objetivo para elegir la (s) ruta (s) que es más probable que sea la más corta. Esto ayuda a determinar si, por ejemplo, el camino que está mirando no está ni siquiera en la dirección correcta.

De todos modos, es tan simple como puedo hacerlo (al menos escribiendo en mi teléfono). Esperemos que ayude y no confunda. Las otras respuestas son mejor información, pero esto está destinado a la simplicidad.

Aquí hay una explicación del algoritmo de búsqueda A *.