Búsqueda de los mejores primero

La búsqueda del mejor primero es una clase de algoritmos de búsqueda que explora un gráfico expandiendo 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ística que, 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]}${\displaystyle f(n)}$

Algunos autores han utilizado el término "búsqueda best-first" para referirse específicamente a una búsqueda con una heurística que intenta predecir qué tan cerca está el final de un camino de una solución (o meta), de modo que los caminos que se juzgan más cercanos a una solución (o meta) se extienden primero. Este tipo específico de búsqueda se denomina búsqueda best-first voraz ^[2] o búsqueda heurística pura . ^[3]

La selección eficiente del mejor candidato actual para la extensión normalmente se implementa utilizando una cola de prioridad .

El algoritmo de búsqueda A* es un ejemplo de un algoritmo de búsqueda de mejor primero, al igual que B* . Los algoritmos de mejor primero se utilizan a menudo para encontrar rutas en la búsqueda combinatoria . Ni A* ni B* son búsquedas de mejor primero codiciosas, ya que incorporan la distancia desde el inicio además de las distancias estimadas hasta el objetivo.

Usando un algoritmo voraz , expanda el primer sucesor del padre. Después de que se genera un sucesor: ^[4]

1. Si la heurística del sucesor es mejor que la de su padre, el sucesor se coloca al principio de la cola (con el padre reinsertado directamente detrás de él) y el bucle se reinicia.
2. De lo contrario, el sucesor se inserta en la cola (en una ubicación determinada por su valor heurístico). El procedimiento evaluará los sucesores restantes (si los hay) del padre.

A continuación se muestra un ejemplo de pseudocódigo de este algoritmo, donde la cola representa una cola de prioridad que ordena los nodos en función de sus distancias heurísticas desde el objetivo. Esta implementación realiza un seguimiento de los nodos visitados y, por lo tanto, se puede utilizar para gráficos no dirigidos . Se puede modificar para recuperar la ruta.

El procedimiento GBS(inicio, destino) es : marcar inicio como visitado añadir inicio a la cola mientras la cola no esté vacía haz lo siguiente : current_node ← vértice de la cola con la distancia mínima al objetivo eliminar current_node de la cola para cada vecino n del nodo actual hacer : si n no está  en visitado entonces : si n es objetivo: devolver n de lo contrario : marcar n como visitado añadir n a la cola Fallo de retorno

• Búsqueda de haz
• Algoritmo de búsqueda A*
• Algoritmo de Dijkstra

• Wikilibros: Inteligencia artificial: búsqueda de lo mejor primero