PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/zadatak-najbolji-put.txt

   1 ============================================================
   2       Zadatak - pretrazivanje sa vracanjem - svi putevi
   3 ============================================================
   4
   5
   6 Postavka problema
   7 ============================================================
   8
   9 Neka je dat lavirint kao matrica polja, pri cemu razlicite
  10 vrednosti polja imaju razlicito znacenje. Potrebno je pronaci
  11 OPTIMALAN put kroz lavirint od pocetnog polja, do izlaza iz
  12 lavirinta, pri cemu se pod putem smatra niz polja koja je
  13 potrebno posetiti u datom redosledu, da bi se stiglo od
  14 pocetnog polja do cilja. Pri obilasku lavirinta, sa jednog
  15 polja je moguce preci na susedno ako ona imaju istu ivicu,
  16 tj. ako se ono nalazi odmah levo, desno, gore ili dole u
  17 odnosu na trenutno polje.
  18
  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
  23 bilo koji pozitivan broj = vrednost blaga na tom polju
  24
  25 Format fajla
  26 ------------------------------------------------------------
  27
  28 Mapa je u fajlu predstavljena na sledeci nacin:
  29
  30 U prvom redu se nalaze dva broja S i V koji predstavljaju
  31 sirinu i visinu mape.
  32
  33 U sledecih V redova se nalaze po S celih brojeva koji
  34 predstavljaju vrednosti polja u lavirintu.
  35
  36 Polje (0, 0) nalazi se u gornjem levom polju matrice.
  37
  38
  39 Primeri
  40 ------------------------------------------------------------
  41
  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
  46 "blago*.txt" za testiranje zadatka sa blagom
  47
  48
  49 Zadatak
  50 ============================================================
  51
  52 Napisati klasu LavirintProgram koja ucitava ime fajla u kojem
  53 se nalazi definisan lavirint, koordinate pocetne pozicije
  54 (x, y) od koje se trazi izlaz iz lavirinta, kao i izbor sta
  55 zelimo da radimo. Nakon ucitanog izbora, klasa treba da ucita
  56 lavirint iz datog fajla, ispise ga na ekran i izvrsi izabranu
  57 operaciju.
  58
  59 Ponuditi korisniku sledeci izbor:
  60 3 - ispis najkraceg puta od unetog polja do izlaza
  61 4 - ispis najvrednijeg puta od unetog polja do izlaza
  62
  63
  64 Modifikacija pretrazivanja sa vracanjem
  65 ------------------------------------------------------------
  66
  67 Jedan od nacina da se uradi zadatak je koriscenjem modifikacije
  68 pretrazivanja sa vracanjem. Potrebne modifikacije su sledece:
  69
  70 1. Nakon dolaska na odredjeno polje u lavirintu potrebno je
  71 to polje ubaciti na kraj trenutnog puta od pocetka lavirinta
  72 do trenutnog polja
  73 2. Nakon povratka sa polja, potrebno je to polje izabaciti sa
  74 kraja trenutnog puta
  75 3. Prilikom obilaska izlaza, potrebno je trenutnu vrednost
  76 puta uporediti sa do sada najoptimalnijim pronadjenim putem
  77 i ukoliko je trenutni put bolji, kopirati ga u optimalan put
  78 4. Vratiti optimalan put ako postoji ili vrednost null ako ne
  79 postoji
  80
  81
  82 Neobavezne preporuke:
  83 ------------------------------------------------------------
  84
  85 1. Kreirati posebnu klasu Resenje koja ce pamtiti resenje.
  86 Resenje pamtiti kao niz ili listu polja, od cega za svako
  87 polje treba zapamtiti koordinate polja i vrednost
  88 2. Prilikom uporedjivanja resenja, koristiti komparatore
  89 3. Za racunanje vrednosti puta koristiti metode koje su deo
  90 klase put (npr. getSize() i getValue())
  91
  92
  93 Prosirenje zadatka:
  94 ------------------------------------------------------------
  95
  96 Modifikovati postojece metode za trazenje puta tako da:
  97
  98 - pronalaze put sa najvrednijim blagom pojedinacno
  99 - pronalaze put na kojem postoji najvise polja sa blagom
 100 - pronalaze put na kojem postoji najvise uzastopnih polja sa
 101   blagom