Un paso de Dijkstra el algoritmo A* (leer: «una estrella»). En términos de búsqueda de caminos, el algoritmo de Dijkstra querrá probar cada camino y cada vértice para encontrar el camino más corto entre su punto de partida y destino, mientras que A* tiene un atributo adicional, una heurística, que debería permitirle encontrar el camino más corto sin necesidad de verificar cada camino y vértice. Cada algoritmo tiene sus casos de uso, pero en términos generales, tanto Dijkstra como A* pueden encontrar el camino más corto, pero A* lo hará más rápido.

Recomendaría saber un poco sobre el algoritmo de Dijkstra antes de entrar en este artículo, ya que hay muchos puntos de comparación. O mejor aún, ¡lee mi último artículo sobre el tema! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629

Voy a necesitar configurar algunas cosas para mis ejemplos, además de dar una definición de lo que es una heurística. Para empezar, déjame mostrarte el tipo de gráfico que quiero usar para mis ejemplos.

Esto es un poco abstracto, pero quiero usar un tablero a cuadros como mi gráfico, y quiero permitir el movimiento entre sus cuadrados. Si superpongo el gráfico equivalente con vértices y aristas, debería verse algo como esto.

Tomemos el cuadrado/vértice central, E, por ejemplo. Tiene ocho vértices vecinos, por lo que podemos movernos arriba, abajo, izquierda, derecha y en todas las combinaciones diagonales de cada uno. Y eso es realmente todo lo que estaba tratando de configurar aquí: voy a usar un tablero de ajedrez, y permitiré el movimiento en ocho direcciones. Un poco largo, pero ahora comencemos a ver el movimiento y el costo del movimiento.

Comenzando de manera simple, diré que moverse hacia arriba, hacia abajo, a la izquierda y a la derecha tiene un costo de movimiento de 1. El tablero se está poniendo ocupado, así que extraeré el gráfico y agregaré el costo del movimiento como pesos de bordes.

Si estos pesos son distancias, y si las relaciones y los vecinos están dispuestos de esta manera, la geometría puede decirnos sobre el costo de los movimientos diagonales. Usando el Teorema de Pitágoras, deberíamos obtener √(12 + 12) = √2, que es aproximadamente 1.41421356237 Which que no es un número muy agradable para trabajar. Por lo tanto, robaré una idea (¡y citaré mis fuentes!), y multiplicar y redondear los costos hacia abajo. Para ambos tipos de movimiento, los multiplicaré por diez, y luego truncaré sus decimales. Esto nos dará costos finales de 10 para los movimientos hacia arriba, hacia abajo, izquierda y derecha, y 14 para los movimientos diagonales.

Heurística

Siento que estos son difíciles de definir para mí, así que comenzaré con la línea de apertura de Wikipedia sobre el tema:

En informática, inteligencia artificial y optimización matemática, una heurística (del griego ερρίσκω «Encuentro, descubro») es una técnica diseñada para resolver un problema más rápidamente cuando los métodos clásicos son demasiado lentos, o para encontrar una solución aproximada cuando los métodos clásicos no encuentran ninguna solución exacta. Esto se logra negociando la optimalidad, la integridad, la precisión o la precisión de la velocidad. En cierto modo, puede considerarse un atajo.

Es útil? ¿Lo entiendes? Porque no lo entiendo. Quiero decir, lo entiendo un poco, y es una descripción precisa, pero si esta fuera la primera vez que escucharas sobre una heurística, no estoy seguro de que obtendrías la imagen completa de lo que son las heurísticas de esto. Tal vez si te cuento sobre la heurística de A*, obtendrás una mejor comprensión.

Con el algoritmo de Dijkstra, el enfoque se centró en un valor: la distancia más corta desde el índice de inicio. Lo cual, cuando lo piensas, es un poco extraño. Tienes este algoritmo tratando de encontrar caminos nuevos y más cortos a algún destino, pero su enfoque siempre está en dónde comenzó. Imagina a alguien que sale a comprar alimentos, pero camina todo el camino hacia atrás, tratando de vigilar su casa hasta que llega a la tienda. En la vida real, esto probablemente no funcionaría, pero tal vez si les dieras tiempo para ir por toda la ciudad, eventualmente podría funcionar.

Saliéndose de esta analogía tonta, A * es diferente de Dijkstra porque sugiere dar la vuelta y caminar hacia adelante. A*, como Dijkstra, también realiza un seguimiento de cuán lejos está de casa, pero su característica única es que también realiza un seguimiento de cuán lejos está de su destino. Al dar el siguiente paso, Dijkstra mirará qué camino es actualmente el más corto, pero A * va un paso más allá y también considera si ese paso lo está acercando a su objetivo. Más simplemente, A* tiene una estimación aproximada de su distancia restante a su objetivo, y cuando esa estimación se acerca a cero, sabe que se está moviendo en la dirección correcta. Esta es la heurística que usaremos en nuestros ejemplos.

Paso a través del Algoritmo

Este va a ser un ejemplo bastante simple, pero debería mostrarle el flujo básico y la repetición del algoritmo. Me aseguraré de proporcionar enlaces en mis referencias a otros ejemplos más complicados, pero esto debería ser una buena guía para ellos. Voy a usar una configuración similar a la forma en que he demostrado Dijkstra.

Una diferencia más entre Dijkstra y A* es que Dijkstra empieza a hacer loops inmediatamente, pero A* tiene que hacer una pequeña configuración para su vértice de inicio. Así que vamos a hacer eso ahora, y tener una idea de cómo va a funcionar la mesa.

en Primer lugar, vamos a añadir Una para el conjunto Abierto. Segundo, averiguaremos la distancia de A desde el principio. Naturalmente, la distancia de A a A es cero, por lo que se agregará a la tabla, y tendré que ser el número en la esquina superior izquierda del cuadrado de A. Tercero, determinaremos la distancia heurística. Podemos hacer esto de cualquier manera, todo lo que es importante es que medimos esta distancia de la misma manera para cada cuadrado. Voy a usar una distancia en línea recta para todas las distancias heurísticas, lo que significa que puedo hacer uso del Teorema de Pitágoras de nuevo. En este caso, calcularemos √(202 + 302), y encontraremos que A es una distancia de 36.0555127546 from desde L (Redondearé los decimales a la décima más cercana para ahorrar espacio). Agregaré esto a la mesa y lo colocaré en la esquina superior derecha del cuadrado A. Finalmente, la suma. Agregaré la distancia más corta desde el inicio hasta la distancia heurística, la agregaré a la mesa y la colocaré en el centro del cuadrado de A.

Ese es nuestro punto de partida, y ahora podemos mirar a los vecinos de A y agregar sus valores a la tabla.

en Primer lugar, vamos a añadir B, E, y F para el conjunto Abierto. A continuación, podemos encontrar sus distancias más cortas desde el inicio, y porque todo está a un paso del inicio, solo serán 10 para B y E, y 14 para el movimiento diagonal a F. Para la distancia heurística, usaremos el Teorema de Pitágoras desde cada cuadrado hasta el vértice final. Finalmente, obtendremos sus sumas y agregaremos » A » a cada una de sus columnas de vértices anteriores.

En este punto, hemos hecho todo lo necesario con A, por lo que se moverá al conjunto Cerrado, y necesitaremos un nuevo vértice actual. Para determinar qué vértice se debe examinar a continuación, veremos el conjunto Abierto y encontraremos el vértice que tiene la suma más baja. Ahora mismo, eso es F con una suma de 36.1. Por lo tanto, lo convertiremos en el vértice actual y comenzaremos a elaborar los valores para sus vecinos.

F tiene ocho vecinos, pero sólo cinco se van a cambiar aquí. En primer lugar, A está en el set cerrado ahora, por lo que no se puede cambiar ahora. Para los siete restantes, los agregaremos al set Abierto (a menos que ya sean parte de él), y luego trabajemos en sus distancias desde el principio. Esto va a funcionar mucho como el algoritmo de Dijikstra, y agregaremos la distancia de F desde el inicio a la distancia de cada uno de sus vecinos desde F. En nuestra tabla, la distancia de F desde el inicio es 14, así que llenaremos 14+10=24 o 14+14=28 para estos. Sin embargo, B y E ya tienen distancias más cortas hasta el inicio, por lo que sus registros de tabla no se actualizan. Eso deja cinco vértices que se actualizarán, con C, I y K obteniendo 28, y G y J obteniendo 24 por su distancia desde el inicio. A continuación, use el Teorema de Pitágoras para cada una de las distancias heurísticas de estos vértices, luego calcule sus sumas y, finalmente, agregue «F» a la columna de vértices anterior para los vértices que se actualizaron.

F se ha completado y se moverá al conjunto Cerrado, y se elegirá un nuevo vértice actual en función del vértice del conjunto abierto que tenga la suma más baja. Está muy cerca, pero K es una décima más pequeña (Y sí, esto se debe a una diferencia de redondeo, pero en este caso, resulta ser un buen desempate). K será el nuevo vértice a examinar, así que comencemos por mirar a sus vecinos.

K tiene seis vecinos, tres de los cuales ya están en el conjunto Abierto, por lo que las dos últimas H y L será añadido al conjunto Abierto así. Ahora, calcularemos sus distancias desde el inicio. La distancia de K desde el inicio es de 28, por lo que trabajaremos con 28+10=38 para G, J y L, y 28+14=42 para H. Sin embargo, G y J ya tienen distancias más pequeñas para comenzar, por lo que no se actualizarán. Encontraremos las distancias heurísticas para cada uno, calcularemos sus sumas y agregaremos «K» a cada vértice anterior que se actualizó.

K se completa y se mueve al conjunto Cerrado, y el siguiente vértice en el Abierto con la suma más pequeña es L, ¡nuestro destino!

Ahora, que L es el vértice actual, el algoritmo termina, y podemos usar nuestra mesa para trazar el camino de vuelta a la partida:

• L anterior del vértice es K
• K la anterior vértice es F
• F’ anterior vértice es el vértice de partida.

Así, esto significa que el camino más corto es Un > F > K > L.

Analizando los resultados

En comparación con el algoritmo de Dijkstra, A* ha dejado un gran lío detrás de él. Veamos algunos puntos extraños. Comenzando, mira el vértice C y su distancia al inicio: 28. Eso parece raro porque A y C son solo dos movimientos horizontales separados el uno del otro, por lo que la distancia más corta debería ser 20. En este momento, C parece pensar que su camino más corto a A son dos movimientos diagonales a través de F.

Cuando termine el algoritmo de Dijkstra, debería proporcionar una tabla muy completa de distancias desde el punto de partida. Por el contrario, la tabla de A * tiene valores incorrectos, y le falta por completo el vértice D. Pero obtuvo la misma respuesta que la de Dijkstra, y lo hizo mucho más rápido. Dijkstra hubiera querido mirar los 12 vértices antes de declarar que encontró el camino más corto; A* solo necesitaba mirar 4 antes de encontrar el camino correcto. Este cambio en la velocidad se debe a la heurística que estábamos usando: tan a menudo como pudimos, queríamos cerrar la distancia con nuestro destino. Si volvemos a la definición de heurística de Wikipedia, A * ha cambiado integridad por velocidad.

Probemos otro pequeño ejemplo, pero con una obstrucción en el camino hacia el destino.

el punto de Partida es la parte superior izquierda de vértice, y Una* está tratando de encontrar el camino más corto hacia la parte inferior derecha del vértice. Los cuadrados negros representan un espacio en el gráfico y no se pueden atravesar. Si A* sigue su heurística de «siempre acércate al destino», esos cuadrados negros lo llevarán a un callejón sin salida.

En este punto, Un* se busca la menor de las sumas, que serán las plazas justo debajo y a la derecha del vértice de partida. A * explorará ambos caminos, pero el camino hacia abajo se encontrará con otro callejón sin salida, y el camino hacia la derecha encontrará un camino alrededor de los cuadrados negros. Podría ser un poco diferente a esto, pero asumamos que así es como A* manejó este escenario. Incluso cuando se encontraba en callejones sin salida, era capaz de regresar y encontrar otro camino, y no necesitaba mirar cada vértice (el vértice superior derecho se saltó de nuevo). Esto significa que cuando una* estrella está corriendo en su peor momento, es básicamente tan rápido como el rendimiento normal de Dijkstra. Cada algoritmo tiene casos de uso perfectamente válidos, pero en términos de búsqueda de rutas y encontrar las rutas más cortas, A* es la mejor opción.