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
  11 pronaci OPTIMALAN put kroz lavirint od pocetnog polja, do
  12 izlaza iz lavirinta, pri cemu se pod putem smatra niz polja
  13 koja je potrebno posetiti u datom redosledu, da bi se stiglo
  14 od pocetnog polja do cilja. Pri obilasku lavirinta, sa
  15 jednog polja je moguce preci na susedno ako ona imaju istu
  16 ivicu, tj. ako se ono nalazi odmah levo, desno, gore ili
  17 dole u 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 NajboljiPut koja ucitava ime fajla u kojem
  53 se nalazi definisan lavirint, i koordinate pocetne pozicije
  54 (x, y) od koje se trazi izlaz iz lavirinta.
  55
  56 Nakon toga naci najkraci put do izlaza u lavirintu
  57 (vrednosti ovde nisu bitne) i ispisati ga na ekran.
  58
  59 Prosiriti nakon toga program tako da nalazi najvredniji
  60 put u lavirintu - odnosno put kojim ce se pokupiti najvise
  61 zlatnika, ali put ne sme da sadrzi isto polje dva puta.
  62 Ispisati i ovaj put na ekran.
  63
  64
  65 Pretrazivanje sa vracanjem
  66 ------------------------------------------------------------
  67
  68 Jedan od nacina da se uradi zadatak je koriscenjem
  69 pretrazivanja sa vracanjem. Prethodno je radjen primer u
  70 kome se proverava da li put uopste postoji. Ovde je bitno
  71 naci sve puteve sto je dosta slicno u postavci, samo sto
  72 treba i dalje traziti druge mogucnosti nakon sto se nadje
  73 prvo resenje.
  74
  75 Neke od modifikacija u odnosu na samo nalazenje jednog puta:
  76
  77 1. Nakon dolaska na odredjeno polje u lavirintu potrebno je
  78 to polje ubaciti na kraj trenutnog puta od pocetka lavirinta
  79 do trenutnog polja
  80
  81 2. Nakon povratka sa polja, potrebno je to polje izabaciti
  82 sa kraja trenutnog puta
  83
  84 3. Kad se nadje izlaz, potrebno je trenutnu vrednost puta
  85 uporediti sa do sada najoptimalnijim pronadjenim putem i
  86 ukoliko je trenutni put bolji, kopirati ga u optimalan put
  87
  88 4. Na kraju svih pretraga, vratiti optimalan put ako postoji
  89 ili vrednost null ako ne postoji
  90
  91
  92 Neobavezne preporuke:
  93 ------------------------------------------------------------
  94
  95 1. Kreirati posebnu klasu Resenje koja ce pamtiti resenje.
  96 Resenje pamtiti kao niz ili listu polja, od cega za svako
  97 polje treba zapamtiti koordinate polja i vrednost
  98 2. Prilikom uporedjivanja resenja, koristiti komparatore
  99 3. Za racunanje vrednosti puta koristiti metode koje su deo
 100 klase put (npr. getSize() i getValue())
 101
 102
 103 Prosirenje zadatka:
 104 ------------------------------------------------------------
 105
 106 Modifikovati postojece metode za trazenje puta tako da:
 107
 108 - pronalaze put sa najvrednijim blagom pojedinacno
 109 - pronalaze put na kojem postoji najvise polja sa blagom
 110 - pronalaze put na kojem postoji najvise uzastopnih polja sa
 111   blagom