Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de búsqueda informados (A∗ search (Propiedades: (Completo: Sí, …
Algoritmos de búsqueda informados
Best-first search
Idea
Usar una función de evaluación para cada nodo
Implementación
"fringe" es una cola ordenada en orden decreciente de conveniencia
Greedy search
La búsqueda codiciosa (greedy search) expande el nodo que parece estar más cerca del objetivo
Propiedades:
Completo en espacio finito con verificación de estado repetido
Tiempo: O(bm)
Espacio: O(bm)
Óptimo: No
A∗ search
Idea: Evitar expandir caminos que ya son caros
Optimidad de A*
Prueba estándar
Más útil
Propiedades:
Completo: Sí, a menos que haya infinitos nodos con f ≤ f (G)
Tiempo: Exponencial
Espacio: Mantiene todos los nodos en la memoria
Óptimo: Sí, no se puede expandir fi + 1 hasta que termine fi
Prueba de Lema: consistencia
Una heurística es consistente si: h(n) ≤ c(n, a, n0) + h(n0)
Heurística admisible
Dominio
Si h2 (n) ≥ h1 (n) para todos los n (ambos admisibles)
entonces h2 domina h1 y es mejor para la búsqueda
Relaxed Problems
Las heurísticas admisibles pueden derivarse del costo exacto de la solución de una versión relajada del problema