Kaikki mitä sinun tarvitsee tietää leveyden ensimmäisen haun algoritmista



Tässä Breadth-First Search Algorithm -blogissa keskustelemme kaavion kulkumenetelmien logiikasta ja ymmärrämme niiden toiminnan.

Kaavioiden läpimenomenetelmät ovat aina kiehtoneet minua. Tehokkaasta vertaisviestinnästä vertaisviestintään ja lähimpien ravintoloiden ja kahviloiden löytämiseen GPS: n avulla, läpimenomenetelmillä on erilaisia ​​sovelluksia reaalimaailmassa. Tässä Breadth-First Search Algorithm -blogissa keskustelemme graafin läpimenomenetelmien logiikasta ja käytämme esimerkkejä ymmärtämään Breadth-First Search -algoritmin toimintaa.

Saadaksesi syvällisen tiedon tekoälystä ja koneoppimisesta, voit ilmoittautua livenä kirjoittanut Edureka 24/7 tuella ja käyttöikällä.





Tässä on luettelo aiheista käsitelty tässä blogissa:

  1. Johdanto kaavion läpikäyntiin
  2. Mikä on leveys-ensimmäinen haku?
  3. Laajan ensimmäisen haun algoritmin ymmärtäminen esimerkillä
  4. Leveys-ensimmäisen hakualgoritmin pseudokoodi
  5. Leveys - ensimmäinen haku -sovellukset

Johdanto kaavion läpikäyntiin

Kuvaajan vierailua ja tutkintaa prosessointia varten kutsutaan kuvaajan läpikäymiseksi. Tarkemmin sanottuna on kyse kunkin kärjen ja reunan vierailemisesta ja tutkimisesta kaaviossa siten, että kaikki pisteet tutkitaan tarkalleen kerran.



Se kuulostaa yksinkertaiselta! Mutta on saalis.

Kaavioiden läpikäyntitekniikoita on useita, kuten Leveys ensin -haku, Syvyys ensimmäinen haku ja niin edelleen. Haasteena on käyttää kuvaajaa kulkutekniikka, joka soveltuu parhaiten tietyn ongelman ratkaisemiseen. Tämä tuo meidät Breadth-First Search -tekniikkaan.

Mikä on leveyden ensimmäinen haku -algoritmi?

Leveys - ensimmäinen haku -algoritmi on kaavion kulkutekniikka, jossa valitset satunnaisen alkusolmun (lähde- tai juurisolmu) ja aloitat kaavion kulkemisen kerroksittain siten, että kaikki solmut ja niiden vastaavat lapsisolmut vierailevat ja tutkitaan.



Ennen kuin siirrymme eteenpäin ja ymmärrämme esimerkin Laajuus-Ensimmäinen-hausta, tutustutaan kahteen tärkeään graafin kulkemiseen liittyvään termiin:

Kaavion läpikäynti - Leveyden ensimmäisen haun algoritmi - Edureka

  1. Solmun vierailu: Aivan kuten nimestä voi päätellä, solmun vierailu tarkoittaa solmun vierailua tai valitsemista.
  2. Solmun tutkiminen: Tutki valitun solmun vierekkäiset solmut (lapsisolmut).

Katso yllä olevaa kuvaa ymmärtääksesi tämän paremmin.

Laajuuden ensimmäisen haun algoritmin ymmärtäminen esimerkillä

Leveys-Ensimmäinen haku -algoritmi noudattaa yksinkertaista, tasopohjaista lähestymistapaa ongelman ratkaisemiseen. Harkitse alla olevaa binääripuuta (joka on kaavio). Tavoitteenamme on kulkea kuvaajan läpi Leveys-Ensimmäinen haku -algoritmilla.

Ennen kuin aloitamme, sinun on oltava perehtynyt Breadth-First Search -algoritmiin liittyvään päätietorakenteeseen.

Jono on abstrakti tietorakenne, joka noudattaa First-In-First-Out -menetelmää (ensin syötettyihin tietoihin pääsee ensin). Se on avoin molemmista päistä, missä toista päätä käytetään aina tietojen lisäämiseen (enqueue) ja toista käytetään tietojen poistamiseen (dequeue).

Tarkastellaan nyt kaavion kulkemisen vaiheita käyttämällä Leveys-Ensimmäinen-hakua:

Vaihe 1: Ota tyhjä jono.

Vaihe 2: Valitse aloitussolmu (käymällä solmussa) ja lisää se jonoon.

Vaihe 3: Jos jono ei ole tyhjä, pura solmu jonosta ja aseta sen alisolmut (tutkia solmu) jonoon.

pl sql -opetusohjelma, jossa on esimerkkejä

Vaihe 4: Tulosta purettu solmu.

Älä huoli, jos olet hämmentynyt, ymmärrämme tämän esimerkillä.

Katsokaa alla olevaa kaaviota, käytämme Breadth-First Search -algoritmia siirtymiseen kaavion läpi.

Meidän tapauksessamme määritämme solmun 'a' juurisolmuksi ja aloitamme kulkemisen alaspäin ja noudata yllä mainittuja vaiheita.

Yllä oleva kuva kuvaa Breadth-First Search -algoritmin koko prosessin. Sallikaa minun selittää tämä perusteellisemmin.

  1. Määritä ”a” juurisolmuksi ja lisää se jonoon.
  2. Pura solmu ”a” jonosta ja aseta ”a”, eli ”b” ja ”c”, alisolmut.
  3. Tulosta solmu 'a'.
  4. Jono ei ole tyhjä, ja siinä on solmut 'b' ja 'c'. Koska 'b' on jonon ensimmäinen solmu, puretaan se ja lisätään 'b': n alisolmut, eli solmu 'd' ja 'e'.
  5. Toista näitä vaiheita, kunnes jono tyhjenee. Huomaa, että jo käyneitä solmuja ei pitäisi lisätä jonoon uudelleen.

Tarkastellaan nyt Breadth-First Search -algoritmin pseudokoodia.

Leveys-ensimmäisen hakualgoritmin pseudokoodi

Tässä on pseudokoodi Breadth-First Search -algoritmin toteuttamiseksi:

Tulo: lähdekoodina BFS (G, s) antavat Q: n olla jonossa. Q.enqueue (s) -merkinnät käydyiksi, kun (Q ei ole tyhjä) v = Q.dequeue () kaikille naapureille w of v kaaviossa G, jos w ei käy Q.enqueue (w) -merkki w vierailuna

Yllä olevassa koodissa suoritetaan seuraavat vaiheet:

  1. (G, s) syötetään, tässä G on käyrä ja s on juurisolmu
  2. Jono 'Q' luodaan ja alustetaan lähdesolmulla 's'
  3. Kaikki s: n lapsisolmut on merkitty
  4. Pura ”s” jonosta ja vieraile lapsisolmuissa
  5. Käsittele kaikki v: n lapsisolmut
  6. Tallentaa w (lapsisolmut) Q: ssa vieraillakseen edelleen lapsisolmuissaan
  7. Jatka kunnes Q on tyhjä

Ennen blogin päättämistä tarkastellaan joitain Breadth-First Search -algoritmin sovelluksia.

Leveysasteisen haun algoritmin sovellukset

Leveys ensin -haku on yksinkertainen kaavion läpimenomenetelmä, jolla on yllättävä valikoima sovelluksia. Tässä on muutama mielenkiintoinen tapa käyttää Leipää ensin -hakua:

Indeksoijat hakukoneissa: Leveys-Ensimmäinen haku on yksi tärkeimmistä algoritmeista, joita käytetään verkkosivujen indeksointiin. Algoritmi alkaa kulkea lähdesivulta ja seuraa kaikkia sivuun liittyviä linkkejä. Tässä jokaista verkkosivua pidetään solmuna kaaviossa.

GPS-navigointijärjestelmät: Leveys-ensimmäinen haku on yksi parhaista algoritmeista, joita käytetään naapurimaiden etsimiseen GPS-järjestelmän avulla.

Löydä lyhin polku ja vähimmäispinta-ala painottamattomalle kuvaajalle: Painottamattoman kuvaajan osalta lyhimmän polun laskeminen on melko yksinkertaista, koska lyhimmän polun idea on valita polku, jolla on vähiten reunoja. Leveys - ensimmäinen haku voi sallia tämän kulkemalla vähimmäismäärä solmuja lähdesolmusta alkaen. Vastaavasti kattavaan puuhun voimme käyttää jompaa kumpaa, Leveys ensin -haku tai syvyys-ensimmäinen-läpimenomenetelmiä, etsimään kattava puu.

Lähetys: Verkostoituminen käyttää sitä, mitä kutsumme viestinnän paketeiksi. Nämä paketit seuraavat läpimenomenetelmää saavuttaakseen erilaiset verkkosolmut. Yksi yleisimmin käytetyistä läpimenomenetelmistä on Breadth-First Search. Sitä käytetään algoritmina, jota käytetään lähetettyjen pakettien kommunikointiin verkon kaikkien solmujen välillä.

Vertaisverkko: Leveys-ensimmäistä hakua voidaan käyttää läpimenomenetelmänä kaikkien naapurisolmujen löytämiseksi vertaisverkosta. Esimerkiksi BitTorrent käyttää vertaisviestintää Breadth-First Search -toiminnolla.

Joten kyse oli Breadth-First Search -algoritmin toiminnasta. Nyt kun tiedät kuinka kaaviot kulkevat, olet varma, että haluat tietää enemmän. Tässä on muutama asiaankuuluva blogi, jotka pitävät sinut kiinnostuneina:

  1. Johdanto Markov-ketjuihin esimerkkeillä - Markov-ketjut Pythonilla

Tämän avulla olemme tämän blogin lopussa. Jos sinulla on kysyttävää tästä aiheesta, jätä kommentti alle ja palaamme sinuun.

Jos haluat ilmoittautua koko tekoälyn ja koneoppimisen kurssille, Edurekalla on erityisesti kuratoitu joka tekee sinusta taitavan tekniikoista, kuten valvotusta oppimisesta, valvomattomasta oppimisesta ja luonnollisen kielen prosessoinnista. Se sisältää koulutuksen uusimmista kehityksistä ja teknisistä lähestymistavoista tekoälyyn ja koneoppimiseen, kuten syväoppiminen, graafiset mallit ja vahvistusoppiminen.