Vse, kar morate vedeti o algoritmu prvega iskanja širine

Načini prečkanja grafov so me vedno navduševali. Od izvajanja učinkovite medsebojne komunikacije do iskanja najbližjih restavracij in kavarn z uporabo GPS-a imajo metode prečkanja različne načine uporabe v resničnem scenariju. V tem blogu o algoritmu iskanja prve širine bomo razpravljali o logiki metod prečkanja grafov in na zgledih razumeli delovanje algoritma za iskanje široke širine.

kakšna je uporaba programiranja vtičnic

Če želite poglobljeno znanje o umetni inteligenci in strojnem učenju, se lahko vpišete v živo Edureka s 24-urno podporo in življenjskim dostopom.

Tu je seznam tem, ki bodo zajeto v tem blogu:

1. Uvod v prehod grafov
2. Kaj je iskanje po širini?
3. Razumevanje algoritma iskanja širine najprej s primerom
4. Širokoprvi algoritem iskanja Psevkodo
5. Aplikacije širokega iskanja

Uvod v prehod grafov

Postopek obiska in raziskovanja grafa za obdelavo imenujemo prehod grafa. Če smo natančnejši, gre za obisk in raziskovanje vsake oglišča in roba v grafu, tako da so vsa oglišča natančno enkrat raziskana.

Sliši se preprosto! Toda tu je ulov.

Obstaja več tehnik prečkanja grafov, kot so iskanje po širini, iskanje po globini in tako naprej. Izziv je uporaba grafa tehnika prečkanja, ki je najprimernejša za reševanje določenega problema. To nas pripelje do tehnike iskanja širine najprej.

Kaj je algoritem iskanja s širino?

Algoritem iskanja v širini je tehnika premikanja grafov, pri kateri izberete naključno začetno vozlišče (izvorno ali korensko vozlišče) in začnete prehajati graf po plasteh tako, da so vsa vozlišča in njihova podrejena vozlišča obiskana in raziskana.

Preden se premaknemo naprej in s primerom razumemo iskanje po širini, se seznanimo z dvema pomembnima izrazoma, povezanima s prehodom grafov:

1. Obisk vozlišča: Kot že ime pove, obisk vozlišča pomeni obisk ali izbiro vozlišča.
2. Raziskovanje vozlišča: Raziskovanje sosednja vozlišča (podrejena vozlišča) izbranega vozlišča.

Za boljše razumevanje glejte zgornjo sliko.

Razumevanje algoritma iskanja širine najprej s primerom

Razširitveni algoritem za iskanje problema sledi preprostemu pristopu, ki temelji na ravni. Upoštevajte spodnje binarno drevo (ki je graf). Naš cilj je prehoditi graf z uporabo algoritma iskanja širine najprej.

Preden začnemo, morate poznati glavno podatkovno strukturo, vključeno v algoritem za iskanje širine-najprej.

Čakalna vrsta je abstraktna podatkovna struktura, ki sledi metodologiji First-In-First-Out (prvi vstavljeni podatki bodo dostopni najprej). Odprt je na obeh koncih, pri čemer se en konec vedno uporablja za vstavljanje podatkov (čakalna vrsta), drugi pa za odstranjevanje podatkov (razveljavitev).

Zdaj pa si oglejmo korake, ki so povezani s prehodom grafa z uporabo iskanja najprej širine:

Korak 1: Vzemite prazno vrsto.

2. korak: Izberite začetno vozlišče (obisk vozlišča) in ga vstavite v čakalno vrsto.

3. korak: Če čakalna vrsta ni prazna, izvleči vozlišče iz čakalne vrste in v čakalno vrsto vstavi njegova podrejena vozlišča (raziskovanje vozlišča).

se naučite pl sql na spletu brezplačno -

4. korak: Natisnite izvlečeno vozlišče.

Ne skrbite, če ste zmedeni, to bomo razumeli s primerom.

Oglejte si spodnji graf, za prehod skozi graf bomo uporabili algoritem Najširše iskanje.

V našem primeru bomo kot korensko vozlišče dodelili vozlišče ‘a’ in začeli prehajati navzdol ter sledili zgoraj omenjenim korakom.

Zgornja slika prikazuje postopek od konca do konca algoritma iskanja širine prvič. Naj to podrobneje razložim.

1. Kot korensko vozlišče dodelite 'a' in ga vstavite v čakalno vrsto.
2. Izvlecite vozlišče 'a' iz čakalne vrste in vstavite podrejena vozlišča 'a', tj. 'B' in 'c'.
3. Tiskalno vozlišče 'a'.
4. Čakalna vrsta ni prazna in ima vozlišči 'b' in 'c'. Ker je 'b' prvo vozlišče v čakalni vrsti, ga izvlecimo in vstavimo podrejena vozlišča 'b', torej vozlišča 'd' in 'e'.
5. Ponavljajte te korake, dokler se vrsta ne izprazni. Upoštevajte, da vozlišča, ki so že obiskana, ne bi smeli biti dodani v čakalno vrsto ponovno.

Zdaj pa si oglejmo psevdokodo algoritma za iskanje širine najprej.

Širokoprvi algoritem iskanja Psevkodo

Tukaj je psevdokoda za izvajanje algoritma iskanja širine najprej:

Vhod: s kot izvorno vozlišče BFS (G, s) naj bo Q čakalna vrsta. Oznake Q.enqueue (s) so obiskane, medtem ko (Q ni prazno) v = Q.dequeue () za vse sosede w od v na grafu G, če w ni obiskano Q.enqueue (w) označi w kot obiskano

V zgornji kodi se izvedejo naslednji koraki:

1. (G, s) je vnos, tu je G graf in s korensko vozlišče
2. Čakalna vrsta 'Q' se ustvari in inicializira z izvornim vozliščem 's
3. Označena so vsa podrejena vozlišča 's'
4. Izvlecite 's' iz čakalne vrste in obiščite podrejena vozlišča
5. Obdelajte vsa podrejena vozlišča v
6. Shrani w (podrejena vozlišča) v Q za nadaljnje obiskovanje svojih podrejenih vozlišč
7. Nadaljujte, dokler ni 'Q' prazno

Preden zaključimo blog, si oglejmo nekaj aplikacij algoritma za iskanje širine najprej.

Aplikacije algoritma iskanja širine prvič

Iskanje po širini je preprosta metoda prečkanja grafov, ki ima presenetljivo vrsto aplikacij. Tu je nekaj zanimivih načinov, kako se uporablja iskanje kruha najprej:

Pajki v iskalnikih: Iskanje po širini je eden glavnih algoritmov, ki se uporablja za indeksiranje spletnih strani. Algoritem začne prehajati z izvorne strani in sledi vsem povezavam, povezanim s stranjo. Tu bo vsaka spletna stran obravnavana kot vozlišče v grafu.

GPS navigacijski sistemi: Iskanje po širini je eden najboljših algoritmov za iskanje sosednjih lokacij s pomočjo sistema GPS.

Poiščite najkrajšo pot in najmanjše drevo za nestehtani graf: Ko gre za netehtani graf, je izračun najkrajše poti zelo preprost, saj je ideja za najkrajšo pot izbrati pot z najmanjšim številom robov. Iskanje po širini lahko to omogoči tako, da prečka najmanjše število vozlišč, začenši od izvornega vozlišča. Podobno lahko za drevo, ki se razteza, uporabimo katero koli od obeh, način širine najprej iskanje ali prehod globine najprej, da najdemo drevo razpetine.

Oddajanje: Omrežje uporablja tisto, čemur pravimo kot paketi za komunikacijo. Ti paketi sledijo prehodni metodi, da dosežejo različna omrežna vozlišča. Eden najpogosteje uporabljenih načinov prečkanja je iskanje po širini. Uporablja se kot algoritem, ki se uporablja za komunikacijo oddanih paketov po vseh vozliščih v omrežju.

Medsebojno povezovanje: Iskanje po širini se lahko uporabi kot način prečkanja za iskanje vseh sosednjih vozlišč v omrežju enakovrednih omrežij. Na primer, BitTorrent uporablja iskanje po širini za medsebojno komunikacijo.

vsota števk v javi

Torej, to je bilo vse o delovanju algoritma za iskanje širine-najprej. Zdaj, ko veste, kako prečkati grafe, sem prepričan, da vas zanima več. Tukaj je nekaj ustreznih spletnih dnevnikov, ki vas zanimajo:

3. Uvod v Markove verige s primeri - Markovske verige s Pythonom

S tem smo prišli do konca tega spletnega dnevnika. Če imate kakršna koli vprašanja v zvezi s to temo, pustite komentar spodaj in odgovorili vam bomo.

Če se želite vpisati na celoten tečaj o umetni inteligenci in strojnem učenju, ima Edureka posebej kurirano s tem boste usposobljeni za tehnike, kot so nadzorovano učenje, nenadzorovano učenje in obdelava naravnega jezika. Vključuje usposabljanje o najnovejših dosežkih in tehničnih pristopih na področju umetne inteligence in strojnega učenja, kot so globoko učenje, grafični modeli in učenje okrepitve.