¿La primera búsqueda de Greedy es diferente de la búsqueda de la mejor primera?

Question

Una pregunta terminológica: ¿es Greedy best-first search diferente de Best-first search?

El wiki page tiene un párrafo aparte sobre Greedy BFS pero no está nada claro.

Mi comprensión es que Greedy BFS es solo BFS, donde el "mejor nodo de OPEN" en el algoritmo de la wikipedia es una función heurística que se calcula para un nodo. Por lo tanto la aplicación de esta:

OPEN = [initial state] 
CLOSED = [] 
while OPEN is not empty 
do 
1. Remove the best node from OPEN, call it n, add it to CLOSED. 
2. If n is the goal state, backtrace path to n (through recorded parents) and return path. 
3. Create n's successors. 
4. For each successor do: 
    a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent. 
    b. Otherwise: change recorded parent if this new path is better than previous one. 
done 

con "mejor nodo de ABIERTO" es una función heurística estimar qué tan cerca el nodo es el objetivo, es en realidad Greedy BFS. ¿Estoy en lo cierto?

EDIT: comentario sobre la respuesta de Anonymouse:

Así que, esencialmente un codicioso BFS no necesita una "lista abierta" y deben basar sus decisiones únicamente en el nodo actual? Es esta EAHG algoritmo:

1. Set START as CURRENT node 
2. Add CURRENT to Path [and optinally, to CLOSED?] 
3. If CURRENT is GOAL, exit 
4. Evaluate CURRENT's successors 
5. Set BEST successor as CURRENT and go to 2. 

Answer 1

"Mejor primera" podría permitir la revisión de la decisión, mientras que en un algoritmo voraz, las decisiones deben ser definitivas y no revisada.

Por ejemplo, A * -search es la mejor primera búsqueda, sin embargo no es codicioso.

Comprenda que, sin embargo, estos términos no siempre se usan con las mismas definiciones. "Codicioso" generalmente significa que la decisión nunca se revisa, y finalmente acepta soluciones que no son óptimas en beneficio de las mejoras en el tiempo de ejecución. Sin embargo, apuesto a que encontrarás situaciones donde "codicioso" se usa para la combinación de "mejor primero + profundidad primero" que en "intenta expandir el siguiente paso hasta llegar a un callejón sin salida, luego regresa al paso anterior y continúa con el siguiente mejor allí "(que yo llamaría una" profundidad priorizada primero ").

También depende del nivel de abstracción del que está hablando. A * no es codicioso en '' construir un camino ''. Está bien mantener un amplio conjunto de caminos abiertos. Sin embargo, es codicioso en "expandir el espacio de búsqueda" hacia el verdadero camino más corto.

Answer 2

Tengo entendido que Best-first Search es solo un nombre colectivo de una técnica de búsqueda particular en la que utiliza una función de evaluación heurística h (n). Así que A * y Greedy Best-first Search también entran en esta categoría.

¡Corríjame si me equivoco!

Answer 3

BFS es una instancia de árbol de búsqueda y búsqueda gráfica algoritmos en el que se selecciona un nodo de expansión basado en una función de evaluación f(n).

Tradicionalmente, el nodo con la evaluación más baja se selecciona para la expansión, porque la evaluación mide la distancia al objetivo.

BFS utiliza una cola de prioridad.

Greedy BFS intenta expandir el nodo que está más cerca de la meta, sobre la base de que esto conduce a la solución rápidamente.Por lo tanto, evalúa los nodos simplemente usando la función heurística f(n) = h(n).