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
-============================================================\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
+============================================================
+ Zadatak - pretrazivanje sa vracanjem - svi putevi
+============================================================
+
+
+Postavka problema
+============================================================
+
+Neka je dat lavirint kao matrica polja, pri cemu razlicite
+vrednosti polja imaju razlicito znacenje. Potrebno je
+pronaci OPTIMALAN put kroz lavirint od pocetnog polja, do
+izlaza iz lavirinta, pri cemu se pod putem smatra niz polja
+koja je potrebno posetiti u datom redosledu, da bi se stiglo
+od pocetnog polja do cilja. Pri obilasku lavirinta, sa
+jednog polja je moguce preci na susedno ako ona imaju istu
+ivicu, tj. ako se ono nalazi odmah levo, desno, gore ili
+dole u odnosu na trenutno polje.
+
+Znacenja vrednosti polja su;
+0 = slobodno polje u lavirintu na koje je dozvoljeno stati
+-11 = zid, polje na koje nije dozvoljeno stati
+-99 = izlaz iz lavirinta
+bilo koji pozitivan broj = vrednost blaga na tom polju
+
+Format fajla
+------------------------------------------------------------
+
+Mapa je u fajlu predstavljena na sledeci nacin:
+
+U prvom redu se nalaze dva broja S i V koji predstavljaju
+sirinu i visinu mape.
+
+U sledecih V redova se nalaze po S celih brojeva koji
+predstavljaju vrednosti polja u lavirintu.
+
+Polje (0, 0) nalazi se u gornjem levom polju matrice.
+
+
+Primeri
+------------------------------------------------------------
+
+Za testiranje programa su dati su fajlovi:
+"lav1.txt" i "lav2.txt" u kojima postoji resenje
+"lavp.txt" koji ne sadrzi zidove
+"lavb.txt" u kojem nije moguce naci resenje
+"blago*.txt" za testiranje zadatka sa blagom
+
+
+Zadatak
+============================================================
+
+Napisati klasu LavirintProgram koja ucitava ime fajla u kojem
+se nalazi definisan lavirint, i koordinate pocetne pozicije
+(x, y) od koje se trazi izlaz iz lavirinta.
+
+Nakon toga naci najkraci put do izlaza u lavirintu
+(vrednosti ovde nisu bitne) i ispisati ga na ekran.
+
+Prosiriti nakon toga program tako da nalazi najvredniji
+put u lavirintu - odnosno put kojim ce se pokupiti najvise
+zlatnika, ali put ne sme da sadrzi isto polje dva puta.
+Ispisati i ovaj put na ekran.
+
+
+Pretrazivanje sa vracanjem
+------------------------------------------------------------
+
+Jedan od nacina da se uradi zadatak je koriscenjem
+pretrazivanja sa vracanjem. Prethodno je radjen primer u
+kome se proverava da li put uopste postoji. Ovde je bitno
+naci sve puteve sto je dosta slicno u postavci, samo sto
+treba i dalje traziti druge mogucnosti nakon sto se nadje
+prvo resenje.
+
+Neke od modifikacija u odnosu na samo nalazenje jednog puta:
+
+1. Nakon dolaska na odredjeno polje u lavirintu potrebno je
+to polje ubaciti na kraj trenutnog puta od pocetka lavirinta
+do trenutnog polja
+
+2. Nakon povratka sa polja, potrebno je to polje izabaciti
+sa kraja trenutnog puta
+
+3. Kad se nadje izlaz, potrebno je trenutnu vrednost puta
+uporediti sa do sada najoptimalnijim pronadjenim putem i
+ukoliko je trenutni put bolji, kopirati ga u optimalan put
+
+4. Na kraju svih pretraga, vratiti optimalan put ako postoji
+ili vrednost null ako ne postoji
+
+
+Neobavezne preporuke:
+------------------------------------------------------------
+
+1. Kreirati posebnu klasu Resenje koja ce pamtiti resenje.
+Resenje pamtiti kao niz ili listu polja, od cega za svako
+polje treba zapamtiti koordinate polja i vrednost
+2. Prilikom uporedjivanja resenja, koristiti komparatore
+3. Za racunanje vrednosti puta koristiti metode koje su deo
+klase put (npr. getSize() i getValue())
+
+
+Prosirenje zadatka:
+------------------------------------------------------------
+
+Modifikovati postojece metode za trazenje puta tako da:
+
+- pronalaze put sa najvrednijim blagom pojedinacno
+- pronalaze put na kojem postoji najvise polja sa blagom
+- pronalaze put na kojem postoji najvise uzastopnih polja sa
+ blagom