BFS i DFS - Pronalaženje putanje kroz lavirint

Uvod

Svi putevi vode u ....

Razmotrićemo problem pronalaženja putanje kroz lavirint (pri čemu ćemo za primer uzeti tabelu sa 10 x 10 polja).

Sa svakog polja je dozvoljeno prelaziti na susedna polja: napred, nazad, levo ili desno, pod uslovom da dato polje nije blokirano (siva polja na slikama), a naš zadatak je da iznađemo postupak preko koga računar može ustanoviti da li se sa zelenog polja, krećući se po navedenim pravilima, može preći na narandžasto polje. *

Kada rešimo 'prvi zadatak', osvrnućemo se i na postupak za pronalaženje svih putanja.

Lavirint - početna situacija — Slika 1. - "Lavirint" - početna situacija: početno polje označeno je zelenom bojom, traženo polje narandžastom, a polja preko kojih se ne može prelaziti ("sanduci"), označena su sivom bojom.

Pronalaženje putanja

Budući da je članak namenjen mlađim čitaocima, ovoga puta ćemo se pozabaviti opštim idejama, na jednostavan način (nekom drugom prilikom, predstavićemo algoritme za pretragu detaljnije).

Pošto je prvi zadatak - ustanoviti da li je "ikako moguće" stići do ciljanog polja, praktično rešenje podrazumeva postepeno i sistematično ispitivanje susednih polja, "u širinu", "u svim pravcima", a kasnije, ako se ustanovi da postoji (bar jedna) putanja između početnog i krajnjeg polja, primenićemo algoritam koji prati putanje preko svih "susednih polja" koja zapravo povezuju početno i krajnje polje.

Za početak, potrebno je označiti polja brojevima:

početno polje će dobiti vrednost 0 (udaljenost polja "od samog sebe" je, naravno, 0)
polja koja nisu obiđena dobiće vrednost -1 (šifra za "neobiđena polja")
sivi "sanduci" će dobiti vrednost -2 (šifra za "nedostupna polja na koja se ne može prelaziti")

Prolazak kroz lavirint - korak 0 — Slika 2. - Pronalaženje putanje kroz lavirint - početna situacija: početnom polju dodeljuje se vrednost 0 ("nulto rastojanje od samog sebe"), u neobiđena polja upisuje se -1, a u nedostupna polja ("sanduke"), upisuje se -2.

BFS - Breadth First Search (pretraga "u širinu")

U prvom koraku, sa početnog polja prelazi se na sva dostupna susedna polja, i upisuje se vrednost 1 (koja odgovara udaljenosti "plavih" polja od početnog polja (shodno ranije navedenim pravilima)).

Prolazak kroz lavirint - korak 1 — Slika 3. - Pronalaženje putanje kroz lavirint - korak 1. - Krenuvši od početnog polja, sva dostupna susedna polja označavaju se vrednošću 1 (rastojanje datih polja od početnog polja je 1), i potom se navedena polja stavljaju u red za čekanje (čime se "pamti" da je potrebno ponoviti istu proceduru za svako od četiri polja kojima je upravo dodeljena vrednost 1).

Sa polja udaljenosti 1, prelazi se na polja udaljenosti 2 ....

Prolazak kroz lavirint - korak 2 — Slika 4. - Pronalaženje putanje kroz lavirint - korak 2. - Pronalaženje polja udaljenosti 2.

Vrednost 2 se upisuje u polja, i potom se postupak 'ponavlja':

- Sa "dvojki" se prelazi na "trojke".

Prolazak kroz lavirint - korak 3 — Slika 5. - Pronalaženje putanje kroz lavirint - korak 3. - Pronalaženje polja udaljenosti 3.

- Sa "trojki" se prelazi na "četvorke".

Prolazak kroz lavirint - korak 4 — Slika 6. - Pronalaženje putanje kroz lavirint - korak 4. - Pronalaženje polja udaljenosti 4.

- Sa "četvorki" se prelazi na "petice".

Prolazak kroz lavirint - korak 5 — Slika 7. - Pronalaženje putanje kroz lavirint - korak 5. - Pronalaženje polja udaljenosti 5.

- Sa "petica" se prelazi na "šestice".

Prolazak kroz lavirint - korak 6 — Slika 8. - Pronalaženje putanje kroz lavirint - korak 6. - Pronalaženje polja udaljenosti 6.

- Sa "šestica" se prelazi na "sedmice".

Prolazak kroz lavirint - korak 7 — Slika 9. - Pronalaženje putanje kroz lavirint - korak 7. - Pronalaženje polja udaljenosti 7.

- Sa "sedmica" se prelazi na "osmice" ....

Prolazak kroz lavirint - korak 8 — Slika 10. - Pronalaženje putanje kroz lavirint - korak 8. - Pronalaženje polja udaljenosti 8.

.... i, na kraju, sa "osmica" se prelazi na polja udaljenosti devet (koraka).

Prolazak kroz lavirint - korak 9 — Slika 11. - Pronalaženje putanje kroz lavirint - korak 9. - Pronalaženje polja udaljenosti 9. Ovoga puta, jedno od upisanih polja je i traženo polje, i stoga se dalja potraga obustavlja.

Jedno od označenih polja je "narandžasto" (traženo) polje, i stoga se na ovom mestu pretraga zaustavlja.

DFS - Depth First Search (pretraga "u dubinu")

Zarad pronalaženja svih putanja, potrebno je ispratiti sve kombinacije koje se dobijaju kretanjem unazad, od narandžastog polja, preko susednih polja manje udeljenosti, sve do početnog polja.

Da pojasnimo dodatno:

do označenog polja sa udaljenošću 9, može se doći sa bilo kog od susednih polja udaljenosti 8, ALI - samo sa susednih polja udaljenosti 8 (ne i sa ostalih polja koja su označena sa "8")
do nekog od susednih polja udaljenosti 8, može se doći sa bilo kog od susednih polja udaljenosti 7
do nekog od susednih polja udaljenosti 7, može se doći sa bilo kog od susednih polja udaljenosti 6 ....

.... nakon čega slede prelasci 6 => 5, 5 => 4, 4 => 3, 3 => 2, 2 => 1, redom - do početnog polja.

Pronalaženje putanje - Animacija — Slika 12. - Animacija koja prikazuje algoritam DFS (Depth First Search), koji pronalazi sve moguće putanje (svetlo plava polja), pri čemu je jedna od putanja (prva koju bi algoritam DFS pronašao), označena tamno plavom bojom.

Autor članka Nikola Vukićević Za web portal codeblog.rs

Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.