Búsqueda Voraz Primero el Mejor

 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

Finalmente, entre los nodos hijos de Fagaras está el objetivo Bucharest y finaliza el procedimiento del algoritmo.

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(b^m), pero una buena heurística puede reducirla considerablemente.

•        Espacio

O(b^m): mantiene todos los nodos en memoria

•        Optimalidad: No

 

Referencias bibliográficas 

1.     Stuart Russell and Peter Norving. "Artifcial Intelligence a modern approach" 2010