Da quello che ho letto finora. Il Best First Search sembra più veloce in termini di trovare il percorso più breve verso l'obiettivo perché l'algoritmo di Dijkstra deve rilassare tutti i nodi mentre attraversa il grafico. Che cosa rende migliore l'algoritmo di Dijkstra rispetto a Best First Search?Perché utilizzare l'algoritmo di Dijkstra anziché la migliore (la più economica) prima ricerca?
EDIT: La modifica chiarisce che ti interessa Best-prima ricerca, e non BFS.
Best-First Search è in realtà un algoritmo informato, che espande per primo il nodo più promettente. Molto simile al ben noto A* algorithm (in realtà A * è uno specifico algoritmo di ricerca best-first).
Dijkstra è un algoritmo non aggiornato - deve essere utilizzato quando non si ha conoscenza del grafico e non è possibile stimare la distanza da ciascun nodo all'obiettivo.
Si noti che A * (che è la ricerca migliore per la prima volta) decade nell'algoritmo di Dijkstra quando si utilizza heuristic functionh(v) = 0 per ogni v.
Inoltre, migliore prima ricerca non è ottimale [non garantiti per trovare il percorso più breve], e anche un *, se non si utilizza un admissible heuristic function, mentre l'algoritmo di Dijkstra è sempre ottimale, in quanto non relè su qualsiasi euristico.
Conclusione: Best-First Search dovrebbe essere preferito su dijkstra quando si ha una certa conoscenza sul grafico, e può stimare una distanza dal bersaglio. In caso contrario, una Best-First Search non informata che utilizza h(v) = 0 e i relè solo sui vertici già esplorati, decadono nell'algoritmo di Dijkstra.
Inoltre, se l'ottimalità è importante - l'algoritmo di Dijkstra si adatta sempre, mentre un algoritmo di ricerca best-first (A * in particolare) può essere utilizzato solo se è disponibile una funzione euristica appropriata.
risposta originale - risponde il motivo per cui ha scelto di Dijkstra oltre BFS:
BFS non riesce quando si tratta di weighted graphs.
Esempio:
A
/ \
1 5
/ \
B----1----C
In qui: w(A,B) = w(B,C) = 1, w(A,C) = 5.
BFS da A restituisce A->C come il percorso più breve, ma per il grafico ponderato, è un percorso di peso 5 !!! mentre il percorso più breve è di peso 2: A->B->C.
L'algoritmo di Dijkstra non farà questo errore e restituirà il percorso ponderato più breve.
Se il grafo è non ponderata - BFS è sia ottimale e completo - e di solito dovrebbe essere preferito su Dijkstra - sia perché è più semplice e veloce (almeno asintoticamente parlando).
Intendevi prima la ricerca in ampiezza, non prima più economica di BFS? –
@ user25464: la tua domanda originale non era chiara (almeno per me), pensavo volessi dire BFS. Guarda la modifica: risponde alla tua domanda? Conservo l'originale anche per i futuri lettori, forse qualcuno lo troverà utile. – amit
dato che la tua risposta originale era in risposta a una modifica "sbagliata" di @dmeister (che dovrebbe imparare a google prima di correggere le domande di altre persone) penso che sarebbe meglio eliminarlo. non è collegato alla domanda e aiuta solo a perpetuare la confusione iniziata dall'errore di dmeister. –
Normalmente Best First Search algoritmi nella ricerca di percorso, alla ricerca di percorso tra due nodi date: Fonte e Sink, ma l'algoritmo di Dijkstra ritrova percorso tra sorgente e tutti gli altri nodi. Quindi non puoi confrontarli. Anche Dijkstra è di tipo Best First Search (variazione di A *) significa che non si può dire che non è la migliore prima ricerca. Anche i normali algoritmi Best First Search utilizzano l'euristica e non sono garanzia di correttezza. Infine, in caso di ponderazione, normalmente il loro tempo di esecuzione dipende dai pesi, ma l'algoritmo di Dijkstra dipende solo dalla dimensione del grafico.
BFS è utile per trovare il percorso più breve dalla sorgente a un vertice nel caso in cui tutti i bordi abbiano lo stesso peso, vale a dire trovare il minimo di spigoli dalla sorgente a un vertice. Mentre Dikjstra vale per i grafici ponderati
Sono abbastanza sicuro che la B in BFS sta per "Larghezza". Ho modificato la domanda di conseguenza. – dmeister
Penso che BFS sia più lento in molti scenari. Quando le prestazioni sono importanti, la precisione può essere ridotta per favorire le prestazioni. –
@dmeister è difficile lasciare un commento e lasciarmi correggere? –