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 i 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.

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.

Algoritam

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"), na neobiđena polja upisuje se -1, a u nedostupna polja ("sanduke"), upisuje se -2.

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.

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:

do polja udaljenosti 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"!)
na svako od polja udaljenosti 8, može se doći sa bilo kog od susednih polja udaljenosti 7
na svako od 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.