Algoritmo A Estrella

Taller Final
“Heurística”

Integrantes: Alexis Peralta Silva
Camilo Vargas Medalla
Asignatura: Inteligencia Artificial
Carrera : Ing. Civil en Computación eInformática
Profesor : Dagoberto Navea Alfaro
Fecha : 19 de Junio - 2012

Representacion de todos los estados – “Mall Las Americas”.
1er Piso
2do Piso

•Una vez que tenemos definido elespacio de búsqueda, el paso siguiente es definir la
tercera de las componentes principales de un sistema de búsqueda: la estrategia de
control o algoritmo de búsqueda.

•La estrategia decontrol indica el orden en el que se van a visitar los nodos a partir del
nodo inicial para llegar a un nodo objetivo.

•La estrategia de control es el elemento más importante desde el punto de vistade la IA.
Una buena estrategia de control debe permitirnos llegar a una solución sin necesidad de
visitar todos, o casi todos, los nodos del espacio de búsqueda.
a) Algoritmo: Voraz
Elalgoritmo elegido es el voraz (primero el mejor) ya que este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Para resolver un determinadoproblema, sigue una heurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima.
Función de evaluación f(n) = h(n) (heurística).
* Labúsqueda voraz primero el mejor expande el nodo más cercano al objetivo.
* Probablemente conduce rápidamente a una solución.
* Evalúa los nodos utilizando solamente la función heurística,que, en general, se minimiza, porque se refiere a un coste f(n) = h(n).
•  La prioridad la marca la función heurística (coste estimado del camino que falta hasta la solución).
* En cadaiteración se escoge el nodo más “cercano” a la solución (el primero de la cola).
* No se garantiza la solución óptima.
La BÚSQUEDA VORAZ PRIMERO EL MEJOR trata de expandir el nodo más cercano al...