Ejercicio de Busqueda A*

Algoritmo de búsqueda  A estrella 

Es un algoritmo de búsqueda para el cálculo de caminos mínimos o en grafos algoritmo heurístico, una de sus características es que hará uso de una función de evaluación heurística, mediante la cual etiquetar los diferentes nodos del grafo  y que servirá para determinar la probabilidad de dichos nodos de pertenecer al camino óptimo.

El pseudocódigo es el siguiente:

Para demostrar lo dicho anteriormente mostraré un ejemplo

El nodo inicial es el nodo (2,4) o el que está de color verde, el nodo final es el nodo (3,2) o nodo Azul , los nodos de color Morado  son nodos sólidos y no pueden ser traspasados.

Al empezar el algoritmo tendremos el nodo inicial como opción y lo agregamos a la lista abierta, luego como no es el nodo final, obtenemos sus nodos adyacentes y luego lo dejaremos en la lista cerrada, calculamos los valores de los nodos de la lista abierta (a menos que ya los hayamos calculado) y tomamos el de menor valor:

La heurística que se utilizo  es la distancia de Manhattan:

H = Math.Abs(nodoActual.X – nodoFinal.X) + Math.Abs(nodoActual.Y – nodoFinal.Y)

Ejemplo tomamos el cuadrado B (1,4) hasta el nodo final (3,2)

h = (1 – 3) + (4 – 2)

h =  2 + 2

h = 4

En resumen Lo que hicimos fue contar los cuadrados que hay para llegar del nodo actual al nodo final, Ahora, el nodo que tiene el menor valor es C, por lo tanto buscamos sus nodos adyacentes, dando como resultado el nodo E y F porque los demás son sólidos y el nodo (4,5) aunque es alcanzable diagonalmente, es inalcanzable porque uno de los nodos cerca es sólido, por último se  añade el nodo C a la lista cerrada y los demás nodos a la lista abierta, pero como ya se encuentran, se verifica que el valor calculado no sea menor