Búsqueda Heurística

1. Los métodos de búsqueda heurística disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en primer lugar los caminos más prometedores

1.1. Caracteristicas

1.2. No garantizan que se encuentre una solución, aunque existan soluciones.

1.3. Si encuentran una solución, no se asegura que ésta tenga las mejores propiedades (que sea de longitud mínima o de coste óptimo).

1.4. En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.

2. FUNCIONES

2.1. La función heucarística puede tener dos interpretaciones.

2.2. Por una parte, la función puede ser una estimación de lo próximo que se encuentra el estado de un estado objetivo. Bajo esta perspectiva, los estados de menor valor heurístico son los preferidos

2.3. Pero en otros casos puede suceder que lo que convenga sea maximizar esa función.

3. Algoritmo

3.1. 1. Poner Nodo inicial en la lista 2. If Nodo Inicial es la solución: return ok endif. 3. Costo(inicial)= Nodo.costo; 4. While(lista.esVacia()){ 5. Selecciono el Nodo de la lista min(costo(Nodo)) 6. If Nodo es solución: return ok endif; 7. Expandir Nodo 8. Elimino la lista actual 9. Costo de los sucesores. costo(sucesor)=costo(Nodo)+sucesor.costo 10. Guardar la lista 11. } 12. Return No solución;

4. Video