Principio del algoritmo A*

El algoritmo A* (A-Star) es el método de búsqueda directa más eficaz para resolver el camino más corto en una red de carreteras estática.

Ten en cuenta que es el algoritmo de búsqueda directa más eficiente. Desde entonces, han aparecido muchos algoritmos de preprocesamiento (ALT, CH, HL, etc.) y su eficiencia de búsqueda en línea es miles o incluso decenas de miles de veces mayor que la del algoritmo A *.

La fórmula de cálculo se expresa como: f(n)=g(n) h(n),

Entre ellos, f(n) es desde el punto inicial hasta el objetivo punto a través del nodo n Función de estimación,

g(n) es el costo real desde el nodo inicial hasta n nodos en el espacio de estados,

h(n) es el mejor camino desde n al costo estimado del nodo objetivo.

La clave para garantizar que se encuentre el camino más corto (de la solución óptima) es la elección de la función de estimación f(n):

El valor estimado h(n)lt ; = n al objetivo El valor real de la distancia del nodo. En este caso, la cantidad de puntos buscados es grande, el rango de búsqueda es grande y la eficiencia es baja. Pero se puede obtener la solución óptima. Y si h (n) = d (n), es decir, la distancia estimada h (n) es igual a la distancia más corta, entonces la búsqueda seguirá estrictamente el camino más corto y la eficiencia de la búsqueda es la más alta en este momento.

Si el valor estimado>valor real, el número de puntos buscados es pequeño, el rango de búsqueda es pequeño y la eficiencia es alta, pero no se puede garantizar la solución óptima.