Ho studiato gli algoritmi di attraversamento di due grafici, ricerca di profondità prima e ricerca di ampiezza. Da entrambi gli algoritmi si usa lo stesso problema di attraversamento di grafici che vorrei conoscere come scegliere tra i due. Voglio dire è uno più efficiente rispetto agli altri o qualsiasi motivo per scegliere l'uno sull'altro in uno scenario particolare?Vantaggio di profondità prima ricerca su larghezza prima ricerca o viceversa
Grazie
La principale differenza per me è in qualche modo teorica. Se avessi un grafico di dimensioni infinite, DFS non troverà mai un elemento se esiste al di fuori del primo percorso che sceglie. Continuerebbe essenzialmente a scendere il primo percorso e non troverebbe mai l'elemento. Il BFS alla fine troverebbe l'elemento.
Se la dimensione del grafico è finita, è probabile che DFS trovi più velocemente un elemento anomalo (distanza maggiore tra root e obiettivo) in cui BFS troverà un elemento più vicino più velocemente. Tranne nel caso in cui DFS sceglie il percorso dell'elemento superficiale.
Questa non è una cattiva risposta, ma DFS e BFS possono entrambi fallire nel caso infinito - DFS può fallire se un grafico è infinitamente profondo, mentre BFS può funzionare. Tuttavia, DFS funzionerà se il grafico non è infinitamente profondo, ma infinitamente * ampio * - mentre BFS fallirà. Attraversare grafici infiniti (da quello che capisco) è molto diverso dal percorrere grafici finiti. –
In generale, BFS è migliore per i problemi relativi alla ricerca dei percorsi più brevi o di problemi in qualche modo correlati. Perché qui si passa da un nodo a tutti i nodi adiacenti ad esso e quindi si sposta in modo efficace dalla lunghezza del percorso uno alla lunghezza del percorso due e così via.
Mentre DFS all'altra estremità aiuta di più nei problemi di connettività e anche nel trovare cicli nel grafico (anche se penso che potresti essere in grado di trovare cicli con un po 'di modifica di BFS). Determinare la connettività con DFS è banale, se si chiama la procedura di esplorazione due volte dalla procedura DFS, il grafico viene disconnesso (questo è per un grafico non orientato). Qui puoi vedere l'algoritmo di componente fortemente connesso per un grafico diretto, che è una modifica di DFS. Un'altra applicazione del DFS è l'ordinamento topologico.
Queste sono alcune applicazioni di entrambi gli algoritmi:
DFS:
connettività
componenti fortemente connesse
topologico Ordinamento
UST:
Shortest Path (Dijkstra è qualche cosa di una modifica di BFS).
Verificare se il grafico è Bipartitie.
Per un albero completo/perfetto, DFS occupa una quantità di spazio lineare rispetto alla profondità dell'albero mentre BFS occupa una quantità di spazio esponenziale rispetto alla profondità dell'albero. Questo perché per BFS il numero massimo di nodi nella coda è proporzionale al numero di nodi in un livello dell'albero. In DFS il numero massimo di nodi nello stack è proporzionale alla profondità dell'albero.
Quando si attraversa un grafico a più fili, l'ordine in cui i nodi sono attraversati può influenzare notevolmente (di molti ordini di grandezza) il numero di nodi da tracciare con il metodo di movimento. Alcuni tipi di algoritmi saranno enormemente migliori quando si usa l'ampiezza; altri saranno massicciamente migliori quando si utilizza la ricerca di profondità.
A un estremo, eseguire una ricerca in profondità su un albero binario con nodi foglia N richiede che il metodo di movimento tenga traccia dei nodi lgN mentre una ricerca in larghezza richiederebbe di tenere traccia di almeno N/2 nodi (poiché potrebbe eseguire la scansione di tutti gli altri nodi prima di eseguire la scansione di eventuali nodi foglia, immediatamente prima della scansione del primo nodo foglia, avrebbe rilevato N/2 dei nodi padre delle foglie che devono essere monitorati separatamente poiché nessuno di essi fa riferimento l'un l'altro) .
All'estremo opposto, si esegue un riempimento in una griglia NxN con un metodo che, se il pixel non è ancora stato colorato, i colori che pixel e quindi riempiono il suo vicino richiederanno di accodare O (N) le coordinate dei pixel se si utilizza la ricerca in ampiezza, ma le coordinate dei pixel O (N^2) se si utilizza depth-first. Quando si utilizza la ricerca in ampiezza, la vernice sembrerà "distesa", indipendentemente dalla forma da dipingere; quando si utilizza l'algoritmo depth-first per dipingere una spirale rettangolare, ogni linea di cui è diritta su un lato e seghettata sull'altro (quali lati dovrebbero essere dritti e frastagliati dipende dall'algoritmo esatto utilizzato), tutte le sezioni diritte verranno dipinte prima di qualsiasi di quelle frastagliate, il che significa che il sistema deve tracciare separatamente la posizione di ogni jag.
In alcune lingue, un BFS è una scelta leggermente migliore perché la più semplice implementazione di DFS è ricorsiva, che introduce un overhead, e anche potrebbe causare il codice per colpire il limite di dimensione dello stack per grandi grafici. Il vantaggio evidente (e applicazione) di BFS è che nei grafici non ponderati può essere utilizzato per costruire un cammino minimo da u a v Questa ha numerose applicazioni -. Per esempio, è possibile calcolare il minor numero di mosse necessario per risolvere un dato problema eseguendo un BFS sul suo spazio di stato. BFS può anche darti le distanze più corte da un vertice u a tutti gli altri vertici nel grafico: per ogni vertice , ricorda solo il bordo che era stato usato per scoprilo.
vedere http://stackoverflow.com/questions/687731/breadth-first-vs-depth-first ... contiene alcune informazioni e collegamenti utili, tra cui 3 blog parte collegati a una delle ultime due risposte. – hatchet
Grazie per aver condiviso questo. Sembra davvero utile. In realtà, capisco come funzionano entrambi gli algoritmi, voglio solo sapere perché ne abbiamo bisogno di due :) – Kris
simile a http://stackoverflow.com/questions/1657174/what- is-breadth-first-search-useful-for – hatchet