From: Doni Pracner Date: Sun, 4 Dec 2016 18:58:02 +0000 (+0100) Subject: najbolji put, tekst, cr/lf fix X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=commitdiff_plain;h=e9a069bea132ac74682a92ba56dad7f813992032 najbolji put, tekst, cr/lf fix --- diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt index ba5a83f..88ae9a0 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt @@ -1,111 +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, 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 +============================================================ + 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