La búsqueda mejor primero es un algoritmo de búsqueda que explora un gráfico al expandir el nodo más prometedor elegido de acuerdo con una regla específica.
Judea Pearl describió la búsqueda del mejor primero como una estimación de la promesa del nodo n mediante una "función de evaluación heurísticaque, en general, puede depender de la descripción de n , la descripción del objetivo, la información recopilada por la búsqueda hasta ese punto y, lo más importante, de cualquier conocimiento adicional sobre el dominio del problema ". [1] [2]
Algunos autores han utilizado "la mejor búsqueda primero" para referirse específicamente a una búsqueda con una heurística que intenta predecir qué tan cerca está el final de una ruta de una solución (o meta), de modo que las rutas que se consideran más cercanas a una solución (o una meta) se amplían primero. Este tipo específico de búsqueda se denomina búsqueda codiciosa del mejor primero [2] o búsqueda heurística pura . [3]
La selección eficiente del mejor candidato actual para la extensión se implementa típicamente usando una cola de prioridad .
El algoritmo de búsqueda A * es un ejemplo de un algoritmo de búsqueda del mejor primero, al igual que B * . Los algoritmos del mejor primero se utilizan a menudo para la búsqueda de rutas en la búsqueda combinatoria . Ni A * ni B * son una búsqueda codiciosa del mejor primero, ya que incorporan la distancia desde el inicio además de las distancias estimadas hasta la meta.
BFS codicioso
Usando un algoritmo codicioso , expanda el primer sucesor del padre. Después de que se genera un sucesor: [4]
- Si la heurística del sucesor es mejor que la del padre, el sucesor se coloca al principio de la cola (con el padre reinsertado directamente detrás de él) y el ciclo se reinicia.
- De lo contrario, el sucesor se inserta en la cola (en una ubicación determinada por su valor heurístico). El procedimiento evaluará a los sucesores restantes (si los hay) del padre.
Ver también
Referencias
- ^ Pearl, J. Heuristics: estrategias de búsqueda inteligente para la resolución de problemas informáticos . Addison-Wesley, 1984. pág. 48.
- ↑ a b Russell, Stuart J .; Norvig, Peter (2003), Inteligencia artificial: un enfoque moderno (2a ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 0-13-790395-2. págs. 94 y 95 (nota 3).
- ^ Korf, Richard E. (1999). "Algoritmos de búsqueda de inteligencia artificial". En Atallah, Mikhail J. (ed.). Manual de algoritmos y teoría de la computación . Prensa CRC. ISBN 0849326494.
- ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Búsqueda codiciosa mejor-primero cuando falla EHC, Carnegie Mellon
enlaces externos
- Wikilibros: Inteligencia artificial: búsqueda primero en el mejor