Qual è breadth-first ricerca utile per?

Question

Di solito, quando ho dovuto camminare un grafico, ho sempre usato ricerca in profondità a causa dello spazio minore complessità. Non ho onestamente mai visto una situazione che richiede una ricerca in ampiezza, anche se la mia esperienza è piuttosto limitata.

Quando ha senso utilizzare una ricerca in ampiezza?

Aggiorna : Suppongo che la mia risposta qui mostra una situazione in cui ho usato un BFS (perché ho pensato che era un DFS). Sono ancora curioso di sapere, però, perché è stato utile in questo caso.

Answer 1

Quando si vuole raggiungere un nodo attraversando il minor numero possibile di bordi, vale a dire quando si vuole trovare il percorso più breve in un grafo non ponderata.

Anche la complessità spazio di una ricerca in profondità può essere superiore a quella di una ricerca in ampiezza quando ad esempio ogni nodo ha un solo nodo figlio, cioè quando il grafico è profondo ma non molto ampio.

Answer 2

Se il dominio di ricerca è infinito, in profondità-ricerca non garantisce di interrompere / trovare una soluzione, anche se una soluzione esiste finita.

Inoltre è possibile vedere gli algoritmi più elaborati come A * di essere un sottotipo speciale di breadth-first-ricerca.

In generale, bfs è sia ottimale e completa (con fattore di ramificazione finita) mentre DFS non è.

Answer 3

Potrebbe essere usato per risolvere un problema di ricerca con il numero minimo di passi. Andando a fondo prima potrebbe portare (se non limitato in qualche modo) a profondità infinita.

Es.: Trovare il nodo più vicino alla radice che soddisfa una condizione

Answer 4

Nessuno ha ancora parlato di un fattore chiave nei casi in cui ricerca in ampiezza è utile: la visita di un modo un nodo può eliminare l'obbligo di visitare il nodo di qualche altro modo. In alcuni casi, ci si finisce per fare lo stesso lavoro indipendentemente dall'ordine in cui vengono visitati i nodi, ma BFS avranno molte meno azioni in attesa in un momento di DFS. In altri casi, visitando i nodi in una sequenza può richiedere più lavoro di altri; vari algoritmi dei cammini sono fornite come esempio. Se la visita di un nodo richiede visitando i suoi vicini di casa a meno che il nodo è noto per essere raggiungibile con un percorso più breve rispetto a quello attuale, visitando i nodi in ordine breadth-first tipicamente tradurrà in nodi viene assegnato il percorso più breve - o qualcosa di simile a da- -sulla loro prima visita. Al contrario, una ricerca in profondità potrebbe causare molti nodi da visitare con percorsi molto lunghi la prima volta, poi da percorsi leggermente più brevi, percorsi poi un po 'più brevi, ecc richiedono un importo complessivo veramente mostruosa di lavoro.

A proposito, un'illustrazione grafica bella della differenza tra gli algoritmi di profondità-prima e in largo, in primo luogo è un riempimento alluvione zona, dove un nodo bianca è flood-riempita dipingendo di nero e inondazioni che riempiono i suoi vicini. Se si cerca di inondazioni riempire un'area quadrata NxN di partenza in un cornder, un'operazione in profondità riempirebbe piazza in una spirale oa zig-zag sequenza, con operazioni NxN-1 rimanente nella pila. Un riempimento ampiezza sarebbe "pour" fuori dal punto di partenza, e contenere al massimo le operazioni di O (N) in attesa, indipendentemente dalla forma da riempire. A proposito, il riempimento delle inondazioni in IBM BASICA ha lavorato in questo modo (non sono sicuro circa QBASIC).

Answer 5

Un esempio sta attraversando il file system (profondità ricorsiva limitata).

Secondo wikipedia , è utile anche per alcuni algoritmi grafico (bipartiteness, collegato componenti).

Answer 6

  

Quando ha senso utilizzare una ricerca in ampiezza?

Ad esempio, quando si ha bisogno di trovare il percorso più breve in un grafico - DFS solo non può farlo. Ci sono alcune altre applicazioni, ma, in generale, DFS e BFS sono lo stesso algoritmo a lavorare su diverse strutture di dati (BFS utilizza coda e DFS funziona con stack).

Answer 7

Quando è necessario per ottenere il percorso più breve per un vertice da un grafico con nessun peso bordo.

Answer 8

Nella ricerca in profondità si possono trovare soluzioni "locali" -. Per trovare davvero una soluzione globale è necessario attraversare l'intero grafico (o utilizzare un euristica)

Answer 9

BFS a volte è veramente utile. Supponiamo di avere un albero che rappresenta diciamo WBS. Si consiglia di presentare al vostro utente solo 1 livello di esso.

Answer 10

Larghezza-primo algoritmo di ricerca ama stare il più vicino possibile al punto di partenza. Alcune delle situazioni che mi vengono in mente sono:

siti web
1. Social networking puoi usarlo anche per trovare le persone in distanza specificata.
2. Può essere utile in torrenting / peer-to-peer per cercare computer vicina.
sistemi
3. navigazione GPS possono utilizzare per trovare luoghi vicini.