Tot ce trebuie să știți despre algoritmul de căutare a lățimii întâi

Metodele Grafic Traversal m-au fascinat întotdeauna destul de mult. De la efectuarea unei comunicări eficiente de la egal la egal la găsirea celor mai apropiate restaurante și cafenele folosind GPS, metodele de traversare au un set variat de aplicații în scenariul din lumea reală. În acest blog despre algoritmul Breadth-First Search, vom discuta despre logica din spatele metodelor de traversare a graficului și vom folosi exemple pentru a înțelege funcționarea algoritmului Breadth-First Search.

Pentru a obține cunoștințe aprofundate despre inteligența artificială și învățarea automată, vă puteți înscrie pentru live de Edureka cu suport 24/7 și acces pe viață.

Iată o listă de subiecte care vor fi acoperit în acest blog:

este greu de învățat

1. Introducere în grafică transversală
2. Ce este căutarea pe lățime?
3. Înțelegerea algoritmului Breadth-First Search cu un exemplu
4. Algoritmul Pseudocodului de Căutare Breadth-First
5. Aplicații de căutare în lățime

Introducere în grafică transversală

Procesul de vizitare și explorare a unui grafic pentru procesare se numește traversare a graficului. Pentru a fi mai specific, este vorba despre vizitarea și explorarea fiecărui vârf și margine într-un grafic, astfel încât toate vârfurile să fie explorate exact o dată.

Sună simplu! Dar există o captură.

Există mai multe tehnici de parcurgere a graficelor, cum ar fi Căutarea lățimii întâi, Căutarea în primul rând a adâncimii și așa mai departe. Provocarea este să folosești un grafic tehnică de traversare care este cea mai potrivită pentru rezolvarea unei anumite probleme. Acest lucru ne aduce la tehnica Breadth-First Search.

Ce este algoritmul de căutare Breadth-First?

Algoritmul Breadth-First Search este o tehnică de parcurgere a graficului, în care selectați un nod inițial aleatoriu (nod sursă sau rădăcină) și începeți să parcurgeți graficul în funcție de nivel, astfel încât toate nodurile și nodurile respective ale copiilor să fie vizitate și explorate.

Înainte de a ne deplasa mai departe și de a înțelege Breadth-First Search cu un exemplu, să ne familiarizăm cu doi termeni importanți legați de traversarea graficului:

1. Vizitarea unui nod: Așa cum sugerează și numele, a vizita un nod înseamnă a vizita sau a selecta un nod.
2. Explorarea unui nod: Explorarea noduri adiacente (noduri copil) ale unui nod selectat.

Consultați figura de mai sus pentru a înțelege mai bine acest lucru.

Înțelegerea algoritmului Breadth-First Search cu un exemplu

Algoritmul Breadth-First Search urmează o abordare simplă, bazată pe nivel, pentru a rezolva o problemă. Luați în considerare arborele binar de mai jos (care este un grafic). Scopul nostru este să parcurgem graficul utilizând algoritmul Breadth-First Search.

Înainte de a începe, trebuie să fiți familiarizați cu structura principală a datelor implicată în algoritmul Breadth-First Search.

O coadă este o structură abstractă de date care urmează metodologia First-In-First-Out (datele introduse mai întâi vor fi accesate mai întâi). Este deschis pe ambele capete, unde un capăt este întotdeauna folosit pentru a insera date (coadă) și celălalt este utilizat pentru a elimina date (coadă).

Acum, să aruncăm o privire asupra pașilor implicați în parcurgerea unui grafic utilizând Căutarea lățimii:

Pasul 1: Luați o coadă goală.

Pasul 2: Selectați un nod de pornire (vizitând un nod) și introduceți-l în coadă.

Pasul 3: Cu condiția ca coada să nu fie goală, extrageți nodul din coadă și introduceți nodurile copilului său (explorând un nod) în coadă.

Pasul 4: Imprimați nodul extras.

Nu vă faceți griji dacă sunteți confuz, vom înțelege acest lucru cu un exemplu.

Uitați-vă la graficul de mai jos, vom folosi algoritmul Breadth-First Search pentru a parcurge graficul.

În cazul nostru, vom atribui nodul „a” ca nod rădăcină și vom începe să traversăm în jos și să urmăm pașii menționați mai sus.

Imaginea de mai sus descrie procesul end-to-end al algoritmului Breadth-First Search. Permiteți-mi să explic acest lucru mai în profunzime.

1. Alocați „a” ca nod rădăcină și introduceți-l în coadă.
2. Extrageți nodul „a” din coadă și introduceți nodurile secundare ale „a”, adică „b” și „c”.
3. Imprimă nodul „a”.
4. Coada nu este goală și are nodurile „b” și „c”. Deoarece „b” este primul nod din coadă, să-l extragem și să introducem nodurile secundare ale „b”, adică nodul „d” și „e”.
5. Repetați acești pași până când coada devine goală. Rețineți că nodurile care sunt deja vizitate nu trebuie adăugate la coadă din nou.

Să vedem acum pseudocodul algoritmului Breadth-First Search.

Algoritmul Pseudocodului de Căutare Breadth-First

Iată pseudocodul pentru implementarea algoritmului Breadth-First Search:

Intrare: s ca nod sursă BFS (G, s) lasă Q să fie coadă. Q.quequeue (s) marchează s ca vizitat în timp ce (Q nu este gol) v = Q.quequeue () pentru toți vecinii w de v în Graficul G dacă w nu este vizitat Q.enqueue (w) marchează w ca vizitat

În codul de mai sus, se execută următorii pași:

1. (G, s) este introdus, aici G este graficul și s este nodul rădăcină
2. O coadă „Q” este creată și inițializată cu nodul sursă „s”
3. Toate nodurile secundare ale „s” sunt marcate
4. Extrageți „s” din coadă și vizitați nodurile copil
5. Procesați toate nodurile copil ale v
6. Stochează w (noduri copil) în Q pentru a-și vizita în continuare nodurile copil
7. Continuați până când apare „Q” gol

Înainte de a încheia blogul, să analizăm câteva aplicații ale algoritmului Breadth-First Search.

Aplicații ale algoritmului de căutare Breadth-First

Breadth-first Search este o metodă simplă de parcurgere a graficului care are o gamă surprinzătoare de aplicații. Iată câteva moduri interesante în care este utilizată Bread-First Search:

Crawlerele din motoarele de căutare: Breadth-First Search este unul dintre principalii algoritmi utilizați pentru indexarea paginilor web. Algoritmul începe să treacă de la pagina sursă și urmează toate linkurile asociate paginii. Aici fiecare pagină web va fi considerată ca un nod într-un grafic.

Sisteme de navigare GPS: Breadth-First Search este unul dintre cei mai buni algoritmi utilizați pentru a găsi locații învecinate utilizând sistemul GPS.

Găsiți cea mai scurtă cale și arborele minim de întindere pentru un grafic neponderat: Când vine vorba de un grafic neponderat, calcularea celei mai scurte căi este destul de simplă, deoarece ideea din spatele celei mai scurte căi este de a alege o cale cu cel mai mic număr de muchii. Breadth-First Search poate permite acest lucru prin parcurgerea unui număr minim de noduri începând de la nodul sursă. În mod similar, pentru un arbore care se întinde, putem folosi oricare dintre cele două metode, Breadth-First Search sau Depth-first traversal, pentru a găsi un arbore care se întinde.

numai valorile matricei de imprimare php

Difuzare: Rețeaua folosește ceea ce numim pachete pentru comunicare. Aceste pachete urmează o metodă de traversare pentru a ajunge la diferite noduri de rețea. Una dintre cele mai utilizate metode de traversare este Breadth-First Search. Este folosit ca un algoritm care este utilizat pentru a comunica pachete difuzate pe toate nodurile dintr-o rețea.

Rețea de la egal la egal: Breadth-First Search poate fi folosită ca metodă de traversare pentru a găsi toate nodurile învecinate într-o rețea Peer to Peer. De exemplu, BitTorrent folosește Breadth-First Search pentru comunicare de la egal la egal.

Deci, asta a fost totul despre funcționarea algoritmului Breadth-First Search. Acum, că știi cum să parcurgi grafice, sunt sigur că ești curios să afli mai multe. Iată câteva bloguri relevante pentru a vă menține interesat:

3. Introducere în lanțurile Markov cu exemple - Lanțuri Markov cu Python

Cu aceasta, ajungem la sfârșitul acestui blog. Dacă aveți întrebări cu privire la acest subiect, vă rugăm să lăsați un comentariu mai jos și vă vom răspunde.

Dacă doriți să vă înscrieți la un curs complet de inteligență artificială și învățare automată, Edureka are un curs special care vă va face să faceți cunoștințe în tehnici precum învățarea supravegheată, învățarea nesupravegheată și procesarea limbajului natural. Acesta include instruire cu privire la cele mai noi progrese și abordări tehnice în inteligența artificială și învățarea automată, cum ar fi învățarea profundă, modelele grafice și învățarea prin întărire.