La ricerca migliore per primo di Greedy è diversa dalla ricerca Best-first?

Question

Una domanda terminologica - la ricerca migliore per prima di Greedy è diversa dalla ricerca Best-first?

Il wiki page ha un paragrafo a parte su BFS Greedy ma è un po 'poco chiaro.

La mia comprensione è che Greedy BFS è solo BFS dove il "nodo migliore da OPEN" nell'algoritmo di wikipedia è una funzione euristica che si calcola per un nodo. Quindi, l'applicazione del presente:

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 "miglior nodo da OPEN" essendo una funzione euristica valutando come chiudere il nodo è quello l'obiettivo, è in realtà Greedy BFS. Ho ragione?

EDIT: Commenta la risposta di Anonymouse:

Quindi, in sostanza un avido BFS non ha bisogno di una "lista aperta" e dovrebbe basare le proprie decisioni solo sul nodo corrente? È questo algoritmo GBFS:

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

"Miglior prima" potrebbe consentire revisione la decisione, mentre in un algoritmo greedy, le decisioni dovrebbero essere definitiva, e non rivisto.

Per esempio A * -search è un best-prima-di ricerca, tuttavia non è avido.

Comprendere che, tuttavia, questi termini non vengono sempre utilizzati con le stesse definizioni. "Greedy" di solito significa che la decisione non viene mai rivista, accettando alla fine soluzioni subottimali a vantaggio dei miglioramenti nel tempo di esecuzione. Tuttavia, scommetto che troverai situazioni in cui "avido" viene utilizzato per la combinazione di "prima il meglio prima + profondità" come in "prova ad espandere il miglior passo successivo finché non raggiungiamo un punto morto, quindi ritorna al passaggio precedente e continua con il prossimo migliore "(che chiamerei prima" profondità prioritaria ").

Inoltre dipende dal livello di astrazione di cui si sta parlando. A * non è avido in "costruire un percorso". Va bene mantenendo una grande serie di percorsi aperti intorno. È comunque avido nell '"espandere lo spazio di ricerca" verso il vero percorso più breve.

Answer 2

E 'la mia comprensione, Best-prima ricerca è soltanto un nome collettivo di una particolare tecnica di ricerca in cui si utilizza una funzione di valutazione euristica h (n). Quindi anche A * e Greedy Best-first Search rientrano in questa categoria.

Per favore correggimi se sbaglio!

Answer 3

BFS è un esempio di albero di ricerca e ricerche grafico algoritmi in cui viene selezionato un nodo per espansione basata su una funzione di valutazione f(n).

Tradizionalmente, il nodo con la valutazione più bassa è selezionato per l'espansione, perché la distanza misure di valutazione alla meta.

BFS utilizza una coda di priorità.

Greedy BFS cerca di espandere il nodo che è più vicino alla meta, per il fatto che, questo cavo alla soluzione rapidamente.Pertanto valuta i nodi semplicemente utilizzando la funzione euristica f(n) = h(n).