Graafikute läbimise meetodid on mind alati üsna paelunud. Alustades tõhusast vastastikusest suhtlusest kuni lähimate restoranide ja kohvikute leidmiseni GPS-i abil, on läbimismeetoditel reaalses stsenaariumis mitmekesine rakendus. Selles Breadth-First Search algoritmi ajaveebis käsitleme graafide läbimise meetodite loogikat ja kasutame näiteid, et mõista algoritmi Breadth-First Search algoritmi toimimist.
Tehisintellekti ja masinõppe põhjalike teadmiste saamiseks saate registreeruda otseülekandeks autor Edureka 24/7 toe ja eluaegse juurdepääsuga.
Siin on loetelu tulevastest teemadest selles blogis kajastatud:
- Graafiku läbimise sissejuhatus
- Mis on laiuse esimene otsing?
- Näidise abil laiuse esimese otsingu algoritmi mõistmine
- Laiuse esimese otsingu algoritmi pseudokood
- Esimese laiuse otsingu rakendused
Graafiku läbimise sissejuhatus
Graafi külastamise ja uurimise protsessi töötlemiseks nimetatakse graafi läbimiseks. Täpsemalt öeldes on see graafiku iga tipu ja serva külastamine ja uurimine nii, et kõiki tippe uuritakse täpselt üks kord.
See kõlab lihtsalt! Kuid seal on konks.
Graafiku läbimise tehnikaid on mitu, näiteks laius-esimene otsing, sügavus esimene otsing ja nii edasi. Väljakutse on kasutada graafikut läbimistehnika, mis sobib kõige paremini konkreetse probleemi lahendamiseks. See viib meid Breadth-First Search tehnika juurde.
Mis on laiuse esimese otsingu algoritm?
Laiuse esimene otsingualgoritm on graafi läbiv tehnika, kus valite juhusliku algsõlme (lähte- või juursõlme) ja hakkate graafiliselt kihiti liikuma nii, et külastatakse ja uuritakse kõiki sõlme ja nende vastavaid laste sõlmi.
Enne kui läheme edasi ja mõistame näite abil laiuse esimest otsingut, tutvume kahe graafi läbimisega seotud olulise terminiga:
fibonacci järjestuse java silmuse jaoks
- Sõlme külastamine: Täpselt nagu nimigi ütleb, tähendab sõlme külastamine sõlme külastamist või valimist.
- Sõlme uurimine: Avastamine valitud sõlme külgnevad sõlmed (alamsõlmed).
Selle paremaks mõistmiseks vaadake ülaltoodud joonist.
Näite abil aru saamine laiuse esimese otsingu algoritmist
Laiuse esimene otsingu algoritm järgib probleemi lahendamiseks lihtsat, tasemepõhist lähenemist. Vaatleme allpool olevat binaarpuud (mis on graafik). Meie eesmärk on graafi läbimine, kasutades laiuse esimese otsingu algoritmi.
Enne kui alustame, peate olema tuttav algoritmis Breadth-First Search seotud peamise andmestruktuuriga.
Järjekord on abstraktne andmestruktuur, mis järgib meetodit First-In-First-Out (kõigepealt sisestatakse kõigepealt sisestatud andmed). See on avatud mõlemast otsast, kus ühte otsa kasutatakse alati andmete sisestamiseks (enqueue) ja teist kasutatakse andmete eemaldamiseks (dequeue).
Vaatame nüüd graafiku läbimise samme, kasutades laiuse esimest otsingut:
Samm 1: Võtke tühi järjekord.
2. samm: Valige algussõlm (sõlme külastamine) ja sisestage see järjekorda.
3. samm: Tingimusel, et järjekord ei ole tühi, eraldage sõlm järjekorrast ja sisestage selle alamsõlmed (sõlme uurides) järjekorda.
4. samm: Väljatrükitud sõlme printimine.
Ärge muretsege, kui olete segaduses, mõistame seda näite abil.
Heitke pilk allpool olevale graafikule. Graafiku läbimiseks kasutame algoritmi Breadth-First Search algoritmi.
mida split teeb javas
Meie puhul määrame juursõlmeks sõlme ‘a’, alustame liikumist allapoole ja järgime ülalnimetatud samme.
Ülaloleval pildil on kujutatud otsingu algoritmi otsast lõpuni protsess. Las ma selgitan seda põhjalikumalt.
- Määra juursõlmeks ‘a’ ja sisesta see järjekorda.
- Eemaldage järjekorrast sõlm „a” ja sisestage „a”, st „b” ja „c” alamsõlmed.
- Trükisõlm ‘a’.
- Järjekord ei ole tühi ja sellel on sõlmed „b” ja „c”. Kuna ‘b’ on järjekorra esimene sõlm, siis eraldame selle ja sisestame „b“ alamsõlmed, st sõlmed „d“ ja „e“.
- Korrake neid samme, kuni järjekord tühjeneb. Pange tähele, et juba külastatud sõlme ei tohiks järjekorda lisada uuesti.
Vaatame nüüd algoritmi Breadth-First Search pseudokoodi.
Laiuse esimese otsingu algoritmi pseudokood
Siin on pseudokood laiuse esimese otsingu algoritmi rakendamiseks:
kuidas püütonis arvu ümber pöörata
Sisend: s kui lähtesõlm BFS (G, s) laseb Q-l olla järjekord. Q.enqueue (s) märgivad külastatuks ajal (Q pole tühi) v = Q.dequeue () kõigile graafiku G naabritele w, kui w pole külastatud Q.enqueue (w) märkige w külastatuks
Ülaltoodud koodis täidetakse järgmised toimingud:
- (G, s) on sisend, siin on G graaf ja s on juursõlm
- Järjekord Q luuakse ja lähtestatakse allikasõlmega s
- Kõik ’s’ alamsõlmed on tähistatud
- Eemaldage järjekorrast s-id ja külastage lapse sõlmi
- Töötle kõik v-i lapse sõlmed
- Kauplused w (lapse sõlmed) Q-s, et oma lapse sõlmi veelgi külastada
- Jätkake, kuni ‘Q’ on tühi
Enne ajaveebi lõpetamist vaatame mõningaid algoritmi Breadth-First Search rakendusi.
Laiuse esimese otsingu algoritmi rakendused
Laius kõigepealt otsing on lihtne graafi läbimise meetod, millel on üllatav rakendusala. Siin on mõned huvitavad viisid, kuidas leiba esmast otsingut kasutatakse:
Indekseerijad otsingumootorites: Laiuse esimene otsing on üks peamisi algoritme, mida veebilehtede indekseerimiseks kasutatakse. Algoritm hakkab liikuma alglehelt ja järgib kõiki lehega seotud linke. Siin loetakse iga veebileht graafiku sõlmpunktiks.
GPS-navigatsioonisüsteemid: Laiuse esimene otsing on üks parimaid algoritme, mida kasutatakse GPS-süsteemi abil naabruskohtade leidmiseks.
Leidke kaalumata graafiku jaoks lühim tee ja minimaalne haaramispuu: Kaalumata graafiku puhul on kõige lühema tee arvutamine üsna lihtne, kuna kõige lühema tee idee on valida tee, kus on kõige vähem servi. Laius-esimene otsing võimaldab seda, kui läbib minimaalse arvu sõlmede alates lähtesõlmest. Samamoodi võime laiuva puu leidmiseks kasutada laieneva puu leidmiseks ühte neist kahest meetodist: laius-esimene otsing või sügavus-esimene läbimismeetod.
Ringhääling: Võrgustikus kasutatakse seda, mida me nimetame suhtlemiseks pakettidena. Need paketid järgivad läbimismeetodit, et jõuda erinevate võrgusõlmedeni. Üks levinumaid läbimismeetodeid on laiuse esimene otsing. Seda kasutatakse algoritmina, mida kasutatakse levitatud pakettide edastamiseks võrgu kõigi sõlmede vahel.
Peer to Peer Networking: Laiuse esmast otsingut saab kasutada läbimismeetodina, et leida kõik naabersõlmed Peer to Peer võrgus. Näiteks kasutab BitTorrent vastastikuse suhtluse jaoks Breadth-First Searchi.
Nii et see kõik puudutas algoritmi „Leiba esimene otsimine“ tööd. Nüüd, kui teate, kuidas graafikuid läbida, olen kindel, et soovite rohkem teada saada. Siin on mõned asjakohased ajaveebid, et teid huvitada:
Sellega jõuame selle blogi lõpuni. Kui teil on selle teema kohta küsimusi, jätke palun allpool kommentaar ja võtame teiega ühendust.
Kui soovite registreeruda tehisintellekti ja masinõppe kursusele, on Edurekal spetsiaalselt kureeritud mis aitab teil omandada selliseid tehnikaid nagu juhendatud õppimine, järelevalveta õppimine ja loomuliku keele töötlemine. See hõlmab koolitust tehisintellekti ja masinõppe uusimate edusammude ja tehniliste lähenemisviiside kohta, nagu sügavõpe, graafilised mudelid ja tugevdav õppimine.