X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?a=blobdiff_plain;f=PretrazivanjeSaVracanjem%2FLavirint%2FNajboljiPut%2Fzadatak-najbolji-put.txt;h=c0e14c35c31f0e3bce161b92d8824349618d19fd;hb=3104c260a16cb5de854a4a3669a4c9f47cd1c736;hp=8c1d6a5df82871542a53d60b910b238009559ba3;hpb=572437043c8e9dd5343cdda3a656f2c8f7a638ae;p=spa2-materijali.git diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt index 8c1d6a5..c0e14c3 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt @@ -1,101 +1,111 @@ -============================================================ - 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, koordinate pocetne pozicije -(x, y) od koje se trazi izlaz iz lavirinta, kao i izbor sta -zelimo da radimo. Nakon ucitanog izbora, klasa treba da ucita -lavirint iz datog fajla, ispise ga na ekran i izvrsi izabranu -operaciju. - -Ponuditi korisniku sledeci izbor: -3 - ispis najkraceg puta od unetog polja do izlaza -4 - ispis najvrednijeg puta od unetog polja do izlaza - - -Modifikacija pretrazivanja sa vracanjem ------------------------------------------------------------- - -Jedan od nacina da se uradi zadatak je koriscenjem modifikacije -pretrazivanja sa vracanjem. Potrebne modifikacije su sledece: - -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. Prilikom obilaska izlaza, potrebno je trenutnu vrednost -puta uporediti sa do sada najoptimalnijim pronadjenim putem -i ukoliko je trenutni put bolji, kopirati ga u optimalan put -4. 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 +============================================================ + 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 NajboljiPut 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