Búscalo aquí:

Algoritmo A* [código]

El algoritmo A*, (leído A estrella) es un algoritmo de búsqueda en grafos. Fue presentado en 1968 por Peter E. Hart,, Nils J. Nilsson y Bertram Raphael, el algoritmo encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre una condición inicial y una condición meta.


Éste algoritmo encuentra el camino de menor coste entre un nodo origen y un nodo meta, tratando de evadir los caminos de coste alto. Para cumplir con esto, el algoritmo A* usa la siguiente función de evaluación:

f(n) = g(n) + h(n)

f(n) = costo del camino del nodo inicial al nodo n

h(n) = costo estimado del nodo n a la meta

f(n) = costo estimado desde el nodo n a la meta

Éste algoritmo se caracteriza por usar heurísticas admisibles, es decir, heurísticas que nunca sobrepasan el costo real para alcanzar la meta. Además de esto cumple con la propiedad de completitud, es decir, siempre encontrará la solución si es que existe.


A* aplicado al problema del 8 - puzzle

El algoritmo A* también puede solucionar éste problema, incluso de una manera mucho más óptima (en tiempo y en espacio) comparada con las soluciones ofrecidas por los algoritmos de búsqueda no informada.

Entonces partiremos nuevamente de un determinado estado inicial al cual encontramos su función f(n), y luego expandimos, generando nuevos nodos hijos. Cada uno de estos nodos hijos son encolados en una cola de prioridad, tomando como prioridad el valor de f(n) de cada nodo generado.

Sacamos de la cola de prioridad el elemento con menor prioridad (menor f(n)) expandimos su nodos de la misma manera antes descrita. De esta manera, el árbol se va expandiendo por los nodos que representan el camino hacia el nodo meta pero con el menor coste.


Test del A* aplicado al problema del 8 - puzzle

La implementación del algoritmo A* se ha realizado haciendo uso de dos heurísticas diferentes, las cuales permiten que para un mismo nodo, el valor del costo estimando del estado de dicho nodo hacia el estado meta, tenga valores diferentes. De esta manera, las heurísticas implementadas son:

* H1: Heurística que dado un estado inicial y un estado meta para el 8-puzzle, contabiliza el número de casillas del 1 al 8 que no se encuentran en su posición correcta, sin tomar en cuenta la casilla vacía (considerada con valor 0)

Es decir, si:

estado_inicial = 213506487
estado_meta = 123456780

H1 = 1 +1 + 0 + 1+ 0 + 0 +1 + 0 + 1 = 5

Esto debido a que las casillas 2,1,5,4,7 en estado_inicial no se encuentran en su posición adecuada respecto a estado_meta. El costo máximo para alcanzar la meta aplicando H1 es 8, por lo tanto es admisible.



* H2: Heurística que dado un estado inicial y un estado meta para el 8-puzzle, contabiliza la suma total de distancias mínimas de cada casilla hacia su posición correcta, es decir se aplica la distancia total de Manhattan.

Es decir, si:

estado_inicial = 215387046

estado_meta = 123456780

H2 = 1 +1 + 2 + 3+ 1 + 3 +0 + 2 + 1 = 14


Teniendo como estado meta a 123456780, el costo máximo para alcanzar la meta aplicando H2 es 14, por lo tanto esta heurística también es admisible.




Implementación del A* aplicado al problema del 8 - puzzle

La implementación del algoritmo A* aplicado a solucionar el problema de 8 puzzle se ha realizado en C++ y hace uso de la estructura Heap Binario para implementar sobre ella la cola de prioridad y de ésta manera lograr mayor eficiencia en los resultados.

El código en C++ del algoritmo A* aplicado a solucionar el problema de 8 puzzle lo pueden descargar DESDE AQUI.

Así mismo, pueden descargar desde aqui el informe del test realizado a la implementación delalgoritmo A* aplicado a solucionar el problema de 8 puzzle.

Espero les sea de utilidad, saludos.



Quieres leer más post como éste???...suscribete aquí!!!




10 comentarios:

  1. no funciona el enlace del algoritmo a*

    ResponderEliminar
  2. El link esta correcto, volver a intentar, sino pueden hacerlo desde el link que coloc en el post, pueden hacerlo desde: http://joshi.ueuo.com/laboratorio.php?&idart=14

    saludos

    ResponderEliminar
  3. Hola a todos, debido a que muchos lectores me comentaron por correo que el link no funciona bien (a mi si y entro como usuario :P), asi que cambie de servidor, por el que siempre uso para este tipo de trabajos

    El nuevo link es: codigo en C++ del Algoritmo A*.

    Saludos

    ResponderEliminar
  4. holaaaaa...
    oie el link sigue sin funcionar :S :S... dice que la pag no se encuentra

    ResponderEliminar
  5. el primer link de descarga me abre varios ventanas en el borland cosa ke no se puede llegar a correr.. el 2do link esta roto... Alguien me puede enviar el nuevo link ke sisi funke.. wtc_gm01@hotmail.com

    ResponderEliminar
  6. hola, yo lo ejecute en los IDE's DevC++ y CodeBlocks y si corre ok.

    El otro link tambien esta operativo, es de un informe de resultados, muestra estadisticas de la ejecucion del programa

    ResponderEliminar
  7. he estado intentando realizar este mismo proyecto del puzzle 8 para el puzzle 8 en java, usando tablas hash, para busqueda en profundidad y en anchura, pero me hasido bastante dificil, me podrian ayudar con este problema?, gracias :D

    ResponderEliminar
  8. El link para bajar el código no funciona, y me interesa mucho poder observarlo y correrlo para ver su funcionamiento real.
    Si no es mucha molestia me gustaría que me proporcionaras el código o que lo volvieras a a subir.
    Gracias.

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...