Torres de Hanoi Heuristica

                           Torres de Hanoi  Heuristica Pura 

Desarrollar el siguiente ejercicio de las Torres de Hanoi, con eucarística A* y definir si el grafo tiene los siguientes conceptos:

Eucarística -Admisible

                 - Consistente

                 - Monótona

Estado Inicial:

Estado final

Se solucionan el problema con el algoritmo de búsqueda A* porque este algoritmo su objetivo  es encontrar siempre y cuando se cumplan determinadas condiciones, el camino de menor costo entre un nodo origen y uno objetivo, es la forma más ampliamente conocida de la búsqueda primero el mejor, siendo la búsqueda A* tanto completa como óptima entonces lo que buscamos es el costo de llegar al nodo actual.

La siguiente Función que manejaremos es:

                          

En consiste la Ecuación :

-g(n) es:Costo para llegar al nodo n

-F(n) es : Costo final del camino para llegar al nodo deseado, a través del nodo n

-h(n) es; Costo estimado para llegar al nodo de solución desde el nodo n  

Aquí veremos el grafo:

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