gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / NajboljiPut / zadatak-najbolji-put.txt
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt
--- /dev/null
@@ -0,0 +1,101 @@
+============================================================\r
+ Zadatak - pretrazivanje sa vracanjem - svi putevi\r
+============================================================\r
+\r
+\r
+Postavka problema\r
+============================================================\r
+\r
+Neka je dat lavirint kao matrica polja, pri cemu razlicite \r
+vrednosti polja imaju razlicito znacenje. Potrebno je pronaci\r
+OPTIMALAN put kroz lavirint od pocetnog polja, do izlaza iz \r
+lavirinta, pri cemu se pod putem smatra niz polja koja je \r
+potrebno posetiti u datom redosledu, da bi se stiglo od \r
+pocetnog polja do cilja. Pri obilasku lavirinta, sa jednog \r
+polja je moguce preci na susedno ako ona imaju istu ivicu, \r
+tj. ako se ono nalazi odmah levo, desno, gore ili dole u \r
+odnosu na trenutno polje.\r
+\r
+Znacenja vrednosti polja su;\r
+0 = slobodno polje u lavirintu na koje je dozvoljeno stati\r
+-11 = zid, polje na koje nije dozvoljeno stati\r
+-99 = izlaz iz lavirinta\r
+bilo koji pozitivan broj = vrednost blaga na tom polju\r
+\r
+Format fajla\r
+------------------------------------------------------------\r
+\r
+Mapa je u fajlu predstavljena na sledeci nacin:\r
+\r
+U prvom redu se nalaze dva broja S i V koji predstavljaju\r
+sirinu i visinu mape.\r
+\r
+U sledecih V redova se nalaze po S celih brojeva koji\r
+predstavljaju vrednosti polja u lavirintu.\r
+\r
+Polje (0, 0) nalazi se u gornjem levom polju matrice.\r
+\r
+\r
+Primeri\r
+------------------------------------------------------------\r
+\r
+Za testiranje programa su dati su fajlovi:\r
+"lav1.txt" i "lav2.txt" u kojima postoji resenje\r
+"lavp.txt" koji ne sadrzi zidove\r
+"lavb.txt" u kojem nije moguce naci resenje\r
+"blago*.txt" za testiranje zadatka sa blagom\r
+\r
+\r
+Zadatak\r
+============================================================\r
+\r
+Napisati klasu LavirintProgram koja ucitava ime fajla u kojem\r
+se nalazi definisan lavirint, koordinate pocetne pozicije \r
+(x, y) od koje se trazi izlaz iz lavirinta, kao i izbor sta \r
+zelimo da radimo. Nakon ucitanog izbora, klasa treba da ucita\r
+lavirint iz datog fajla, ispise ga na ekran i izvrsi izabranu\r
+operaciju. \r
+\r
+Ponuditi korisniku sledeci izbor:\r
+3 - ispis najkraceg puta od unetog polja do izlaza\r
+4 - ispis najvrednijeg puta od unetog polja do izlaza\r
+\r
+\r
+Modifikacija pretrazivanja sa vracanjem\r
+------------------------------------------------------------\r
+\r
+Jedan od nacina da se uradi zadatak je koriscenjem modifikacije\r
+pretrazivanja sa vracanjem. Potrebne modifikacije su sledece:\r
+\r
+1. Nakon dolaska na odredjeno polje u lavirintu potrebno je\r
+to polje ubaciti na kraj trenutnog puta od pocetka lavirinta \r
+do trenutnog polja\r
+2. Nakon povratka sa polja, potrebno je to polje izabaciti sa \r
+kraja trenutnog puta\r
+3. Prilikom obilaska izlaza, potrebno je trenutnu vrednost \r
+puta uporediti sa do sada najoptimalnijim pronadjenim putem\r
+i ukoliko je trenutni put bolji, kopirati ga u optimalan put\r
+4. Vratiti optimalan put ako postoji ili vrednost null ako ne \r
+postoji\r
+\r
+\r
+Neobavezne preporuke:\r
+------------------------------------------------------------\r
+\r
+1. Kreirati posebnu klasu Resenje koja ce pamtiti resenje.\r
+Resenje pamtiti kao niz ili listu polja, od cega za svako\r
+polje treba zapamtiti koordinate polja i vrednost\r
+2. Prilikom uporedjivanja resenja, koristiti komparatore\r
+3. Za racunanje vrednosti puta koristiti metode koje su deo \r
+klase put (npr. getSize() i getValue())\r
+\r
+\r
+Prosirenje zadatka:\r
+------------------------------------------------------------ \r
+\r
+Modifikovati postojece metode za trazenje puta tako da:\r
+\r
+- pronalaze put sa najvrednijim blagom pojedinacno\r
+- pronalaze put na kojem postoji najvise polja sa blagom\r
+- pronalaze put na kojem postoji najvise uzastopnih polja sa\r
+ blagom\r