Búsqueda Informada
Profesor Romero Herrera Rodolfo
22/03/2012
Práctica 4 Inteligencia Artificial – Búsqueda Informada (Rompecabezas)
Algoritmo A*, Primero el mejor, etc.
AlbertoA. Rosales Valencia
Boleta: 2008630445 E-mail: AlbertoRValencia@gmail.com
Resumen
El presente trabajo propone la realización de una aplicación que se desenvuelva en una de las áreastemáticas mas estudiadas de la Inteligencia Artificial como es la Búsqueda Informada, muy altamente aplicada en juegos, comenzando con la definición de un punto de partida inicial y punto destino. En estecaso se aplicará uno de los mejores algoritmos en búsqueda de rutas entre 2 puntos, el algoritmo A*, con el cual se rearmara un rompecabezas automáticamente.
Palabras Clave: InteligenciaArtificial, Heurística, A*, Búsqueda Informada, Grafos.
Introducción
El algoritmo A* es un algoritmo de búsqueda en grafos el algoritmo encuentra, siempre y cuando se cumplan unas determinadascondiciones, 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 decoste 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 na 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 realpara alcanzar la meta. Además de esto cumple con la propiedad de completitud, es decir, siempre encontrará la solución si es que existe.
Método/Diseño
El método empleado para desarrollar estapráctica fue el algoritmo A*, ya que este demuestra una estrategia óptima debido a su propuesta, que se basa en no solo considerar una ruta para llegar al camino, sino en tener una flexibilidad para...
Regístrate para leer el documento completo.