BFS i DFS - Pronalaženje putanje kroz lavirint

Svi putevi vode u ....

Razmotrimo problem pronalaženja puta kroz lavirint. Za primer ćemo uzeti tablu 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 zablokirano (siva polja). Naš zadatak je da pronađemo postupak kojim ćemo ustanoviti da li se sa zelenog polja, krećući se po datim pravilima, može preći na narandžasto (da, mi vidimo da može, ali, moramo da ubedimo računar da i on "progleda").

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") sivom.

Za početak, označićemo polja brojevima: početno polje će dobiti vrednost 0 (njegova udaljenost od samog sebe je, naravno - 0), polja koja nismo obišli će dobiti vrednost -1 (šifra za "nije obiđeno"), a sivi "sanduci" će dobiti vrednost -2 (šifra za nedostupna polja na koja ne možemo da prelazimo).

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

Potom ćemo sa početnog polja preći na sva dostupna susedna polja i upisati na njih vrednost 1, koja odgovara njihovoj udaljenosti od početnog polja, shodno navedenim pravilima.

Prolazak kroz lavirint - korak 1
Slika 3. - Pronalaženje putanje kroz lavirint - korak 1. - Pošavši sa početnog polja, označićemo sva dostupna susedna polja vrednošću 1 (njihovo rastojanje od početnog polja je 1) i stavićemo ih u red za čekanje (čime pamtimo da je potrebno ponoviti ovu istu proceduru za svako od četiri polja kojima smo upravo upisali vrednost 1).

Sa polja udaljenosti 1, preći ćemo na polja udaljenosti 2 i ponoviti postupak.

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

Sa "dvojki" ćemo preći na "trojke".

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

Sa "trojki" na "četvorke".

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

Sa "četvorki" na "petice".

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

Sa "petica" na "šestice".

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

Sa "šestica" na "sedmice".

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

Sa "sedmica" 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" na "devetke". Jedno od polja na koje stupamo je i traženo narandžasto polje, pa se ovde pretraga zaustavlja.

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, pa se stoga dalja potraga obustavlja.

Da bismo pronašli sve putanje, moramo ispratiti sve kombinacije koje se dobijaju kretanjem 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; na svako od tih polja može se doći sa bilo kog od susednih polja udaljenosti 7 (ALI - samo sa susednih polja!); na svako od polja udaljenosti 7 sa svakog od susednih polja udaljenosti 6 i tako 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), pri čemu je jedna od njih (prva koju bi DFS pronašao) označena tamno plavom bojom.
Preuzmite pojedinačne slike iz GIF animacije

Takođe, sada znate kako funkcioniše alat Paint Bucket u programu MS Paint. :D

Napomena: Tekstovi i slike na sajtu www.skola-programiranja.rs (osim u slučajevima pojedinih fotografija, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.skola-programiranja.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora i Računarskog centra SystemPro. ©SystemPro d.o.o. novembar 2019.
Autor članka Nikola Vukićević Za web portal www.skola-programiranja.rs Preuzeto sa sajta www.codeblog.rs uz odobrenje autora
Podelite sa prijateljima: