Este algoritmo selecciona un nodo para expansión basada en una función de evaluación (f(n)), tradicionalmente se selecciona el nodo con la evaluación más baja, la evaluación mide la distancia al objetivo, Usa BUSQUEDA-ÁRBOLES con cola de prioridad.
Existe toda una familia de algoritmos de Búsqueda Primero el
Mejor con diferentes funciones de evaluación, cada uno tiene una función
heurística f(n) = h(n) es el costo estimado del camino más barato desde el nodo
n hasta el nodo objetivo.
En el planeamiento de rutas, la heurística f(h) sería el
costo del camino más barato puede ser la distancia en línea recta entre dos
ciudades.
Ejemplo:
Considerando el mapa de Romanía y como heurística la
distancia en línea recta desde las diferentes ciudades hasta Bucharest, según
el problema planteado en [1]. Averiguar el camino con costo menor desde Arad a
Bucharest.
Aplicando
el algoritmo Voraz primero el mejor, tomamos Arad con h(n) = 366
Expandimos los nodos adyacentes a Arad
Elegimos el menor nodo con menor valor h(n), en este caso Sibiu
Entre los nodos hijos de Sibiu con menor valor h(n) es Fagaras
|
|
||
|
|
Solución: El algoritmo primero el mejor ha permitido
hallar el camino Arad-Sibiu-Fagaras-Bucharest
Pregunta:
¿El camino
hallado Arad-Sibiu-Fagaras-Bucharest es el mejor?
Resp:
No, el
camino mejor es: Arad-Sibiu-Rimnicu Vicea-Pitesti-Bucarest
• Completitud
No, puede quedar atrapada
en ciclos (p.e., saltando de una misma ciudad a otra)
• Tiempo
O(bm), pero una buena heurística
puede reducirla considerablemente.
• Espacio
O(bm): mantiene todos los nodos
en memoria
• Optimalidad: No
Referencias bibliográficas
1. Stuart
Russell and Peter Norving. "Artifcial Intelligence a modern approach"
2010
