From 5d2538154a96eacb64e24e362003bbe8c61711d7 Mon Sep 17 00:00:00 2001 From: Doni Pracner Date: Sun, 4 Dec 2016 23:50:26 +0100 Subject: [PATCH] Lavirint - resenje za najbolji put --- .../Lavirint/NajboljiPut/Lavirint.java | 88 +++++++++++ .../Lavirint/NajboljiPut/Mapa.java | 143 ++++++++++-------- .../Lavirint/NajboljiPut/NajboljiPut.java | 44 ++++++ .../Lavirint/NajboljiPut/Resenje.java | 133 ++++++++++------ 4 files changed, 292 insertions(+), 116 deletions(-) create mode 100644 PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java create mode 100644 PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java new file mode 100644 index 0000000..a96bd8c --- /dev/null +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Lavirint.java @@ -0,0 +1,88 @@ +/** + * 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 index a5e8a15..d90f1f2 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Mapa.java @@ -1,78 +1,89 @@ public class Mapa { - public final static int IZLAZ = -99; - public final static int ZID = -11; - public final static int ERROR = Integer.MIN_VALUE; + 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; + private int visina, sirina; + private int[][] mat; + private boolean[][] pos; - public int getSirina() { - return sirina; - } + public int getSirina() { + return sirina; + } - public int getVisina() { - return visina; - } + 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 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 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 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(int sirina, int visina) { + this.sirina = sirina; + this.visina = visina; + mat = new int[sirina][visina]; + pos = new boolean[sirina][visina]; + } - public static Mapa ucitajIzFajla(String imeFajla) { - if (!Svetovid.testIn(imeFajla)) { - return null; - } + public Mapa(String imeFajla) { + if (!Svetovid.testIn(imeFajla)) { + throw new RuntimeException("Fajl za kreiranje mape (" + + imeFajla + ") nije prisupacan"); + } - int sirina = Svetovid.in(imeFajla).readInt(); - int visina = Svetovid.in(imeFajla).readInt(); - if (sirina >= 0 && visina >= 0) { - Mapa res = new Mapa(sirina, visina); - for (int j = 0; j < visina; j++) - for (int i = 0; i < sirina; i++) - res.mat[i][j] = Svetovid.in(imeFajla).readInt(); - Svetovid.closeIn(imeFajla); - return res; - } else { - Svetovid.closeIn(imeFajla); - return null; - } - } + 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 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 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 new file mode 100644 index 0000000..f0756b0 --- /dev/null +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java @@ -0,0 +1,44 @@ +/** + * Program za nalazenje puta u lavirintu. + * + * Date su dva varijante problema optimalnog puta, najkraci + * put i najvredniji put. + */ + +public class NajboljiPut { + + public static void main(String[] args) { + Svetovid.out.println("Unesite ime fajla: "); + String fajl = Svetovid.in.readLine(); + if (!Svetovid.testIn(fajl)) { + System.out.println("Greska: nema fajla!"); + return; + } + + Lavirint l = new Lavirint(fajl); + Resenje r; + + System.out.println("Unesite koordinate za pocetak:"); + System.out.println("x?"); + int x = Svetovid.in.readInt(); + System.out.println("y?"); + int y = Svetovid.in.readInt(); + + System.out.println("Najkraci put je:"); + r = l.najkraciPut(x, y); + if (r != null) { + r.stampaj(); + } else { + System.out.println("Nema resenja"); + } + + System.out.println("Najvredniji put je:"); + r = l.najvrednijiPut(0, 0); + if (r != null) { + r.stampaj(); + System.out.println("Vrednost puta: " + r.getVrednost()); + } else { + System.out.println("Nema resenja"); + } + } +} \ No newline at end of file diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java index e29f569..ffb2622 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java +++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/Resenje.java @@ -11,62 +11,95 @@ import java.util.ArrayList; import java.util.List; import java.util.Collections; -public class Resenje implements Cloneable { - private ArrayList polja; +public class Resenje { + private ArrayList polja; + private List nepromenljivaListaPolja; - Resenje() { - polja = new ArrayList(); - } + public Resenje() { + polja = new ArrayList(); + nepromenljivaListaPolja = Collections.unmodifiableList(polja); + } + + /** + Pravi novo resenje sa istim sadrzajem kao original + */ + public Resenje(Resenje original) { + // pozovemo "podrazumevani" konstruktor + this(); + // iskopiramo sva polja iz originala + for (Polje p : original.getPolja()) { + dodaj(p.getX(), p.getY(), p.getV()); + } + } - // Dodaje pulje u resenje - public void dodaj(int x, int y, int v) { - polja.add(new Polje(x, y, v)); - } + // Dodaje pulje u resenje + public void dodaj(int x, int y, int v) { + polja.add(new Polje(x, y, v)); + } - // Izbacuje polje iz resenja - public void izbaciKraj() { - if (getLength() > 0) { - polja.remove(getLength() - 1); - } else { - System.err.println("greska: resenje je vec prazno"); - } - } + // Izbacuje polje iz resenja + public void izbaciKraj() { + if (getLength() > 0) { + polja.remove(getLength() - 1); + } else { + System.err.println("greska: resenje je vec prazno"); + } + } - // Stampa resenje - public void stampaj() { - System.out.println(getLength()); - for (int i = 0; i < getLength(); i++) - System.out.println(polja.get(i)); - } + // Stampa resenje + public void stampaj() { + System.out.println(getLength()); + 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) { + sb.append(polja.get(0)); + for (int i = 1; i < getLength(); i++) { + sb.append(", " + polja.get(i)); + } + } + sb.append(" ]"); + + return sb.toString(); + } - // Vraca duzinu resenja - public int getLength() { - return polja.size(); - } + // Vraca duzinu resenja + public int getLength() { + 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 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); + } - // Kreira klon od resenja - @Override - public Resenje clone() { - Resenje rez = new Resenje(); - for (Polje p : polja) { - rez.dodaj(p.getX(), p.getY(), p.getV()); - } - return rez; - } + // Vraca sva polja na putu. Ne koristi se u ovoj verziji zadatka. + // Moze se koristiti za proveru kvaliteta resenja + public List getPolja() { + return nepromenljivaListaPolja; + } - // Vraca vrednost puta - // Vrednost se definise kao zbir svih vrednosti polja na putu - public int getVrednost() { - int rez = 0; - for (Polje p : polja) { - rez = rez + p.getV(); - } - return rez; - } + // Kreira nezavisnu kopiju ovog resenja + public Resenje kopija() { + Resenje rez = new Resenje(); + for (Polje p : polja) { + rez.dodaj(p.getX(), p.getY(), p.getV()); + } + return rez; + } + + // Vraca vrednost puta + // Vrednost se definise kao zbir svih vrednosti polja na putu + public int getVrednost() { + int rez = 0; + for (Polje p : polja) { + rez = rez + p.getV(); + } + return rez; + } } -- 2.17.1