La mia comprensione di dijkstra e di Plain-First Search è corretta?

Question

La mia comprensione di dijkstra e di Plain-First Search è corretta?

#1 da (1 voti)

1

Devo aiutare a convalidare se capisco quando usare Dijkstra e quando BFS sono corretti.

Il mio modo di intendere BFS e Dijkstra, quando usare cosa, sono corretto?

Come la vedo io. Dato un grafico, che può essere immaginato come albero N-ary, dove i bordi non hanno un valore speciale (tutti sono della stessa lunghezza) e vogliamo solo passare dal nodo A al nodo B.

Per risolvere questo problema, è possibile utilizzare un BFS
Anche Dijkstra può essere usato, ma sta sprecando memoria, spazio e OP

Tuttavia, viene fornito un grafico, in cui i bordi hanno valori diversi:

Immagina tre nodi: A, B, C. La lunghezza da A a B è 1 La lunghezza da A a B è 5 La lunghezza da A a C è 100 La lunghezza da B a C è 1

Quindi, sì, puoi avere più percorsi dal nodo A al B. Siamo interessati al percorso più breve da A a C.

C'è un metodo NO per risolvere questo problema usando un semplice BFS, ho ragione ...? Devo usare Dijkstra ...

Dal lato dell'implementazione, Dijskstra può essere inteso come BFS, ma con una differenza che stiamo avendo un contenitore BIANCO da cui prendiamo sempre il nodo con il percorso tmp più corto ... (coda di priorità)? Considerando che in BFS normale possiamo usare WHITE una coda o un deque ..? Quindi l'unica differenza di Dijsktra è la coda di priorità ... (e forse alcune piccole cose in algo, ho scritto sia BFS che Dijkstra, non posso richiamare dalla testa)

Riguardo alle complessità, su wiki non ne sono sicuro. Per BFS dovrebbe essere O (a) + O (b)

a = Numero di nodi
b = numero di bordi

Ma c'è anche il backtrack ...? Su wiki è proprio quello che viene mostrato ... quindi è incompleto ...? anche il backtracking fa parte dell'algoritmo ... fondamentale. Posso tornare indietro a n * log (n), n è il numero di elementi che ho salvato durante l'attraversamento ...

Per Dijkstra .... O (a * a) + O (b * b) ...? Perché posso visitarne due volte ...? più O (a) per impostare le distanze di ciascun nodo, più O (n * lungo (n)) per il backtrack ...?

dijkstra

posta Jan Glaser 22.05.2016 - 08:43

fonte

1 risposta

Leggi altre domande sui tag dijkstra

Qual è il modo migliore per unire due stringhe XML con gli stessi nomi di tag? Come mappare la raccolta di numeri grandi univoci su un array?

score 1 · Accepted Answer

Lo hai per lo più corretto, ma:

Si noti che l'algoritmo di Dijkstra è solo un caso speciale di ricerca in ampiezza che fissa nodi prioritari basati su un costo calcolato piuttosto che sull'ordine in cui possono essere raggiunti.
L'unico costo aggiuntivo coinvolto nell'algoritmo di Dijkstra, quindi, è il costo di mantenere la coda di priorità per determinare quale nodo provare prima.
La complessità dell'algoritmo di Dijkstra dipende molto, quindi, dalla struttura dei dati che usi per memorizzare quella coda. C'è una buona coppia di articoli su A * search ( link e link ) che discute le varie strutture di dati che è possibile utilizzare. Nota che la ricerca A * è molto simile all'algoritmo di Dijsktra (usa solo un metodo leggermente diverso per determinare la priorità per quale nodo esaminare prima) e quindi i concetti discussi per A * si applicano anche alle implementazioni dell'algoritmo di Dijsktra.
La somiglianza di A * e il fatto che può funzionare molto meglio dell'algoritmo di Dijkstra per molti scopi significa che potresti voler prendere in considerazione l'uso di quest'ultimo.
Né la ricerca in ampiezza né l'algoritmo di Dijsktra dovrebbero coinvolgere il backtracking, sebbene quest'ultimo possa coinvolgere la riscoperta di un nodo utilizzando un percorso a costo inferiore per raggiungerlo (che non è proprio la stessa cosa) se si hanno margini con costi negativi ( oppure, in A *, se la tua euristica sovrastima i costi effettivi).