gitweb on Svarog

projekti pod git sistemom za održavanje verzija -- projects under the git version control system
Zadatak nalazenje da li postoji put u lavirintu.
[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / PostojanjePuta / zad-put-u-lavirintu.txt
1 ============================================================
2 Zadatak - pretrazivanje sa vracanjem - put u lavirintu
3 ============================================================
6 Postavka problema
7 ============================================================
9 Neka je dat lavirint kao matrica polja, pri cemu razlicite
10 vrednosti polja imaju razlicito znacenje. Potrebno je pronaci
11 put kroz lavirint od pocetnog polja, do izlaza iz lavirinta,
12 pri cemu se pod putem smatra niz polja koja je potrebno
13 posetiti u datom redosledu, da bi se stiglo od pocetnog polja
14 do cilja. Pri obilasku lavirinta, sa jednog polja je moguce
15 preci na susedno ako ona imaju istu ivicu, tj. ako se ono
16 nalazi odmah levo, desno, gore ili dole u odnosu na trenutno
17 polje.
19 Znacenja vrednosti polja su;
20 0 = slobodno polje u lavirintu na koje je dozvoljeno stati
21 -11 = zid, polje na koje nije dozvoljeno stati
22 -99 = izlaz iz lavirinta
25 Format fajla
26 ------------------------------------------------------------
28 Mapa je u fajlu predstavljena na sledeci nacin:
30 U prvom redu se nalaze dva broja S i V koji predstavljaju
31 sirinu i visinu mape.
33 U sledecih V redova se nalaze po S celih brojeva koji
34 predstavljaju vrednosti polja u lavirintu.
36 Polje (0, 0) nalazi se u gornjem levom polju matrice.
39 Primeri
40 ------------------------------------------------------------
42 Za testiranje programa su dati su fajlovi:
43 "lav1.txt" i "lav2.txt" u kojima postoji resenje
44 "lavp.txt" koji ne sadrzi zidove
45 "lavb.txt" u kojem nije moguce naci resenje
47 "lav-rupe.txt" za testiranje modifikacije zadatka sa rupama
48 "lav-prepreke.txt" za testiranje modifikacije zadatka sa preprekama
50 Modifikacije su opisane na kraju teksta.
53 Zadatak
54 ============================================================
56 Napisati klasu LavirintProgram koja ucitava ime fajla u kojem
57 se nalazi definisan lavirint, koordinate pocetne pozicije
58 (x, y) od koje se trazi izlaz iz lavirinta, kao i izbor sta
59 zelimo da radimo. Nakon ucitanog izbora, klasa treba da ucita
60 lavirint iz datog fajla, ispise ga na ekran i izvrsi izabranu
61 operaciju.
63 Ponuditi korisniku sledeci izbor:
64 1 - provera da li postoji put od unetog polja do izlaza
65 2 - ispis puta ukoliko postoji, odnosno ispis poruke da put
66 ne postoji
69 Pretrazivanje sa vracanjem
70 ------------------------------------------------------------
72 Jedan od nacina da se uradi zadatak je koriscenjem pretrazivanja
73 sa vracanjem (poznatom u literaturi pod engleskim nazivom
74 "backtrack").
76 Ideja je jednostavna, krenemo od prvog polja, oznacimo ga
77 kao poseceno i pokusamo da se prebacimo na bilo koje
78 neobidjeno susedno. Na tom polju ponovimo isti postupak i
79 tako nastavljamo dok ne naidjemo na izlaz ili dok vise
80 nemamo gde da idemo.
82 Ukoliko nismo naisli na izlaz, a nemamo gde dalje da idemo,
83 onda oznacimo trenutno polje kao neobidjeno i vratimo se
84 jedno polje nazad i probamo nekog drugog suseda. Ako vise
85 nema suseda vratimo se jos jedno polje. Ukoliko vise nema
86 gde da se vracamo znaci da se do izlaza ne moze doci.
88 Backtrack je najlakse izvoditi rekurzivno, tako da se poziv
89 procedure vrsi za pojedinacno polje. Ovako se povratkom iz
90 rekurzije vracamo na polje odakle smo dosli.
93 Jedna od mogucih varijanti ideje procedure:
95 rek(i,j,...)
96 - nije u matrici? -> izlaz
97 - zid? -> izlaz
98 - poseceno polje? -> izlaz
99 - da li je kraj? -> obradimo resenje
100 - inace trazimo dalje
101 - postavimo da je poseceno polje
102 - pokusamo da obidjemo sve susede:
103 - rek(i+1,j,..)
104 - rek(i-1,j,..)
105 - rek(i,j+1,..)
106 - rek(i,j-1,..)
107 - postavimo da polje nije poseceno
110 Prosirenje zadatka:
111 ------------------------------------------------------------
113 Neka je dat lavirint sa sledecim dodatnim poljima:
114 -1 = rupa na putu
115 bilo koji pozitivan broj = visina prepreke na putu
117 Modifikovati postojece metode za trazenje puta tako da:
118 - omogucavaju preskakanje rupa, ali samo ako je rupa velicine
119 jednog polja. Rupe koje su u datom pravcu duze od jednog
120 polja ne preskakati
121 - omogucava penjanje po preprekama, ali samo po preprekama
122 koje su za najvise 3 vislje od visine trenutnog polja.
123 Ukoliko se vec nalazimo na prepreci, dozvoljeno je preci na
124 vislju prepreku, ukoliko ona nije veca za vise od 3 od
125 postojece prepreke. Silazak sa prepreke je moguc na bilo
126 koje polje osim zida
127 - omogucava preskakanje prepreka, ali najvise 4 puta
Svarog.pmf.uns.ac.rs/gitweb maintanance Doni Pracner