Mejor primera búsqueda

Mejor primera búsqueda 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 mejor primera búsqueda como la estimación de la promesa del nodo n por una función de evaluación heurística f()n){displaystyle f(n)} que, en general, puede depender de la descripción n, la descripción del objetivo, la información reunida por la búsqueda hasta ese punto, y lo más importante, sobre cualquier conocimiento extra sobre el dominio del problema."

Algunos autores han utilizado la "búsqueda mejor primero" 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 (u objetivo), de modo que los caminos que se consideran más cercanos a una solución (u objetivo) se extiendan primero. Este tipo específico de búsqueda se denomina búsqueda codiciosa de lo mejor primero o búsqueda heurística pura.

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

El algoritmo de búsqueda A* es un ejemplo de algoritmo de búsqueda del 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 una búsqueda codiciosa de lo mejor primero, ya que incorporan la distancia desde el inicio además de las distancias estimadas hasta la meta.

Codiciosa BFS

Usando un algoritmo codicioso, expanda el primer sucesor del padre. Después de generar un sucesor:

1. Si la heurística del sucesor es mejor que su padre, el sucesor está situado en el frente de la cola (con el padre reinsertado directamente detrás de ella), y el bucle se reinicia.
2. Elegido, el sucesor se inserta en la cola (en un lugar determinado por su valor heurístico). El procedimiento evaluará a los sucesores restantes (si los hay) del padre.

A continuación se muestra un ejemplo de pseudocódigo de este algoritmo, donde 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, puede usarse para gráficos no dirigidos. Se puede modificar para recuperar la ruta.

procedimiento GBS(start, target) es:
Mark start as visited
añadir inicio a la cola
 mientras queue es no vacío do:
current_node ← vértice de la cola con min distancia al objetivo
remove current_node from queue
 en adelante vecino n de current_node do:
 si n no dentro visitados entonces:
 si n es objetivo:
 retorno n
 más:
marca n como visitado
añadir n a la cola
 retorno fracaso