Qualcuno può spiegare in ampiezza prima ricerca?

Question

Qualcuno può spiegare in ampiezza prima ricerca per risolvere il tipo di sotto dei problemi

Ho bisogno di trovare tutti i percorsi tra 4 e 7

Answer 1

Si guarda a tutti i nodi adiacenti al nodo di partenza. Poi si guarda a tutti i nodi adiacenti a quelli (non tornare a nodi che hai già guardato). Ripetere fino a soddisfare nodo trovato o non più nodi.

Per il tipo di problema si indica, si utilizza il processo sopra descritto per costruire una serie di percorsi, che chiude qualsiasi che arriva al nodo di destinazione desiderata, e quando il grafico è esaurita, l'insieme di percorsi che così terminato è il vostro set di soluzioni.

Answer 2

ricerca in ampiezza (BFS) significa che si elabora tutti i figli diretti i nodi di partenza, prima di andare a livelli più profondi. BFS è implementata con una coda che memorizza un elenco di nodi che devono essere elaborati.

Si inizia l'algoritmo aggiungendo il nodo iniziale alla coda. Poi si continua a eseguire l'algoritmo fino ad avere più nulla da elaborare nella coda.

Quando si dequeue un elemento dalla coda, diventa il nodo attivo. Quando si elaborano il nodo attivo, si aggiungono tutti i suoi figli alla parte posteriore della coda. È terminare l'algoritmo quando si dispone di una coda vuota.

Dal momento che si tratta di un grafico al posto di un albero, è necessario memorizzare un elenco dei nodi elaborati in modo da non entrare in un loop.

Una volta raggiunto il nodo 7 si dispone di un percorso di corrispondenza e si può smettere di fare la BFS per quel percorso ricorsivo. Il che significa che semplicemente non aggiungi i suoi figli alla coda. Per evitare i loop e per conoscere il percorso esatto che hai visitato, come fate il vostro ricorsive BFS chiamate, passare in sui nodi già visitati.

Answer 3

Pensate a come siti web con link ad altri siti su di loro. Sia A nostro nodo principale o il nostro sito di partenza.

A is the starting page    (Layer 1)
A links to AA, AB, AC     (Layer 2)
AA links to AAA, AAB, AAC (Layer 3)
AB links to ABA, ABB, ABC (Layer 3)
AC links to ACA, ACB, ACC (Layer 3)

Questo è solo tre strati profondi. Si ricerca uno strato alla volta. Quindi, in questo caso si dovrebbe iniziare a livello di A. Se questo non corrisponde si va al livello successivo, AA, AB e AC. Se nessuno di questi siti web è quello che si sta cercando, allora seguite i link e andare al livello successivo. In altre parole, si guarda a uno strato alla volta.

Una ricerca in profondità (il suo complemento) si dovrebbe andare da A a AA a AAA. In altre parole, si dovrebbe andare in profondità prima di andare WIDE.

Answer 4

Si prova ogni nodo collegato al nodo radice. Poi si prova ogni nodo collegato ai nodi precedenti. Così via, fino a trovare la risposta.

In sostanza, ogni iterazione test nodi che sono alla stessa distanza dal nodo radice.

Answer 5

BEGIN

4;

4,2;

4,2,1; 4,2,3; 4,2,5;

4,2,1; (fail) 4,2,3,6; 4,2,5,6; 4,2,5,11;

4,2,3,6,7, (pass) 4,2,3,6,8; 4,2,5,6,7; (pass) 4,2,5,6,8; 4,2,5,11,12;

4,2,3,6,8,9; 4,2,3,6,8,10; 4,2,5,6,8,9; 4,2,5,6,8,10; 4,2,5,11,12; (fail)

4,2,3,6,8,9; (fail) 4,2,3,6,8,10; (fail) 4,2,5,6,8,9; (fail) 4, 2,5,6,8,10; (fail) |

FINE