Lavirint - resenje za najbolji put

diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java
new file mode 100644 (file)
index 0000000..a96bd8c
--- /dev/null
+++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java
@@ -0,0 +1,88 @@
+/**\r
+ * Klasa Lavirint sadrzi nekoliko metoda za trazenje puteva.\r
+ * \r
+ * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore\r
+ * koji se korste pri trazenju najkraceg i najvrednijeg puta.\r
+ */\r
+\r
+import java.util.Comparator;\r
+\r
+public class Lavirint {\r
+\r
+       // Polje m sadrzi kompletnu mapu\r
+       private Mapa m;\r
+       // Polje optResenje sluzi za pamcenje optimalnog resenja\r
+       private Resenje optResenje;\r
+\r
+       // Ucitava mapu iz datog fajla i stampa je na ekran\r
+       Lavirint(String imeFajla) {\r
+               m = Mapa.ucitajIzFajla(imeFajla);\r
+               m.stampaj();\r
+       }\r
+\r
+       // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
+       // koristi komparator po duzini resenja, tj. trazi se najkrace resenje\r
+       // Samo resenje kreira se u metodi optPut\r
+       public Resenje najkraciPut(int x, int y) {\r
+               Resenje r = new Resenje();\r
+               optPut(x, y, r, new KomparatorPoDuzini());\r
+               return optResenje;\r
+       }\r
+\r
+       // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
+       // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje\r
+       // Samo resenje kreira se u metodi optPut\r
+       public Resenje najvrednijiPut(int x, int y) {\r
+               Resenje r = new Resenje();\r
+               optPut(x, y, r, new KomparatorPoVredosti());\r
+               return optResenje;\r
+       }\r
+\r
+       // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem\r
+       // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u\r
+       // optResenje\r
+       // Optimalnost resenja se proverava komparatorom\r
+       private void optPut(int x, int y, Resenje r, Comparator<Resenje> c) {\r
+               if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
+                       return;\r
+               }\r
+               if (m.getPos(x, y)) {\r
+                       return;\r
+               }\r
+               if (m.getMat(x, y) == Mapa.ZID) {\r
+                       return;\r
+               }\r
+               if (m.getMat(x, y) == Mapa.IZLAZ) {\r
+                       r.dodaj(x, y, 0);\r
+                       if (optResenje == null || c.compare(r, optResenje) < 0) {\r
+                               optResenje = r.kopija();\r
+                       }\r
+                       r.izbaciKraj();\r
+                       return;\r
+               }\r
+               \r
+               // pokusavamo da trazimo dalje put\r
+               m.setPos(x, y, true);\r
+               r.dodaj(x, y, m.getMat(x, y));\r
+               optPut(x + 1, y, r, c);\r
+               optPut(x, y + 1, r, c);\r
+               optPut(x, y - 1, r, c);\r
+               optPut(x - 1, y, r, c);\r
+               m.setPos(x, y, false);\r
+               r.izbaciKraj();\r
+       }\r
+}\r
+\r
+// Komparator za resenja po duzini resenja\r
+class KomparatorPoDuzini implements Comparator<Resenje> {\r
+       public int compare(Resenje r1, Resenje r2) {\r
+               return r1.getLength() - r2.getLength();\r
+       }\r
+}\r
+\r
+// Komparator za resenja po vrednosti resenja\r
+class KomparatorPoVredosti implements Comparator<Resenje> {\r
+       public int compare(Resenje r1, Resenje r2) {\r
+               return r2.getVrednost() - r1.getVrednost();\r
+       }\r
+}
\ No newline at end of file

diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java
index a5e8a15..d90f1f2 100644 (file)
--- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java
+++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java
@@ -1,78 +1,89 @@
 public class Mapa {\r
 public class Mapa {\r

- public final static int IZLAZ = -99;\r
- public final static int ZID = -11;\r
- public final static int ERROR = Integer.MIN_VALUE;\r
+       public final static int IZLAZ = -99;\r
+       public final static int ZID = -11;\r
+       public final static int ERROR = Integer.MIN_VALUE;\r

 \r
 \r

- private int visina, sirina;\r
- private int[][] mat;\r
- private boolean[][] pos;\r
+       private int visina, sirina;\r
+       private int[][] mat;\r
+       private boolean[][] pos;\r

 \r
 \r

- public int getSirina() {\r
-  return sirina;\r
- }\r
+       public int getSirina() {\r
+               return sirina;\r
+       }\r

 \r
 \r

- public int getVisina() {\r
-  return visina;\r
- }\r
+       public int getVisina() {\r
+               return visina;\r
+       }\r

 \r
 \r

- public void setPos(int x, int y, boolean b) {\r
-  if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
-   pos[x][y] = b;\r
-  }\r
- }\r
+       public void setPos(int x, int y, boolean b) {\r
+               if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
+                       pos[x][y] = b;\r
+               }\r
+       }\r

 \r
 \r

- public boolean getPos(int x, int y) {\r
-  if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
-   return pos[x][y];\r
-  } else {\r
-   return true;\r
-  }\r
- }\r
+       public boolean getPos(int x, int y) {\r
+               if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
+                       return pos[x][y];\r
+               } else {\r
+                       return true;\r
+               }\r
+       }\r

 \r
 \r

- public int getMat(int x, int y) {\r
-  if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
-   return mat[x][y];\r
-  } else {\r
-   return ERROR;\r
-  }\r
- }\r
+       public int getMat(int x, int y) {\r
+               if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
+                       return mat[x][y];\r
+               } else {\r
+                       return ERROR;\r
+               }\r
+       }\r

 \r
 \r

- public Mapa(int sirina, int visina) {\r
-  this.sirina = sirina;\r
-  this.visina = visina;\r
-  mat = new int[sirina][visina];\r
-  pos = new boolean[sirina][visina];\r
- }\r
+       public Mapa(int sirina, int visina) {\r
+               this.sirina = sirina;\r
+               this.visina = visina;\r
+               mat = new int[sirina][visina];\r
+               pos = new boolean[sirina][visina];\r
+       }\r

 \r
 \r

- public static Mapa ucitajIzFajla(String imeFajla) {\r
-  if (!Svetovid.testIn(imeFajla)) {\r
-   return null;\r
-  }\r
+       public Mapa(String imeFajla) {\r
+               if (!Svetovid.testIn(imeFajla)) {\r
+                       throw new RuntimeException("Fajl za kreiranje mape ("\r
+                               + imeFajla + ") nije prisupacan");\r
+               }\r

 \r
 \r

-  int sirina = Svetovid.in(imeFajla).readInt();\r
-  int visina = Svetovid.in(imeFajla).readInt();\r
-  if (sirina >= 0 && visina >= 0) {\r
-   Mapa res = new Mapa(sirina, visina);\r
-   for (int j = 0; j < visina; j++)\r
-    for (int i = 0; i < sirina; i++)\r
-     res.mat[i][j] = Svetovid.in(imeFajla).readInt();\r
-   Svetovid.closeIn(imeFajla);\r
-   return res;\r
-  } else {\r
-   Svetovid.closeIn(imeFajla);\r
-   return null;\r
-  }\r
- }\r
+               sirina = Svetovid.in(imeFajla).readInt();\r
+               visina = Svetovid.in(imeFajla).readInt();\r
+               mat = new int[sirina][visina];\r
+               pos = new boolean[sirina][visina];\r
+               for (int j = 0; j < visina; j++) {\r
+                       for (int i = 0; i < sirina; i++) {\r
+                               mat[i][j] = Svetovid.in(imeFajla).readInt();\r
+                       }\r
+               }\r
+               Svetovid.closeIn(imeFajla);\r
+       }\r

 \r
 \r

- public void stampaj() {\r
-  if (visina != 0 && sirina != 0) {\r
-   System.out.println(visina + " " + sirina);\r
-   for (int j = 0; j < visina; j++) {\r
-    for (int i = 0; i < sirina; i++) {\r
-     System.out.print(mat[i][j] + "\t");\r
-    }\r
-    System.out.println();\r
-   }\r
-  }\r
- }\r
+       public static Mapa ucitajIzFajla(String imeFajla) {\r
+               if (!Svetovid.testIn(imeFajla)) {\r
+                       return null;\r
+               }\r
+               \r
+               return new Mapa(imeFajla);\r
+\r
+       }\r
+\r
+       public void stampaj() {\r
+               if (visina != 0 && sirina != 0) {\r
+                       System.out.println(visina + " " + sirina);\r
+                       for (int j = 0; j < visina; j++) {\r
+                               for (int i = 0; i < sirina; i++) {\r
+                                       System.out.print(mat[i][j] + "\t");\r
+                               }\r
+                               System.out.println();\r
+                       }\r
+               }\r
+       }\r
+       \r
+       public String toString() {\r
+               return "Mapa velicine " + sirina + " x " + visina;\r
+       }\r

 }\r
 }\r

diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java
new file mode 100644 (file)
index 0000000..f0756b0
--- /dev/null
+++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java
@@ -0,0 +1,44 @@
+/**\r
+ * Program za nalazenje puta u lavirintu.\r
+ * \r
+ * Date su dva varijante problema optimalnog puta, najkraci\r
+ * put i najvredniji put.\r
+ */\r
+\r
+public class NajboljiPut {\r
+\r
+       public static void main(String[] args) {\r
+               Svetovid.out.println("Unesite ime fajla: ");\r
+               String fajl = Svetovid.in.readLine();\r
+               if (!Svetovid.testIn(fajl)) {\r
+                       System.out.println("Greska: nema fajla!");\r
+                       return;\r
+               }\r
+\r
+               Lavirint l = new Lavirint(fajl);\r
+               Resenje r;\r
+\r
+               System.out.println("Unesite koordinate za pocetak:");\r
+               System.out.println("x?");\r
+               int x = Svetovid.in.readInt();\r
+               System.out.println("y?");\r
+               int y = Svetovid.in.readInt();\r
+\r
+               System.out.println("Najkraci put je:");\r
+               r = l.najkraciPut(x, y);\r
+               if (r != null) {\r
+                       r.stampaj();\r
+               } else {\r
+                       System.out.println("Nema resenja");\r
+               }\r
+\r
+               System.out.println("Najvredniji put je:");\r
+               r = l.najvrednijiPut(0, 0);\r
+               if (r != null) {\r
+                       r.stampaj();\r
+                       System.out.println("Vrednost puta: " + r.getVrednost());\r
+               } else {\r
+                       System.out.println("Nema resenja");\r
+               }\r
+       }\r
+}
\ No newline at end of file

diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java
index e29f569..ffb2622 100644 (file)
--- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java
+++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java
@@ -11,62 +11,95 @@ import java.util.ArrayList;
 import java.util.List;\r
 import java.util.Collections;\r
 \r
 import java.util.List;\r
 import java.util.Collections;\r
 \r

-public class Resenje implements Cloneable {\r
- private ArrayList<Polje> polja;\r
+public class Resenje {\r
+       private ArrayList<Polje> polja;\r
+       private List<Polje> nepromenljivaListaPolja;\r

 \r
 \r

- Resenje() {\r
-  polja = new ArrayList<Polje>();\r
- }\r
+       public Resenje() {\r
+               polja = new ArrayList<Polje>();\r
+               nepromenljivaListaPolja = Collections.unmodifiableList(polja);\r
+       }\r
+       \r
+       /**\r
+               Pravi novo resenje sa istim sadrzajem kao original\r
+        */\r
+       public Resenje(Resenje original) {\r
+               // pozovemo "podrazumevani" konstruktor\r
+               this();\r
+               // iskopiramo sva polja iz originala\r
+               for (Polje p : original.getPolja()) {\r
+                       dodaj(p.getX(), p.getY(), p.getV());\r
+               }\r
+       }\r

 \r
 \r

- // Dodaje pulje u resenje\r
- public void dodaj(int x, int y, int v) {\r
-  polja.add(new Polje(x, y, v));\r
- }\r
+       // Dodaje pulje u resenje\r
+       public void dodaj(int x, int y, int v) {\r
+               polja.add(new Polje(x, y, v));\r
+       }\r

 \r
 \r

- // Izbacuje polje iz resenja\r
- public void izbaciKraj() {\r
-  if (getLength() > 0) {\r
-   polja.remove(getLength() - 1);\r
-  } else {\r
-   System.err.println("greska: resenje je vec prazno");\r
-  }\r
- }\r
+       // Izbacuje polje iz resenja\r
+       public void izbaciKraj() {\r
+               if (getLength() > 0) {\r
+                       polja.remove(getLength() - 1);\r
+               } else {\r
+                       System.err.println("greska: resenje je vec prazno");\r
+               }\r
+       }\r

 \r
 \r

- // Stampa resenje\r
- public void stampaj() {\r
-  System.out.println(getLength());\r
-  for (int i = 0; i < getLength(); i++)\r
-   System.out.println(polja.get(i));\r
- }\r
+       // Stampa resenje\r
+       public void stampaj() {\r
+               System.out.println(getLength());\r
+               for (int i = 0; i < getLength(); i++)\r
+                       System.out.println(polja.get(i));\r
+       }\r
+       \r
+       public String toString() {\r
+               StringBuilder sb = new StringBuilder();\r
+               sb.append("Resenje: [ ");\r
+               if (getLength()>0) {\r
+                       sb.append(polja.get(0));\r
+                       for (int i = 1; i < getLength(); i++) {\r
+                               sb.append(", " + polja.get(i));\r
+                       }\r
+               }\r
+               sb.append(" ]");\r
+               \r
+               return sb.toString();\r
+       }\r

 \r
 \r

- // Vraca duzinu resenja\r
- public int getLength() {\r
-  return polja.size();\r
- }\r
+       // Vraca duzinu resenja\r
+       public int getLength() {\r
+               return polja.size();\r
+       }\r

 \r
 \r

- // Vraca i-to polje na putu. Ne koristi se u ovoj verziji zadatka.\r
- // Moze se koristiti za proveru kvaliteta resenja\r
- public Polje getPolje(int i) {\r
-  return polja.get(i);\r
- }\r
+       // Vraca i-to polje na putu. Ne koristi se u ovoj verziji zadatka.\r
+       // Moze se koristiti za proveru kvaliteta resenja\r
+       public Polje getPolje(int i) {\r
+               return polja.get(i);\r
+       }\r

 \r
 \r

- // Kreira klon od resenja\r
- @Override\r
- public Resenje clone() {\r
-  Resenje rez = new Resenje();\r
-  for (Polje p : polja) {\r
-   rez.dodaj(p.getX(), p.getY(), p.getV());\r
-  }\r
-  return rez;\r
- }\r
+       // Vraca sva polja na putu. Ne koristi se u ovoj verziji zadatka.\r
+       // Moze se koristiti za proveru kvaliteta resenja\r
+       public List<Polje> getPolja() {\r
+               return nepromenljivaListaPolja;\r
+       }\r

 \r
 \r

- // Vraca vrednost puta\r
- // Vrednost se definise kao zbir svih vrednosti polja na putu\r
- public int getVrednost() {\r
-  int rez = 0;\r
-  for (Polje p : polja) {\r
-   rez = rez + p.getV();\r
-  }\r
-  return rez;\r
- }\r
+       // Kreira nezavisnu kopiju ovog resenja\r
+       public Resenje kopija() {\r
+               Resenje rez = new Resenje();\r
+               for (Polje p : polja) {\r
+                       rez.dodaj(p.getX(), p.getY(), p.getV());\r
+               }\r
+               return rez;\r
+       }\r
+\r
+       // Vraca vrednost puta\r
+       // Vrednost se definise kao zbir svih vrednosti polja na putu\r
+       public int getVrednost() {\r
+               int rez = 0;\r
+               for (Polje p : polja) {\r
+                       rez = rez + p.getV();\r
+               }\r
+               return rez;\r
+       }\r

 }\r
 }\r