El algoritmo de búsqueda es uno de las mejores y más populares técnicas utilizadas en la búsqueda de caminos y los recorridos de gráficos

Que es una heurística ?

El término heurística se utiliza para algoritmos que encuentran soluciones entre todos las posibles alternativas, pero no garantizan que se encuentren los mejores, por lo que pueden ser considerados como algoritmos aproximados y no precisos. Estos algoritmos, por lo general encuentran una solución cercana a la mejor solución y la encuentran rápido y fácilmente. A Veces estos algoritmos pueden ser exactos, que es que realmente encuentren la mejor solución, pero el algoritmo todavía se llama heurística hasta que está mejor solución ha demostrado ser la mejor.El método utilizado desde un algoritmo heurístico Es uno de los métodos conocidos, como el de la codicia, pero para ser fácil y rápido el algoritmo ignora o incluso suprime algunas de las demandas del problema.

Algoritmo de Búsqueda A*

A * El algoritmo de búsqueda es uno de las mejores y más populares técnicas utilizadas en la búsqueda de caminos y los recorridos de gráficos.

Informalmente hablando,los algoritmos de búsqueda A*, a diferencia de otras técnicas de recorrido, tiene "cerebros". Lo que significa es que es realmente un algoritmo inteligente que lo separa de los otros algoritmos convencionales.

Y también vale la pena mencionar que muchos juegos y mapas basados ​​en web utilizan este algoritmo para encontrar el camino más corto muy eficientemente (aproximación).

Consideremos una rejilla cuadrada que tiene muchos obstáculos y se nos da una célula inicial y una célula objetivo. Queremos llegar a la célula objetivo (si es posible) de la celda de partida lo más rápido posible. Aqui el Algoritmo  A*de búsqueda viene al rescate.

Lo que hace el algoritmo de búsqueda A * es que en cada paso elige el nodo de acuerdo con un valor -f 'que es un parámetro igual a la suma de otros dos parámetros -' g 'y' h '. En cada paso elige el nodo / célula que tiene el 'f' más bajo, y procesa ese nodo / célula.

Definimos 'g' y 'h' tan sencillamente como sea posible a continuación

G = el costo de movimiento para moverse desde el punto de partida a un cuadrado dado en la cuadrícula, siguiendo el camino generado para llegar allí.

H = el costo de movimiento estimado para moverse desde ese cuadrado dado en la cuadrícula hasta el destino final. Esto se refiere a menudo como la heurística, que no es más que una especie de conjetura inteligente. Realmente no sabemos la distancia real hasta que encontramos el camino, porque todo tipo de cosas pueden estar en el camino (paredes, agua, etc.). Puede haber muchas maneras de calcular esta 'h' que se discuten en las secciones posteriores.

Heurística

Podemos calcular g, pero ¿cómo calcular h?

Podemos hacer dos cosas.

A) Calcule el valor exacto de h (que sin duda requiere mucho tiempo).

              O

B) Aproximar el valor de h usando algunas heurísticas (menos tiempo).

Discutiremos ambos métodos.

A) Heurística exacta -

Podemos encontrar valores exactos de h, pero eso es generalmente mucho tiempo.

A continuación se presentan algunos de los métodos para calcular el valor exacto de h.

1) Pre-calcular la distancia entre cada par de células antes de ejecutar el algoritmo de búsqueda A *.

...