Sve što trebate znati o algoritmu pretraživanja prve širine



U ovom blogu o algoritmu pretraživanja širine prvog, razgovarat ćemo o logici metoda križanja grafova i razumjeti njihov rad.

Metode prelaska grafova uvijek su me prilično fascinirale. Od izvođenja učinkovite ravnopravne komunikacije do pronalaska najbližih restorana i kafića pomoću GPS-a, metode prelaska imaju raznolik skup aplikacija u stvarnom scenariju. U ovom blogu o algoritmu pretraživanja širine prvog, razgovarat ćemo o logici metoda prijelaza grafova i na primjerima razumjeti rad algoritma pretraživanja širine prvo.

Da biste stekli detaljno znanje o umjetnoj inteligenciji i strojnom učenju, možete se prijaviti uživo Edureka s 24/7 podrškom i doživotnim pristupom.





Evo popisa tema koje će biti pokriven na ovom blogu:

  1. Uvod u prelazak grafikona
  2. Što je prvo pretraživanje u širini?
  3. Razumijevanje algoritma pretraživanja širine-prvo na primjeru
  4. Pseudokod algoritma pretraživanja u širini
  5. Primjene pretraživanja u širini

Uvod u prelazak grafikona

Proces posjećivanja i istraživanja grafa radi obrade naziva se prelazak grafa. Da budemo precizniji, sve je u tome da posjetimo i istražimo svaki vrh i rub u grafu tako da se svi vrhovi istražuju točno jednom.



To zvuči jednostavno! Ali tu je kvaka.

Postoji nekoliko tehnika zaokretanja grafova, poput pretraživanja u širinu, prvo pretraživanje u dubinu i tako dalje. Izazov je koristiti graf tehnika prelaska koja je najprikladnija za rješavanje određenog problema. To nas dovodi do tehnike pretraživanja širine prvo.

Što je algoritam pretraživanja najšire širine?

Algoritam pretraživanja najšire širine tehnika je prelaženja grafa, gdje odabirete slučajni početni čvor (izvorni ili korijenski čvor) i započinjete obilazak grafa slojno na takav način da se svi čvorovi i njihovi podređeni čvorovi posjete i istraže.



Prije nego što krenemo dalje i na primjeru shvatimo pretraživanje od prve širine, upoznajmo se s dva važna pojma u vezi s okretanjem grafa:

Grafički prijelaz - Algoritam prvog pretraživanja širine - Edureka

  1. Posjeta čvoru: Baš kao što i samo ime govori, posjet čvoru znači posjetiti ili odabrati čvor.
  2. Istraživanje čvora: Istražujući susjedni čvorovi (podređeni čvorovi) odabranog čvora.

Pogledajte gornju sliku da biste to bolje razumjeli.

Razumijevanje algoritma pretraživanja širine prvo na primjeru

kako koristiti split metodu u javi

Širina algoritma pretraživanja slijedi jednostavan pristup zasnovan na razini za rješavanje problema. Razmotrite dolje binarno stablo (koje je graf). Cilj nam je preći graf pomoću algoritma pretraživanja širine-prvog.

Prije nego što započnemo, morate biti upoznati s glavnom strukturom podataka koja je uključena u algoritam pretraživanja širina-prvo.

Red čekanja je apstraktna struktura podataka koja slijedi metodologiju First-In-First-Out (prvo će se pristupiti podacima koji su umetnuti prvi). Otvoren je na oba kraja, gdje se jedan kraj uvijek koristi za umetanje podataka (enqueue), a drugi se koristi za uklanjanje podataka (dequeue).

Pogledajmo sada korake u prelasku grafa pomoću pretraživanja širina-prva:

Korak 1: Uzmi prazan red.

Korak 2: Odaberite početni čvor (posjet čvoru) i umetnite ga u Red čekanja.

Korak 3: Pod uvjetom da Red čekanja nije prazan, izvucite čvor iz reda i umetnite njegove podređene čvorove (istražujući čvor) u Red čekanja.

Korak 4: Ispišite izvučeni čvor.

Ne brinite ako ste zbunjeni, shvatit ćemo to na primjeru.

Pogledajte grafikon u nastavku, mi ćemo se za prelazak kroz grafikon služiti algoritmom za pretraživanje u širinu.

U našem ćemo slučaju dodijeliti čvor ‘a’ kao korijenski čvor i početi se kretati prema dolje i slijediti gore spomenute korake.

Gornja slika prikazuje postupak od početka do kraja algoritma pretraživanja širine-prvog. Dopustite mi da ovo objasnim detaljnije.

  1. Dodijelite 'a' kao korijenski čvor i umetnite ga u red čekanja.
  2. Izvadite čvor 'a' iz reda i umetnite podređene čvorove 'a', tj. 'B' i 'c'.
  3. Čvor za ispis 'a'.
  4. Red čekanja nije prazan i ima čvor 'b' i 'c'. Budući da je 'b' prvi čvor u redu, izvucimo ga i umetnimo podređene čvorove 'b', tj. Čvor 'd' i 'e'.
  5. Ponavljajte ove korake dok se red ne isprazni. Imajte na umu da se čvorovi koji su već posjećeni ne bi trebali dodavati u red čekanja opet.

Pogledajmo sada pseudokod algoritma za pretraživanje najšire širine.

Pseudokod algoritma pretraživanja u širini

Evo pseudokoda za implementaciju algoritma pretraživanja širine prvo:

Ulaz: s kao izvorni čvor BFS (G, s) neka Q bude red. Q.enqueue (s) označavaju posjećene dok (Q nije prazan) v = Q.dequeue () za sve susjede w od v na Grafikonu G ako w nije posjećen Q.enqueue (w) označavaju w kao posjete

U gornjem kodu izvršavaju se sljedeći koraci:

  1. (G, s) je ulaz, ovdje je G grafikon, a s korijenski čvor
  2. Red „Q“ kreira se i inicijalizira s izvornim čvorom „s“
  3. Označeni su svi podređeni čvorovi s
  4. Izdvojite ‘s’ iz reda i posjetite podređene čvorove
  5. Obradite sve podređene čvorove v
  6. Pohranjuje w (podređene čvorove) u Q za daljnje posjećivanje njegovih podređenih čvorova
  7. Nastavite dok ne dođe 'Q' prazan

Prije nego što završimo s blogom, pogledajmo neke primjene algoritma za pretraživanje najšire širine.

Primjene algoritma pretraživanja u širini

Pretraživanje u širinu je jednostavna metoda prelaska grafova koja ima iznenađujući raspon primjena. Evo nekoliko zanimljivih načina na koje se koristi pretraživanje od kruha:

Alati za indeksiranje u pretraživačima: Široko pretraživanje prvo je jedan od glavnih algoritama koji se koristi za indeksiranje web stranica. Algoritam započinje kretanje s izvorne stranice i slijedi sve veze povezane sa stranicom. Ovdje će se svaka web stranica smatrati čvorom na grafikonu.

GPS navigacijski sustavi: Pretraživanje u širinu jedan je od najboljih algoritama koji se koristi za pronalaženje susjednih lokacija pomoću GPS sustava.

Pronađite najkraći put i minimalno rasponično stablo za neponderirani graf: Kada je riječ o neponderiranom grafu, izračunavanje najkraćeg puta je prilično jednostavno, jer je ideja najkraćeg puta odabrati put s najmanjim brojem bridova. Pretraživanje u širinu može to omogućiti prelaskom minimalnog broja čvorova počevši od izvornog čvora. Slično tome, za razapinjuće stablo možemo koristiti bilo koju od dviju metoda pretraživanja širine prvo ili dubine prijelaza kako bismo pronašli rastegnuto stablo.

Emitiranje: Umrežavanje koristi ono što nazivamo paketima za komunikaciju. Ovi paketi slijede metodu obilaženja kako bi došli do različitih mrežnih čvorova. Jedna od najčešće korištenih metoda prelaska je pretraživanje širine na prvo mjesto. Koristi se kao algoritam koji se koristi za komunikaciju emitiranih paketa preko svih čvorova u mreži.

Umrežavanje ravnopravnih osoba: Pretraživanje u širinu može se koristiti kao metoda obilaženja za pronalaženje svih susjednih čvorova u mreži ravnopravnih mreža. Na primjer, BitTorrent koristi široku pretragu za ravnopravnu komunikaciju.

pl sql za početnike s primjerima

Dakle, sve je bilo u radu algoritma za pretraživanje u širinu. Sad kad znate kako prelaziti grafove, siguran sam da želite znati više. Evo nekoliko relevantnih blogova koji će vas zanimati:

  1. Uvod u Markovljeve lance s primjerima - Markovljevi lanci s Pythonom

Ovim smo došli do kraja ovog bloga. Ako imate pitanja u vezi s ovom temom, ostavite komentar u nastavku i javit ćemo vam se.

Ako se želite upisati na cjeloviti tečaj o umjetnoj inteligenciji i strojnom učenju, Edureka ima posebno kuriranog koji će vas osposobiti za tehnike poput nadziranog učenja, nenadgledanog učenja i obrade prirodnog jezika. Uključuje obuku o najnovijim dostignućima i tehničkim pristupima u umjetnoj inteligenciji i strojnom učenju kao što su duboko učenje, grafički modeli i učenje ojačanja.