I metodi di Graph Traversal mi hanno sempre affascinato. Dall'esecuzione di una comunicazione peer to peer efficace alla ricerca dei ristoranti e dei bar più vicini utilizzando il GPS, i metodi di attraversamento hanno una serie varia di applicazioni nello scenario del mondo reale. In questo blog sull'algoritmo di ricerca Breadth-First, discuteremo la logica alla base dei metodi di attraversamento dei grafi e utilizzeremo esempi per comprendere il funzionamento dell'algoritmo di ricerca Breadth-First.
Per avere una conoscenza approfondita dell'Intelligenza Artificiale e del Machine Learning, puoi iscriverti al live di Edureka con supporto 24 ore su 24, 7 giorni su 7 e accesso a vita.
Ecco un elenco di argomenti che saranno trattato in questo blog:
- Introduzione al Graph Traversal
- Cos'è la ricerca Breadth-First?
- Comprensione dell'algoritmo di ricerca Breadth-First con un esempio
- Pseudocodice dell'algoritmo di ricerca in ampiezza
- Applicazioni di ricerca in ampiezza
Introduzione al Graph Traversal
Il processo di visita ed esplorazione di un grafico per l'elaborazione è chiamato attraversamento del grafico. Per essere più specifici, si tratta di visitare ed esplorare ogni vertice e bordo in un grafo in modo che tutti i vertici vengano esplorati esattamente una volta.
Sembra semplice! Ma c'è un problema.
Esistono diverse tecniche di attraversamento del grafico come la ricerca in larghezza, la ricerca in profondità e così via. La sfida è usare un grafico tecnica di attraversamento più adatta per risolvere un particolare problema. Questo ci porta alla tecnica di ricerca in base alla larghezza.
Cos'è l'algoritmo di ricerca Breadth-First?
L'algoritmo di ricerca Breadth-First è una tecnica di attraversamento del grafico, in cui si seleziona un nodo iniziale casuale (nodo di origine o radice) e si inizia ad attraversare il grafico a livello di livello in modo tale che tutti i nodi ei rispettivi nodi figli vengano visitati ed esplorati.
Prima di andare oltre e comprendere la ricerca Breadth-First con un esempio, familiarizziamo con due termini importanti relativi all'attraversamento del grafico:
- Visitare un nodo: Proprio come suggerisce il nome, visitare un nodo significa visitare o selezionare un nodo.
- Esplorare un nodo: Esplorando il nodi adiacenti (nodi figlio) di un nodo selezionato.
Fare riferimento alla figura sopra per capire meglio questo.
Comprensione dell'algoritmo di ricerca in base alla larghezza con un esempio
L'algoritmo di Breadth-First Search segue un semplice approccio basato sul livello per risolvere un problema. Considera l'albero binario sottostante (che è un grafico). Il nostro obiettivo è attraversare il grafico utilizzando l'algoritmo di ricerca Breadth-First.
Prima di iniziare, devi avere familiarità con la struttura dati principale coinvolta nell'algoritmo di ricerca Breadth-First.
Una coda è una struttura dati astratta che segue la metodologia First-In-First-Out (si accederà prima ai dati inseriti per primi). È aperto su entrambe le estremità, dove un'estremità viene sempre utilizzata per inserire dati (accodamento) e l'altra viene utilizzata per rimuovere dati (dequeue).
Ora diamo uno sguardo ai passaggi coinvolti nell'attraversare un grafico utilizzando la ricerca Breadth-First:
Passo 1: Prendi una coda vuota.
Passo 2: Seleziona un nodo di partenza (visitando un nodo) e inseriscilo nella coda.
Passaggio 3: A condizione che la coda non sia vuota, estrai il nodo dalla coda e inserisci i suoi nodi figli (esplorando un nodo) nella coda.
Passaggio 4: Stampa il nodo estratto.
Non preoccuparti se sei confuso, lo capiremo con un esempio.
Dai un'occhiata al grafico sottostante, useremo l'algoritmo di ricerca Breadth-First per attraversare il grafico.
Nel nostro caso, assegneremo il nodo 'a' come nodo radice e inizieremo ad attraversare verso il basso e seguire i passaggi sopra menzionati.
L'immagine sopra mostra il processo end-to-end dell'algoritmo di ricerca Breadth-First. Lasciatemi spiegare questo in modo più approfondito.
- Assegna 'a' come nodo principale e inseriscilo nella coda.
- Estrai il nodo 'a' dalla coda e inserisci i nodi figlio di 'a', ovvero 'b' e 'c'.
- Stampa il nodo 'a'.
- La coda non è vuota e ha i nodi 'b' e 'c'. Poiché 'b' è il primo nodo della coda, estraiamolo e inseriamo i nodi figli di 'b', ovvero il nodo 'd' ed 'e'.
- Ripeti questi passaggi finché la coda non si svuota. Notare che i nodi già visitati non devono essere aggiunti alla coda ancora.
Ora diamo un'occhiata allo pseudocodice dell'algoritmo di ricerca Breadth-First.
Pseudocodice dell'algoritmo di ricerca in ampiezza
Ecco lo pseudocodice per implementare l'algoritmo di ricerca Breadth-First:
Input: s come nodo di origine BFS (G, s) lascia che Q sia in coda. Q.enqueue contrassegna s come visitato mentre (Q non è vuoto) v = Q.dequeue () per tutti i vicini w di v nel grafico G se w non è visitato Q.enqueue (w) contrassegna w come visitato
Nel codice sopra, vengono eseguiti i seguenti passaggi:
- (G, s) è l'input, qui G è il grafico es è il nodo radice
- Una coda 'Q' viene creata e inizializzata con il nodo di origine 's'
- Tutti i nodi figlio di 's' sono contrassegnati
- Estrai 's' dalla coda e visita i nodi secondari
- Elabora tutti i nodi figlio di v
- Memorizza w (nodi figlio) in Q per visitare ulteriormente i suoi nodi figlio
- Continua fino a 'Q' vuoto
Prima di concludere il blog, diamo un'occhiata ad alcune applicazioni dell'algoritmo di ricerca Breadth-First.
Applicazioni dell'algoritmo di ricerca in ampiezza
La ricerca in ampiezza è un semplice metodo di attraversamento del grafico che ha una sorprendente gamma di applicazioni. Ecco alcuni modi interessanti in cui viene utilizzata la ricerca Bread-First:
Crawler nei motori di ricerca: Breadth-First Search è uno dei principali algoritmi utilizzati per l'indicizzazione delle pagine web. L'algoritmo inizia ad attraversare dalla pagina di origine e segue tutti i link associati alla pagina. Qui ogni pagina web sarà considerata come un nodo in un grafico.
Sistemi di navigazione GPS: Breadth-First Search è uno dei migliori algoritmi utilizzati per trovare posizioni vicine utilizzando il sistema GPS.
Trova il percorso più breve e l'albero di copertura minimo per un grafico non ponderato: Quando si tratta di un grafico non ponderato, calcolare il percorso più breve è abbastanza semplice poiché l'idea dietro il percorso più breve è di scegliere un percorso con il minor numero di bordi. La ricerca Breadth-First può consentire ciò attraversando un numero minimo di nodi a partire dal nodo di origine. Allo stesso modo, per uno spanning tree, possiamo usare uno dei due metodi, Breadth-First Search o Depth-first traversal per trovare uno spanning tree.
come creare un elenco collegato in c
Trasmissione: Il networking fa uso di ciò che chiamiamo pacchetti per la comunicazione. Questi pacchetti seguono un metodo di attraversamento per raggiungere vari nodi di rete. Uno dei metodi di attraversamento più comunemente usati è la ricerca in base all'ampiezza. Viene utilizzato come algoritmo utilizzato per comunicare i pacchetti trasmessi attraverso tutti i nodi di una rete.
Rete peer to peer: La ricerca Breadth-First può essere utilizzata come metodo di attraversamento per trovare tutti i nodi vicini in una rete peer to peer. Ad esempio, BitTorrent utilizza la ricerca Breadth-First per la comunicazione peer to peer.
Quindi era tutta una questione di funzionamento dell'algoritmo di ricerca Breadth-First. Ora che sai come attraversare i grafici, sono sicuro che sei curioso di saperne di più. Ecco alcuni blog rilevanti per mantenerti interessato:
Con questo, arriviamo alla fine di questo blog. Se hai domande su questo argomento, lascia un commento qui sotto e ti ricontatteremo.
Se desideri iscriverti a un corso completo su Intelligenza Artificiale e Machine Learning, Edureka ha un che ti renderà esperto in tecniche come l'apprendimento supervisionato, l'apprendimento non supervisionato e l'elaborazione del linguaggio naturale. Include la formazione sugli ultimi progressi e approcci tecnici in Intelligenza Artificiale e Machine Learning come Deep Learning, Modelli grafici e Reinforcement Learning.