Alt hvad du behøver at vide om bredden Første søgningsalgoritme



I denne blog om algoritme om bredde-første søgning vil vi diskutere logikken bag grafens tværgående metoder og forstå, hvordan den fungerer.

Metoder til grafgennemgang har altid ret fascineret mig. Fra at udføre effektiv peer-to-peer-kommunikation til at finde de nærmeste restauranter og caféer ved hjælp af GPS, har traversal-metoder et varieret sæt applikationer i det virkelige scenarie. I denne blog om Breadth-First Search Algorithm vil vi diskutere logikken bag grafens gennemgange og bruge eksempler til at forstå funktionen af ​​Breadth-First Search-algoritmen.

For at få indgående kendskab til kunstig intelligens og maskinindlæring kan du tilmelde dig live af Edureka med support døgnet rundt og adgang til hele livet.





Her er en liste over emner, der vil være dækket af denne blog:

  1. Introduktion til grafgennemgang
  2. Hvad er bredden-første søgning?
  3. Forståelse af algoritmen Breadth-First Search med et eksempel
  4. Bredde-første søgning algoritme Pseudokode
  5. Anvendelser af bredde-første søgning

Introduktion til grafgennemgang

Processen med at besøge og udforske en graf til behandling kaldes graph traversal. For at være mere specifik handler det om at besøge og udforske hvert toppunkt og kant i en graf, så alle hjørnerne udforskes nøjagtigt en gang.



Det lyder simpelt! Men der er en fangst.

hashmap-implementering i java-eksempel

Der er flere grafgennemgangsteknikker såsom bredde-første søgning, dybde første søgning og så videre. Udfordringen er at bruge en graf traversal teknik, der er bedst egnet til at løse et bestemt problem. Dette bringer os til teknikken Breadth-First Search.

Hvad er algoritmen for bredeste søgning?

Breadth-First Search-algoritmen er en grafgennemgangsteknik, hvor du vælger en tilfældig startknude (kilde eller rodknude) og begynder at krydse grafen lagvis på en sådan måde, at alle knudepunkter og deres respektive børneknudepunkter bliver besøgt og udforsket.



Før vi går videre og forstår Breadth-First Search med et eksempel, lad os blive fortrolig med to vigtige udtryk relateret til grafgennemgang:

Grafgennemgang - Algoritme ved første søgning i bredde - Edureka

  1. Besøger en knude: Ligesom navnet antyder, betyder det at besøge en node at besøge eller vælge en node.
  2. Udforskning af en node: Udforskning af tilstødende noder (underknudepunkter) for en valgt node.

Se ovenstående figur for bedre at forstå dette.

Forståelse af bredde-første søgealgoritmen med et eksempel

Breadth-First Search-algoritmen følger en enkel, niveaubaseret tilgang til at løse et problem. Overvej nedenstående binære træ (som er en graf). Vores mål er at krydse grafen ved hjælp af algoritmen Breadth-First Search.

Inden vi kommer i gang, skal du være fortrolig med den vigtigste datastruktur, der er involveret i Breadth-First Search-algoritmen.

En kø er en abstrakt datastruktur, der følger metoden First-In-First-Out (data indsat først får adgang til først). Den er åben i begge ender, hvor den ene ende altid bruges til at indsætte data (enqueue) og den anden bruges til at fjerne data (dequeue).

Lad os nu se på de trin, der er involveret i at krydse en graf ved hjælp af Breadth-First Search:

Trin 1: Tag en tom kø.

Trin 2: Vælg en startknude (besøger en knude), og indsæt den i køen.

Trin 3: Forudsat at køen ikke er tom, skal du udpakke noden fra køen og indsætte dens underknudepunkter (udforske en node) i køen.

Trin 4: Udskriv den udpakkede node.

Bare rolig, hvis du er forvirret, vi vil forstå dette med et eksempel.

Se på nedenstående graf, vi bruger algoritmen Breadth-First Search til at krydse grafen.

I vores tilfælde tildeler vi node 'a' som rodknude og begynder at krydse nedad og følger de ovennævnte trin.

hvor mange reserverede ord i java

Ovenstående billede viser slut-til-slut-processen med bredde-første søgningsalgoritme. Lad mig forklare dette nærmere.

  1. Tildel 'a' som rodknudepunkt og indsæt det i køen.
  2. Uddrag node 'a' fra køen, og indsæt underordnede noder for 'a', dvs. 'b' og 'c'.
  3. Udskriv node 'a'.
  4. Køen er ikke tom og har node 'b' og 'c'. Da 'b' er den første knude i køen, lad os udtrække den og indsætte underknudepunkterne for 'b', dvs. node 'd' og 'e'.
  5. Gentag disse trin, indtil køen bliver tom. Bemærk, at de noder, der allerede er besøgt, ikke skal føjes til køen en gang til.

Lad os nu se på pseudokoden til algoritmen Breadth-First Search.

Bredde-første søgning algoritme Pseudokode

Her er pseudokoden til implementering af algoritmen Breadth-First Search:

Input: s som kildeknudepunkt BFS (G, s) lader Q stå i kø. Q.queque (s) markerer s som besøgt, mens (Q er ikke tom) v = Q.queque () for alle naboer w af v i Graf G, hvis w ikke besøges Q.queque (w) markerer w som besøgt

I ovenstående kode udføres følgende trin:

  1. (G, s) er input, her er G grafen og s er rodnoden
  2. En kø 'Q' oprettes og initialiseres med kildeknudepunktet 's'
  3. Alle underordnede noder på 's' er markeret
  4. Uddrag 's' fra køen og besøg underordnede noder
  5. Behandle alle barnets noder i v
  6. Gemmer w (underknudepunkter) i Q for yderligere at besøge dets underknudepunkter
  7. Fortsæt indtil 'Q' er tom

Før vi afslutter bloggen, skal vi se på nogle applikationer af Breadth-First Search-algoritmen.

Anvendelser af bredde-første søgningsalgoritme

Breadth-first-søgning er en simpel grafgennemgangsmetode, der har et overraskende udvalg af applikationer. Her er et par interessante måder, hvorpå Bread-First-søgning bruges:

Crawlere i søgemaskiner: Bredde-første søgning er en af ​​de vigtigste algoritmer, der bruges til indeksering af websider. Algoritmen begynder at krydse fra kildesiden og følger alle de links, der er knyttet til siden. Her betragtes hver webside som en node i en graf.

GPS-navigationssystemer: Bredde-første søgning er en af ​​de bedste algoritmer, der bruges til at finde nabolande ved hjælp af GPS-systemet.

Find den korteste sti og det mindst spændende træ for en ikke-vægtet graf: Når det kommer til en ikke-vægtet graf, er det ganske simpelt at beregne den korteste sti, da ideen bag den korteste sti er at vælge en sti med mindst antal kanter. Bredde-første søgning kan tillade dette ved at krydse et minimum antal noder startende fra kildeknudepunktet. Til et spændende træ kan vi ligeledes bruge en af ​​de to, Breadth-First Search eller Depth-first traversal metoder til at finde et spændende træ.

Broadcasting: Netværk gør brug af det, vi kalder som pakker til kommunikation. Disse pakker følger en gennemgående metode for at nå forskellige netværksnoder. En af de mest anvendte traversalmetoder er Breadth-First Search. Det bruges som en algoritme, der bruges til at kommunikere udsendte pakker på tværs af alle knudepunkter i et netværk.

hvordan man opretter en logger-fil i java

Peer to Peer-netværk: Bredde-første søgning kan bruges som en gennemkørselsmetode til at finde alle de tilstødende noder i et Peer to Peer-netværk. For eksempel bruger BitTorrent Breadth-First Search for peer to peer-kommunikation.

Så det handlede kun om, hvordan Breadth-First Search-algoritmen fungerer. Nu hvor du ved, hvordan du krydser grafer, er jeg sikker på, at du er nysgerrig efter at lære mere. Her er et par relevante blogs, der holder dig interesseret:

  1. Introduktion til Markov-kæder med eksempler - Markov-kæder med Python

Med dette kommer vi til slutningen af ​​denne blog. Hvis du har spørgsmål vedrørende dette emne, bedes du give en kommentar nedenfor, så vender vi tilbage til dig.

Hvis du ønsker at tilmelde dig et komplet kursus om kunstig intelligens og maskinindlæring, har Edureka en specielt kurateret der gør dig dygtig i teknikker som Supervised Learning, Unsupervised Learning og Natural Language Processing. Det inkluderer træning i de nyeste fremskridt og tekniske tilgange inden for kunstig intelligens og maskinindlæring som dyb læring, grafiske modeller og forstærkningslæring.