From 259cc384743122b180e79a962ec0f11634a5b67c Mon Sep 17 00:00:00 2001 From: Doni Pracner Date: Mon, 4 Dec 2017 16:58:10 +0100 Subject: [PATCH] Pojednostavljivanje resenja za NajboljiPut Klasa Resenje se sada zove Put, sto je tacnije za tumacenje zadatka - ne mora uvek biti resenje, a uvek je put. Klasa Polje je integrisana u Put. Put je pojednostavljen, uklonjene su nebitne stvari koje su samo uopstavale klasu za upotrebu van ovog programa. Klasa Lavirint je ujedinjena sa NajboljiPut, tj main metod je sada zajedno sa svim ostalima. Skladistenje matrice i svih ostalih stanja je prebaceno u klasu NajboljiPut, i vise ne postoji odvojena klasa Mapa koja je isto bila uopstenje koje se moglo koristiti i van ovog programa, a nije bilo neophodno. --- .../Lavirint/NajboljiPut/Lavirint.java | 88 ------------- .../Lavirint/NajboljiPut/Mapa.java | 89 ------------- .../Lavirint/NajboljiPut/NajboljiPut.java | 124 +++++++++++++++++- .../Lavirint/NajboljiPut/Polje.java | 30 ----- .../NajboljiPut/{Resenje.java => Put.java} | 70 +++++----- 5 files changed, 158 insertions(+), 243 deletions(-) delete mode 100644 PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java delete mode 100644 PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java delete mode 100644 PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Polje.java rename PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/{Resenje.java => Put.java} (56%) diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java deleted file mode 100644 index a96bd8c..0000000 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java +++ /dev/null @@ -1,88 +0,0 @@ -/** - * Klasa Lavirint sadrzi nekoliko metoda za trazenje puteva. - * - * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore - * koji se korste pri trazenju najkraceg i najvrednijeg puta. - */ - -import java.util.Comparator; - -public class Lavirint { - - // Polje m sadrzi kompletnu mapu - private Mapa m; - // Polje optResenje sluzi za pamcenje optimalnog resenja - private Resenje optResenje; - - // Ucitava mapu iz datog fajla i stampa je na ekran - Lavirint(String imeFajla) { - m = Mapa.ucitajIzFajla(imeFajla); - m.stampaj(); - } - - // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja - // koristi komparator po duzini resenja, tj. trazi se najkrace resenje - // Samo resenje kreira se u metodi optPut - public Resenje najkraciPut(int x, int y) { - Resenje r = new Resenje(); - optPut(x, y, r, new KomparatorPoDuzini()); - return optResenje; - } - - // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja - // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje - // Samo resenje kreira se u metodi optPut - public Resenje najvrednijiPut(int x, int y) { - Resenje r = new Resenje(); - optPut(x, y, r, new KomparatorPoVredosti()); - return optResenje; - } - - // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem - // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u - // optResenje - // Optimalnost resenja se proverava komparatorom - private void optPut(int x, int y, Resenje r, Comparator c) { - if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) { - return; - } - if (m.getPos(x, y)) { - return; - } - if (m.getMat(x, y) == Mapa.ZID) { - return; - } - if (m.getMat(x, y) == Mapa.IZLAZ) { - r.dodaj(x, y, 0); - if (optResenje == null || c.compare(r, optResenje) < 0) { - optResenje = r.kopija(); - } - r.izbaciKraj(); - return; - } - - // pokusavamo da trazimo dalje put - m.setPos(x, y, true); - r.dodaj(x, y, m.getMat(x, y)); - optPut(x + 1, y, r, c); - optPut(x, y + 1, r, c); - optPut(x, y - 1, r, c); - optPut(x - 1, y, r, c); - m.setPos(x, y, false); - r.izbaciKraj(); - } -} - -// Komparator za resenja po duzini resenja -class KomparatorPoDuzini implements Comparator { - public int compare(Resenje r1, Resenje r2) { - return r1.getLength() - r2.getLength(); - } -} - -// Komparator za resenja po vrednosti resenja -class KomparatorPoVredosti implements Comparator { - public int compare(Resenje r1, Resenje r2) { - return r2.getVrednost() - r1.getVrednost(); - } -} \ No newline at end of file diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java deleted file mode 100644 index d90f1f2..0000000 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java +++ /dev/null @@ -1,89 +0,0 @@ -public class Mapa { - public final static int IZLAZ = -99; - public final static int ZID = -11; - public final static int ERROR = Integer.MIN_VALUE; - - private int visina, sirina; - private int[][] mat; - private boolean[][] pos; - - public int getSirina() { - return sirina; - } - - public int getVisina() { - return visina; - } - - public void setPos(int x, int y, boolean b) { - if (0 <= x && x < sirina && 0 <= y && y < visina) { - pos[x][y] = b; - } - } - - public boolean getPos(int x, int y) { - if (0 <= x && x < sirina && 0 <= y && y < visina) { - return pos[x][y]; - } else { - return true; - } - } - - public int getMat(int x, int y) { - if (0 <= x && x < sirina && 0 <= y && y < visina) { - return mat[x][y]; - } else { - return ERROR; - } - } - - public Mapa(int sirina, int visina) { - this.sirina = sirina; - this.visina = visina; - mat = new int[sirina][visina]; - pos = new boolean[sirina][visina]; - } - - public Mapa(String imeFajla) { - if (!Svetovid.testIn(imeFajla)) { - throw new RuntimeException("Fajl za kreiranje mape (" - + imeFajla + ") nije prisupacan"); - } - - sirina = Svetovid.in(imeFajla).readInt(); - visina = Svetovid.in(imeFajla).readInt(); - mat = new int[sirina][visina]; - pos = new boolean[sirina][visina]; - for (int j = 0; j < visina; j++) { - for (int i = 0; i < sirina; i++) { - mat[i][j] = Svetovid.in(imeFajla).readInt(); - } - } - Svetovid.closeIn(imeFajla); - } - - public static Mapa ucitajIzFajla(String imeFajla) { - if (!Svetovid.testIn(imeFajla)) { - return null; - } - - return new Mapa(imeFajla); - - } - - public void stampaj() { - if (visina != 0 && sirina != 0) { - System.out.println(visina + " " + sirina); - for (int j = 0; j < visina; j++) { - for (int i = 0; i < sirina; i++) { - System.out.print(mat[i][j] + "\t"); - } - System.out.println(); - } - } - } - - public String toString() { - return "Mapa velicine " + sirina + " x " + visina; - } -} diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java index f0756b0..b178b78 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java @@ -1,12 +1,112 @@ + /** - * Program za nalazenje puta u lavirintu. + * Klasa NajboljiPut sadrzi nekoliko metoda za trazenje puteva. * - * Date su dva varijante problema optimalnog puta, najkraci - * put i najvredniji put. + * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore + * koji se korste pri trazenju najkraceg i najvrednijeg puta. */ +import java.util.Comparator; + public class NajboljiPut { + // Konstante za polja u mapi + public final static int IZLAZ = -99; + public final static int ZID = -11; + + // interno predstavljanje mape + private int visina, sirina; + private int[][] mat; + // matrica posecenih polja + private boolean[][] pos; + + // Polje optResenje sluzi za pamcenje optimalnog resenja + private Put optResenje; + + // Ucitava mapu iz datog fajla i stampa je na ekran + NajboljiPut(String imeFajla) { + if (!Svetovid.testIn(imeFajla)) { + throw new RuntimeException("Fajl za kreiranje mape (" + imeFajla + ") nije prisupacan"); + } + + sirina = Svetovid.in(imeFajla).readInt(); + visina = Svetovid.in(imeFajla).readInt(); + mat = new int[sirina][visina]; + pos = new boolean[sirina][visina]; + for (int j = 0; j < visina; j++) { + for (int i = 0; i < sirina; i++) { + mat[i][j] = Svetovid.in(imeFajla).readInt(); + } + } + Svetovid.closeIn(imeFajla); + + stampajMapu(); + } + + private void stampajMapu() { + if (visina > 0 && sirina > 0) { + System.out.println(visina + " " + sirina); + for (int j = 0; j < visina; j++) { + for (int i = 0; i < sirina; i++) { + System.out.print(mat[i][j] + "\t"); + } + System.out.println(); + } + } + } + + // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja + // koristi komparator po duzini resenja, tj. trazi se najkrace resenje + // Samo resenje kreira se u metodi optPut + public Put najkraciPut(int x, int y) { + Put r = new Put(); + optPut(x, y, r, new KomparatorPoDuzini()); + return optResenje; + } + + // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja + // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje + // Samo resenje kreira se u metodi optPut + public Put najvrednijiPut(int x, int y) { + Put r = new Put(); + optPut(x, y, r, new KomparatorPoVredosti()); + return optResenje; + } + + // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem + // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u + // optResenje + // Optimalnost resenja se proverava komparatorom + private void optPut(int x, int y, Put r, Comparator c) { + if (x < 0 || x >= sirina || y < 0 || y >= visina) { + return; + } + if (pos[x][y]) { + return; + } + if (mat[x][y] == ZID) { + return; + } + if (mat[x][y] == IZLAZ) { + r.dodaj(x, y, 0); + if (optResenje == null || c.compare(r, optResenje) < 0) { + optResenje = r.kopija(); + } + r.izbaciKraj(); + return; + } + + // pokusavamo da trazimo dalje put + pos[x][y] = true; + r.dodaj(x, y, mat[x][y]); + optPut(x + 1, y, r, c); + optPut(x, y + 1, r, c); + optPut(x, y - 1, r, c); + optPut(x - 1, y, r, c); + pos[x][y] = false; + r.izbaciKraj(); + } + public static void main(String[] args) { Svetovid.out.println("Unesite ime fajla: "); String fajl = Svetovid.in.readLine(); @@ -15,8 +115,8 @@ public class NajboljiPut { return; } - Lavirint l = new Lavirint(fajl); - Resenje r; + NajboljiPut l = new NajboljiPut(fajl); + Put r; System.out.println("Unesite koordinate za pocetak:"); System.out.println("x?"); @@ -41,4 +141,18 @@ public class NajboljiPut { System.out.println("Nema resenja"); } } +} + +// Komparator za resenja po duzini resenja +class KomparatorPoDuzini implements Comparator { + public int compare(Put r1, Put r2) { + return r1.getLength() - r2.getLength(); + } +} + +// Komparator za resenja po vrednosti resenja +class KomparatorPoVredosti implements Comparator { + public int compare(Put r1, Put r2) { + return r2.getVrednost() - r1.getVrednost(); + } } \ No newline at end of file diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Polje.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Polje.java deleted file mode 100644 index c40fc5f..0000000 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Polje.java +++ /dev/null @@ -1,30 +0,0 @@ -/** - * Klasa Polje se koristi za pamcenje x i y koordinata nekog polja, kao i - * vrednosti na toj poziciji u mapi - */ - -public class Polje { - private int x, y, v; - - Polje(int x, int y, int v) { - this.x = x; - this.y = y; - this.v = v; - } - - public int getX() { - return x; - } - - public int getY() { - return y; - } - - public int getV() { - return v; - } - - public String toString() { - return x + " " + y + " " + v; - } -} \ No newline at end of file diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Put.java similarity index 56% rename from PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java rename to PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Put.java index ffb2622..41c7de2 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Put.java @@ -1,33 +1,27 @@ + /** - * Klasa Resenje koristi se za pamcenje pronadjenog puta. + * Klasa Put koristi se za pamcenje pronadjenog puta. * * Polje Polja se koristi za pamcenje svih polja na putu. * - * Polje nepromenljivaListaPolja je dodata da se omoguci - * pristup poljima resenja "spolja" (za proveru kvaliteta puta na primer), - * ali tako da ne moze da se utice na sam sadrzaj te liste. */ import java.util.ArrayList; -import java.util.List; -import java.util.Collections; -public class Resenje { +public class Put { private ArrayList polja; - private List nepromenljivaListaPolja; - public Resenje() { + public Put() { polja = new ArrayList(); - nepromenljivaListaPolja = Collections.unmodifiableList(polja); } - + /** - Pravi novo resenje sa istim sadrzajem kao original + * Pravi novo resenje sa istim sadrzajem kao original */ - public Resenje(Resenje original) { + public Put(Put original) { // pozovemo "podrazumevani" konstruktor this(); // iskopiramo sva polja iz originala - for (Polje p : original.getPolja()) { + for (Polje p : original.polja) { dodaj(p.getX(), p.getY(), p.getV()); } } @@ -52,18 +46,18 @@ public class Resenje { for (int i = 0; i < getLength(); i++) System.out.println(polja.get(i)); } - + public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Resenje: [ "); - if (getLength()>0) { + if (getLength() > 0) { sb.append(polja.get(0)); for (int i = 1; i < getLength(); i++) { sb.append(", " + polja.get(i)); } } sb.append(" ]"); - + return sb.toString(); } @@ -72,21 +66,9 @@ public class Resenje { return polja.size(); } - // Vraca i-to polje na putu. Ne koristi se u ovoj verziji zadatka. - // Moze se koristiti za proveru kvaliteta resenja - public Polje getPolje(int i) { - return polja.get(i); - } - - // Vraca sva polja na putu. Ne koristi se u ovoj verziji zadatka. - // Moze se koristiti za proveru kvaliteta resenja - public List getPolja() { - return nepromenljivaListaPolja; - } - // Kreira nezavisnu kopiju ovog resenja - public Resenje kopija() { - Resenje rez = new Resenje(); + public Put kopija() { + Put rez = new Put(); for (Polje p : polja) { rez.dodaj(p.getX(), p.getY(), p.getV()); } @@ -102,4 +84,30 @@ public class Resenje { } return rez; } + + public class Polje { + private int x, y, v; + + Polje(int x, int y, int v) { + this.x = x; + this.y = y; + this.v = v; + } + + public int getX() { + return x; + } + + public int getY() { + return y; + } + + public int getV() { + return v; + } + + public String toString() { + return x + " " + y + " " + v; + } + } } -- 2.17.1