API tools faq
paste
Advertisement
jovanovski

ВИ DFS/BFS

jovanovski
May 13th, 2013
379
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 28.65 KB | None | 0 0
raw download clone embed print report
  1. import java.io.IOException;
  2. import java.util.Collections;
  3. import java.util.Collection;
  4. import java.util.HashMap;
  5. import java.util.Iterator;
  6. import java.util.LinkedList;
  7. import java.util.Random;
  8. import java.util.TreeSet;
  9.  
  10. //Pomosna sostojba koja ovozmozuva navrakjanje po cekori nanazad vo rekurziven algoritam
  11. class pomosnaSostojba {
  12.     pomosnaSostojba parent;
  13.     Sostojba node;
  14.  
  15.     pomosnaSostojba(pomosnaSostojba pomosenNode, Sostojba nod) {
  16.         this.parent = pomosenNode;
  17.         this.node = nod;
  18.     }
  19.  
  20.     public String toString() {
  21.         return node.toString() + "";
  22.     }
  23.  
  24. }
  25.  
  26. //Momentalna sostojba kaj hanojski kuli so 3 kuli
  27. class Sostojba implements Comparable {
  28.     HanojskaKula h1;
  29.     HanojskaKula h2;
  30.     HanojskaKula h3;
  31.  
  32.     Sostojba(HanojskaKula h1, HanojskaKula h2, HanojskaKula h3) {
  33.         this.h1 = h1;
  34.         this.h2 = h2;
  35.         this.h3 = h3;
  36.  
  37.     }
  38.  
  39.     public int compareTo(Sostojba o) {
  40.  
  41.         o = (Sostojba) o;
  42.         String cmp = h1.plocki.toString() + " " + h2.plocki.toString() + " "
  43.                 + h3.plocki.toString();
  44.         String cmp2 = o.h1.plocki.toString() + " " + o.h2.plocki.toString()
  45.                 + " " + o.h3.plocki.toString();
  46.  
  47.         return cmp.compareTo(cmp2);
  48.     }
  49.  
  50.     public boolean equals(Object obj) {
  51.         if (this.compareTo((Sostojba) obj) == 0)
  52.             return true;
  53.         return false;
  54.     }
  55.  
  56.     @Override
  57.     public int compareTo(Object o) {
  58.         return this.compareTo((Sostojba) o);
  59.     }
  60.  
  61.     public String toString() {
  62.         return "Sostojba: \n" + h1.plocki.toString() + "\n"
  63.                 + h2.plocki.toString() + "\n" + h3.plocki.toString() + "\n";
  64.     }
  65.  
  66. }
  67.  
  68. //Implementacija na kula so ID, i lista od plocki (int)
  69. class HanojskaKula implements Cloneable {
  70.     LinkedList<Integer> plocki;
  71.     String id;
  72.  
  73.     HanojskaKula(String id) {
  74.         plocki = new LinkedList<Integer>();
  75.         this.id = id;
  76.     }
  77.  
  78.     public void add(int plocka) {
  79.         plocki.add(plocka);
  80.     }
  81.  
  82.     public void remove() {
  83.         plocki.remove();
  84.     }
  85.  
  86. }
  87.  
  88. //Lavirit pretstaven vo patrica
  89. class Lavirint {
  90.     char[][] matrix;
  91.     int w;
  92.     int h;
  93.  
  94.     //Konstruktor so sirina i visina na lavirintot, koj povikuva funkcija za generiranje na istiot
  95.     Lavirint(int w, int h) {
  96.         this.w = w;
  97.         this.h = h;
  98.         matrix = new char[w][h];
  99.         randomize();
  100.     }
  101.  
  102.     //Funkcija koja so verojatnost 0.6 postavuva prolaz na edno pole, a so verojatnost 0.4 postavuva blokada
  103.     public void randomize() {
  104.         Random rand = new Random();
  105.         for (int i = 0; i < w; i++) {
  106.             for (int j = 0; j < h; j++) {
  107.                 int n = rand.nextInt(10);
  108.                 if (i == 0 && j == 0) {
  109.                     matrix[i][j] = '.';
  110.                 } else if (i == w - 1 && j == h - 1) {
  111.                     matrix[i][j] = '.';
  112.                 } else if (n >= 0 && n <= 6) {
  113.                     // prolaz
  114.                     matrix[i][j] = '.';
  115.                 } else {
  116.                     // blok
  117.                     matrix[i][j] = '|';
  118.                 }
  119.             }
  120.         }
  121.  
  122.     }
  123.  
  124.     public void printMatrix() {
  125.         for (int i = 0; i < w; i++) {
  126.             for (int j = 0; j < h; j++) {
  127.                 System.out.print(matrix[i][j] + " ");
  128.             }
  129.             System.out.println();
  130.         }
  131.         System.out.println("\n\n\n");
  132.     }
  133.  
  134.     //Generiranje na orientiran graf od dobieniot lavirint
  135.     public Graph makeGraph() {
  136.         LinkedList<Node> nodes = new LinkedList<Node>();
  137.  
  138.         int brojac = 2;
  139.         for (int i = 0; i < w; i++) {
  140.             for (int j = 0; j < h; j++) {
  141.                 if (i == 0 && j == 0) {
  142.                     nodes.add(new Node(1));
  143.                 } else if (i == w - 1 && j == h - 1) {
  144.                     nodes.add(new Node(w * h));
  145.                 } else {
  146.                     nodes.add(new Node(brojac++));
  147.                 }
  148.             }
  149.         }
  150.  
  151.         Graph graf = new Graph(nodes);
  152.         graf.setRoot(nodes.getFirst());
  153.         for (int i = 0; i < w; i++) {
  154.             for (int j = 0; j < h; j++) {
  155.                 if (matrix[i][j] == '.') {
  156.                     int index = i * w + j;
  157.                     // proveri desno
  158.                     if (j < h - 1 && matrix[i][j + 1] == '.') {
  159.                         // System.out.println(index + " ima sosed desno");
  160.                         graf.connectNodes(nodes.get(index),
  161.                                 nodes.get(index + 1));
  162.                     }
  163.  
  164.                     // proveri dole
  165.                     if (i < w - 1 && matrix[i + 1][j] == '.') {
  166.                         // System.out.println(index + " ima sosed dole");
  167.                         graf.connectNodes(nodes.get(index),
  168.                                 nodes.get(index + w));
  169.                     }
  170.  
  171.                     // proveri gore
  172.                     if (i > 0 && matrix[i - 1][j] == '.') {
  173.                         // System.out.println(index + " ima sosed gore");
  174.                         graf.connectNodes(nodes.get(index),
  175.                                 nodes.get(index - w));
  176.                     }
  177.  
  178.                     // proveri levo
  179.                     if (j > 0 && matrix[i][j - 1] == '.') {
  180.                         // System.out.println(index + " ima sosed levo");
  181.                         graf.connectNodes(nodes.get(index),
  182.                                 nodes.get(index - 1));
  183.                     }
  184.                 }
  185.             }
  186.         }
  187.  
  188.         return graf;
  189.     }
  190.  
  191. }
  192.  
  193. class Node {
  194.     LinkedList<Node> neighbours;
  195.     int value;
  196.  
  197.     // Konstruktor
  198.     Node(int value) {
  199.         neighbours = new LinkedList<Node>();
  200.         this.value = value;
  201.     }
  202.  
  203.     // Konstrukor so sosedi (po potreba)
  204.     Node(LinkedList<Node> neighbours, int value) {
  205.         neighbours = new LinkedList<Node>();
  206.         Iterator<Node> a = neighbours.iterator();
  207.         while (a.hasNext()) {
  208.             this.neighbours.add(a.next());
  209.         }
  210.         this.value = value;
  211.     }
  212.  
  213.     // Vrati ja listata na sosedi na ova teme
  214.     public LinkedList<Node> getNeighbours() {
  215.         return this.neighbours;
  216.     }
  217.  
  218.     // Dodadi sosed
  219.     public void addNeighbour(Node ne) {
  220.         this.neighbours.add(ne);
  221.     }
  222.  
  223.     // Izbrisi sosed (po potreba)
  224.     public void removeNeighbour(Node ne) {
  225.         if (this.neighbours.contains(ne))
  226.             this.neighbours.remove(ne);
  227.     }
  228.  
  229.     // Tostring override
  230.     public String toString() {
  231.         return "" + value;
  232.     }
  233.  
  234. }
  235.  
  236. class Graph {
  237.     Node root;
  238.     LinkedList<Node> nodes;
  239.  
  240.     // Konstruktor
  241.     Graph(LinkedList<Node> nodes) {
  242.         this.nodes = new LinkedList<Node>();
  243.         Iterator<Node> a = nodes.iterator();
  244.         while (a.hasNext()) {
  245.             this.nodes.add(a.next());
  246.         }
  247.     }
  248.  
  249.     // Postavi go korenot vo grafot
  250.     public void setRoot(Node root) {
  251.         this.root = root;
  252.     }
  253.  
  254.     // Vrati indeks na node so odredena vrednost
  255.     // Nodovi nemozat da imaat ista int vrenost
  256.     public int findNode(int value) {
  257.         int i = 0;
  258.         Iterator<Node> a = nodes.iterator();
  259.         while (a.hasNext()) {
  260.             Node tmp = a.next();
  261.             if (tmp.value == value)
  262.                 return i;
  263.             i++;
  264.         }
  265.         return -1;
  266.     }
  267.  
  268.     // Povrzi 2 nodovi
  269.     public void connectNodes(Node n1, Node n2) {
  270.         int index1 = findNode(n1.value);
  271.         int index2 = findNode(n2.value);
  272.         nodes.get(index1).addNeighbour(n2);
  273.     }
  274.  
  275. }
  276.  
  277. //Pomosen jazol so parent pointer koj ni dozvoluva da se navrakjame nanazad vo rekurzivni algoritmi
  278. class pomosenNode {
  279.     pomosenNode parent;
  280.     Node node;
  281.  
  282.     pomosenNode(pomosenNode pomosenNode, Node nod) {
  283.         this.parent = pomosenNode;
  284.         this.node = nod;
  285.     }
  286.  
  287.     public String toString() {
  288.         return node.value + "";
  289.     }
  290.  
  291. }
  292.  
  293. public class DFS {
  294.     public static void main(String[] args) throws IOException {
  295.         System.out
  296.                 .println("Zdravo, jas sum Gorjan Jovanovski, i ova e mojata domasna.");
  297.  
  298.         System.out
  299.                 .println("Sledat demonstracii na DFS iterativno, rekurzivno, DFS Deepening, BFS, resenie na primer 1, resenie na lavirint i hanojskite kuli.");
  300.  
  301.         System.out.print("Pritisnete koe bilo kopce za DFS Iterativno.");
  302.         System.in.read();
  303.         System.in.read();
  304.         // Kreiraj lista na teminja
  305.         LinkedList<Node> teminja = new LinkedList<Node>();
  306.  
  307.         // Kreiraj teminja so soodvetni int vrednost
  308.         Node n1 = new Node(1);
  309.         Node n2 = new Node(2);
  310.         Node n3 = new Node(3);
  311.         Node n4 = new Node(4);
  312.  
  313.         // Dodaj gi vo listata
  314.         teminja.add(n1);
  315.         teminja.add(n2);
  316.         teminja.add(n3);
  317.         teminja.add(n4);
  318.  
  319.         // Kreiraj graf so listata
  320.         Graph graf = new Graph(teminja);
  321.  
  322.         // Postavi koj e korenot na grafot (od kaj da pocne prebaruvanjeto)
  323.         graf.setRoot(n1); // Nivo 1
  324.  
  325.         // Povrzi gi nodovite 1 i 2
  326.         graf.connectNodes(n1, n2); // Nivo 2
  327.  
  328.         // Povrzi gi nodovite 1 i 3
  329.         graf.connectNodes(n1, n3); // Nivo 2
  330.  
  331.         // Povrzi gi nodovite 3 i 4
  332.         graf.connectNodes(n3, n4); // Nivo 3
  333.  
  334.         // Prebaraj vo grafot za dadena int vrednost so DFS
  335.         // graf, barana vrednost, maks dlabovina
  336.         System.out.println("DFS Iterativno");
  337.         DFS_Iterativen_Dlabocina(graf, 4, 3);
  338.  
  339.         System.out.print("\n\nPritisnete koe bilo kopce za DFS Rekurzivno.");
  340.         System.in.read();
  341.         System.in.read();
  342.         // Prebaraj so DFS rekurzivno so maks dlabocina
  343.         // poceten jazol, barana vrednost, segasna dlabocina, maks dlabocina
  344.         System.out.println("\nDFS Rekurzivno");
  345.         DFS_Rekurziven_Dlabocina(graf.root, 4, 1, 3);
  346.  
  347.         System.out.print("\n\nPritisnete koe bilo kopce za BFS Iterativno.");
  348.         System.in.read();
  349.         System.in.read();
  350.         // Prebaraj vo grafot za dadena int vrednost so BFS
  351.         // graf, barana vrednost, maks dlabovina
  352.         System.out.println("\nBFS Iterativno");
  353.         BFS_Iterativen_Dlabocina(graf, 4);
  354.  
  355.         System.out
  356.                 .print("\n\nPritisnete koe bilo kopce za DFS Iterative Deepening.");
  357.         System.in.read();
  358.         System.in.read();
  359.         // Prebaraj so iterative deepeing DFS
  360.         System.out.println("\nDFS Iterative Deep");
  361.         DFS_Iterative_Deep(graf, 4, 3);
  362.  
  363.         System.out
  364.                 .print("\n\nPritisnete koe bilo kopce za resavanje na primer 1.");
  365.         System.in.read();
  366.         System.in.read();
  367.  
  368.         // Resi primer 1 so BFS
  369.         primer1();
  370.  
  371.         System.out
  372.                 .print("\n\nPritisnete koe bilo kopce za resavanje na lavirint.");
  373.         System.in.read();
  374.         System.in.read();
  375.  
  376.         // Lavirint - bara od poleto gore levo do poleto dole desno
  377.         System.out.println("\n\n-----------LAVIRINT---------\n\n");
  378.         // Lavirint redici
  379.  
  380.         int lavw = 5;
  381.         // Lavirint koloni
  382.         int lavh = 5;
  383.         // Init
  384.         Lavirint lavirint = new Lavirint(lavw, lavh);
  385.         // Kako izgleda generiraniot lavirit
  386.         lavirint.printMatrix();
  387.         // Kreiraj graf
  388.         Graph lavgraf = lavirint.makeGraph();
  389.         // DFS (do dlabocina 100, po potreba se zgolemuva)
  390.         // Printa lista od koe na koe teme treba da ide, ako najde rez
  391.         System.out.println("\n\n Sega so DFS ke go resime: \n");
  392.  
  393.         LinkedList<Node> rez = DFS_Iterativen_Dlabocina(lavgraf, lavw * lavh,
  394.                 100);
  395.         if (rez != null)
  396.             System.out.println(rez.toString());
  397.  
  398.         // BFS
  399.  
  400.         System.out.println("\n\n Sega so BFS ke go resime: \n");
  401.         BFS_Iterativen_Dlabocina_Multivalue(lavgraf, lavw * lavh, 0);
  402.  
  403.         System.out
  404.                 .print("\n\nPritisnete koe bilo kopce za resavanje na hajoski.");
  405.         System.in.read();
  406.         System.in.read();
  407.  
  408.         // Hanoj
  409.         hanoj(3);
  410.         System.out.println("\nToa e toa, pozdrav :)");
  411.     }
  412.  
  413.     //Izminati sostojbi kaj hanojskite kuli
  414.     static LinkedList<Sostojba> izminatiSostojbi;
  415.    
  416.     //Lista na pomosni sostojbi od kaj sto ke se vratime na tocnata pateka
  417.     static LinkedList<pomosnaSostojba> pateka;
  418.  
  419.     public static void hanoj(int n) {
  420.         //Inicijalizacija na patekata
  421.         pateka = new LinkedList<pomosnaSostojba>();
  422.        
  423.         //Inicijalizacija na izminatite sostojbi
  424.         izminatiSostojbi = new LinkedList<Sostojba>();
  425.        
  426.         //Kreiranje na prvata hanojska sostojba so struktura
  427.         //[3,2,1]
  428.         //[]
  429.         //[]
  430.         HanojskaKula h1 = new HanojskaKula("1");
  431.         h1.add(3);
  432.         h1.add(2);
  433.         h1.add(1);
  434.         HanojskaKula h2 = new HanojskaKula("2");
  435.         HanojskaKula h3 = new HanojskaKula("3");
  436.        
  437.         //Kreiranje sostojba od 3te hanojski kuli
  438.         Sostojba pocetok = new Sostojba(h1, h2, h3);
  439.        
  440.         //Dodavanje na sostojbata vo patekata
  441.         pateka.push(new pomosnaSostojba(null, pocetok));
  442.        
  443.         //Kreiranje na krajnata hanojska sostojba so struktura
  444.         //[]
  445.         //[3,2,1]
  446.         //[]
  447.         HanojskaKula h11 = new HanojskaKula("1");
  448.         HanojskaKula h12 = new HanojskaKula("2");
  449.         h12.add(3);
  450.         h12.add(2);
  451.         h12.add(1);
  452.         HanojskaKula h13 = new HanojskaKula("3");
  453.        
  454.         //Krekiranje krajna sostojba
  455.         Sostojba kraj = new Sostojba(h11, h12, h13);
  456.        
  457.         System.out.println("\n\nPocetna sostojba: ");
  458.         System.out.println(pocetok);
  459.        
  460.         System.out.println("Krajna sostojba: ");
  461.         System.out.println(kraj);
  462.        
  463.         //Dodavaje na pocetokot kako izminata sostojba
  464.         izminatiSostojbi.add(pocetok);
  465.        
  466.         //Povikuvanje na DFS so parametri pocetok i kraj  (t.e. segasna sostojba i krajna)
  467.         hanojDFS(pocetok, kraj);
  468.     }
  469.  
  470.     //Ja optimizira patekata sto ja nasol DFS-to otstranuvajki nepotrebni cekori
  471.     public static void ekstraCekori(LinkedList<pomosnaSostojba> lista) {
  472.  
  473.         /* Za sekoj 3 posledovatelni cekori, proveri dali prvite brojki im se isti negde, i ako se kikni go sredniot cekor
  474.          *  primer:
  475.          *  Sostojba 1:
  476.          *  [3,2,1]
  477.          *  []
  478.          *  []
  479.          *  
  480.          *  Sostojba 2:
  481.          *  [3,2]
  482.          *  [1]
  483.          *  []
  484.          *  Sostojba 3:
  485.          *  [3,2]
  486.          *  []
  487.          *  [1]
  488.          *  
  489.          *  Sredniot cekor e nepotreben, i pritoa ke go isfrlime za optimizacija na rezultatot, sepak DFS vrakja tocen no neoptimalen rezultat
  490.          */
  491.                 for (int i = 0; i < lista.size() - 2; i++) {
  492.             boolean skok = false;
  493.             int kaj = 0;
  494.             if (!lista.get(i).node.h1.plocki.isEmpty()
  495.                     && !lista.get(i + 1).node.h2.plocki.isEmpty()
  496.                     && !lista.get(i + 2).node.h3.plocki.isEmpty())
  497.                 if (lista.get(i).node.h1.plocki.getLast() == lista.get(i + 1).node.h2.plocki
  498.                         .getLast()
  499.                         && lista.get(i + 1).node.h2.plocki.getLast() == lista
  500.                                 .get(i + 2).node.h3.plocki.getLast()) {
  501.                     skok = true;
  502.                     kaj=1;
  503.                 }
  504.  
  505.             if (!lista.get(i).node.h1.plocki.isEmpty()
  506.                     && !lista.get(i + 2).node.h2.plocki.isEmpty()
  507.                     && !lista.get(i + 1).node.h3.plocki.isEmpty())
  508.                 if (lista.get(i).node.h1.plocki.getLast() == lista.get(i + 2).node.h2.plocki
  509.                         .getLast()
  510.                         && lista.get(i + 2).node.h2.plocki.getLast() == lista
  511.                                 .get(i + 1).node.h3.plocki.getLast()) {
  512.                     skok = true;
  513.                     kaj=2;
  514.                 }
  515.  
  516.             if (!lista.get(i + 1).node.h1.plocki.isEmpty()
  517.                     && !lista.get(i).node.h2.plocki.isEmpty()
  518.                     && !lista.get(i + 2).node.h3.plocki.isEmpty())
  519.                 if (lista.get(i + 1).node.h1.plocki.getLast() == lista.get(i).node.h2.plocki
  520.                         .getLast()
  521.                         && lista.get(i).node.h2.plocki.getLast() == lista
  522.                                 .get(i + 2).node.h3.plocki.getLast()) {
  523.                     skok = true;
  524.                     kaj=3;
  525.                 }
  526.  
  527.             if (!lista.get(i + 1).node.h1.plocki.isEmpty()
  528.                     && !lista.get(i + 2).node.h2.plocki.isEmpty()
  529.                     && !lista.get(i).node.h3.plocki.isEmpty())
  530.                 if (lista.get(i + 1).node.h1.plocki.getLast() == lista
  531.                         .get(i + 2).node.h2.plocki.getLast()
  532.                         && lista.get(i + 2).node.h2.plocki.getLast() == lista
  533.                                 .get(i).node.h3.plocki.getLast()) {
  534.                     skok = true;
  535.                     kaj=4;
  536.                 }
  537.  
  538.             if (!lista.get(i + 2).node.h1.plocki.isEmpty()
  539.                     && !lista.get(i).node.h2.plocki.isEmpty()
  540.                     && !lista.get(i + 1).node.h3.plocki.isEmpty())
  541.                 if (lista.get(i + 2).node.h1.plocki.getLast() == lista.get(i).node.h2.plocki
  542.                         .getLast()
  543.                         && lista.get(i).node.h2.plocki.getLast() == lista
  544.                                 .get(i + 1).node.h3.plocki.getLast()) {
  545.                     skok = true;
  546.                     kaj=5;
  547.                 }
  548.  
  549.             if (!lista.get(i + 2).node.h1.plocki.isEmpty()
  550.                     && !lista.get(i + 1).node.h2.plocki.isEmpty()
  551.                     && !lista.get(i).node.h3.plocki.isEmpty())
  552.                 if (lista.get(i + 2).node.h1.plocki.getLast() == lista
  553.                         .get(i + 1).node.h2.plocki.getLast()
  554.                         && lista.get(i + 1).node.h2.plocki.getLast() == lista
  555.                                 .get(i).node.h3.plocki.getLast()) {
  556.                     skok = true;
  557.                     kaj=6;
  558.                 }
  559.  
  560.             // Debug za brisenje
  561.             if(skok){
  562.             //System.out.println("BRISAM --- " + kaj);
  563.             //System.out.println(lista.get(i).node);
  564.             //System.out.println(lista.get(i + 1).node);
  565.             //System.out.println(lista.get(i + 2).node);
  566.  
  567.             lista.remove(i + 1);
  568.             i = 0;
  569.             }
  570.         }
  571.        
  572.         //Finalno printanje na rezultatot otkako e optimiziran
  573.         System.out.println("Ova e finalniot optimiziran pat:");
  574.         for (int i = 0; i < lista.size(); i++) {
  575.             System.out.println(lista.get(i).node);
  576.         }
  577.     }
  578.  
  579.     public static void hanojDFS(Sostojba sega, Sostojba kraj) {
  580.         //Zemanje 2 razlicni kuli za da se pravi sporedba
  581.         for (int i = 0; i < 3; i++) {
  582.             HanojskaKula tmp;
  583.             if (i == 0) {
  584.                 tmp = sega.h1;
  585.             } else if (i == 1) {
  586.                 tmp = sega.h2;
  587.             } else {
  588.                 tmp = sega.h3;
  589.             }
  590.             //Ako sme odbrale prazna kula, skokni ja
  591.             if (tmp.plocki.isEmpty())
  592.                 continue;
  593.  
  594.             for (int j = 0; j < 3; j++) {
  595.                 //Ako sme ja odbrale vtorata da e identicna so prvata, skokni jas
  596.                 if (j == i)
  597.                     continue;
  598.  
  599.                 HanojskaKula tmp2;
  600.                 if (j == 0) {
  601.                     tmp2 = sega.h1;
  602.                 } else if (j == 1) {
  603.                     tmp2 = sega.h2;
  604.                 } else {
  605.                     tmp2 = sega.h3;
  606.                 }
  607.                
  608.                 //Ako vtorata e prazna, ili poslednata plocka na vtorata e pogolema od prvata, stavi ja taa od prvata na vtorata
  609.                 if (tmp2.plocki.isEmpty()
  610.                         || tmp2.plocki.getLast() > tmp.plocki.getLast()) {
  611.                     HanojskaKula h1;
  612.                     HanojskaKula h2;
  613.                     HanojskaKula h3;
  614.                     h3 = new HanojskaKula("3");
  615.                     h3.plocki = (LinkedList<Integer>) sega.h3.plocki.clone();
  616.                     h2 = new HanojskaKula("2");
  617.                     h2.plocki = (LinkedList<Integer>) sega.h2.plocki.clone();
  618.                     h1 = new HanojskaKula("1");
  619.                     h1.plocki = (LinkedList<Integer>) sega.h1.plocki.clone();
  620.                     if (i == 0) {
  621.                         if (j == 1) {
  622.                             h2.add(h1.plocki.removeLast());
  623.                         } else {
  624.                             h3.add(h1.plocki.removeLast());
  625.                         }
  626.                     } else if (i == 1) {
  627.                         if (j == 0) {
  628.                             h1.add(h2.plocki.removeLast());
  629.                         } else {
  630.                             h3.add(h2.plocki.removeLast());
  631.                         }
  632.                     } else {
  633.                         if (j == 0) {
  634.                             h1.add(h3.plocki.removeLast());
  635.                         } else {
  636.                             h2.add(h3.plocki.removeLast());
  637.                         }
  638.                     }
  639.                    
  640.                     //Napravi nova sostojba po promenata
  641.                     Sostojba tmpsostojba = new Sostojba(h1, h2, h3);
  642.  
  643.                     //Proveri dali e izminata do sega sostojbata
  644.                     //ps. ovde treba da se override-ne equals kaj pomosnaSostojba, bidejki .contains raboti
  645.                     // so equals mesto so compareTo
  646.                     if (!izminatiSostojbi.contains(tmpsostojba)) {
  647.                         //Cim ne e, dodadi ja kako izminata
  648.                         izminatiSostojbi.add(tmpsostojba);
  649.                         //Proveri dali e krajnata sostojba
  650.                         if (tmpsostojba.compareTo(kraj) == 0) {
  651.                             System.out.println("NAJDOV!");
  652.                             System.out.println(tmpsostojba);
  653.  
  654.                             //Dodadi ja nea vo patekata so pomosni sostojbi
  655.                             for (int z = 0; z < pateka.size(); z++) {
  656.                                 if (pateka.get(z).node.compareTo(sega) == 0) {
  657.                                     pomosnaSostojba tmps = pateka.get(z);
  658.                                     //Finalna lista na cekori koja ke se optimizira
  659.                                     LinkedList<pomosnaSostojba> finalno = new LinkedList<pomosnaSostojba>();
  660.                                     pomosnaSostojba finals = null;
  661.                                     for (int r = 0; r < pateka.size(); r++) {
  662.                                         if (pateka.get(r).node.compareTo(sega) == 0) {
  663.                                             finals = new pomosnaSostojba(
  664.                                                     pateka.get(r), tmpsostojba);
  665.                                         }
  666.                                     }
  667.                                     finalno.add(finals);
  668.                                     //Pocni da se navrakjas nanazad po parent pointeri na pomosnite sostojbi
  669.                                     // za da dojdes do celata izminata pateka
  670.                                     while (tmps != null) {
  671.                                         finalno.add(tmps);
  672.                                         tmps = tmps.parent;
  673.                                     }
  674.                                    
  675.                                     //Prevrti ja za da se dobie pravilno
  676.                                     Collections.reverse(finalno);
  677.                                    
  678.                                     //Povikaj funcija za optimiziranje i printanje na rezultatot
  679.                                     ekstraCekori(finalno);
  680.                                 }
  681.                             }
  682.  
  683.                         } else {
  684.                             //Najdi go segasniot node vo pomosni sostojbi
  685.                             for (int z = 0; z < pateka.size(); z++) {
  686.                                 if (pateka.get(z).node.compareTo(sega) == 0) {
  687.                                     //dodaj ja novata sostojba so parent pointer kon segasnata
  688.                                     pateka.add(new pomosnaSostojba(pateka
  689.                                             .get(z), tmpsostojba));
  690.                                 }
  691.                             }
  692.                             //Rekurzija
  693.                             hanojDFS(tmpsostojba, kraj);
  694.                         }
  695.                     }
  696.                 }
  697.  
  698.             }
  699.         }
  700.     }
  701.  
  702.     // Da ima po 4 litri vo koja bilo od casite
  703.     public static void primer1() {
  704.  
  705.         System.out.println("\n--------------\nPrimer 1 \n--------------");
  706.  
  707.         LinkedList<Node> teminja = new LinkedList<Node>();
  708.  
  709.         // Kreiraj teminja so soodvetni int vrednost
  710.         Node n30 = new Node(30);
  711.         Node n31 = new Node(31);
  712.         Node n32 = new Node(32);
  713.         Node n33 = new Node(33);
  714.         Node n34 = new Node(34);
  715.         Node n35 = new Node(35);
  716.         Node n20 = new Node(20);
  717.         Node n25 = new Node(25);
  718.         Node n10 = new Node(10);
  719.         Node n15 = new Node(15);
  720.         Node n00 = new Node(0);
  721.         Node n01 = new Node(1);
  722.         Node n02 = new Node(2);
  723.         Node n03 = new Node(3);
  724.         Node n04 = new Node(4);
  725.         Node n05 = new Node(5);
  726.  
  727.         // Dodaj gi vo listata
  728.         teminja.add(n30);
  729.         teminja.add(n31);
  730.         teminja.add(n32);
  731.         teminja.add(n33);
  732.         teminja.add(n34);
  733.         teminja.add(n35);
  734.         teminja.add(n20);
  735.         teminja.add(n25);
  736.         teminja.add(n10);
  737.         teminja.add(n15);
  738.         teminja.add(n00);
  739.         teminja.add(n01);
  740.         teminja.add(n02);
  741.         teminja.add(n03);
  742.         teminja.add(n04);
  743.         teminja.add(n05);
  744.         // Kreiraj graf so listata
  745.         Graph graf = new Graph(teminja);
  746.  
  747.         // Postavi koj e korenot na grafot (od kaj da pocne prebaruvanjeto)
  748.         graf.setRoot(n00); // Nivo 1
  749.  
  750.         // 0/0
  751.         graf.connectNodes(n00, n05);
  752.         graf.connectNodes(n00, n30);
  753.         // 1/0
  754.         graf.connectNodes(n10, n00);
  755.         graf.connectNodes(n10, n30);
  756.         graf.connectNodes(n10, n15);
  757.         // 2/0
  758.         graf.connectNodes(n20, n30);
  759.         graf.connectNodes(n20, n00);
  760.         graf.connectNodes(n20, n25);
  761.         graf.connectNodes(n20, n02);
  762.         // 3/0
  763.         graf.connectNodes(n30, n00);
  764.         graf.connectNodes(n30, n03);
  765.         graf.connectNodes(n30, n35);
  766.         // 0/1
  767.         graf.connectNodes(n01, n10);
  768.         graf.connectNodes(n01, n00);
  769.         graf.connectNodes(n01, n31);
  770.         graf.connectNodes(n01, n05);
  771.         // 3/1
  772.         graf.connectNodes(n31, n01);
  773.         graf.connectNodes(n31, n30);
  774.         graf.connectNodes(n31, n35);
  775.         graf.connectNodes(n31, n04);
  776.         // 0/2
  777.         graf.connectNodes(n02, n20);
  778.         graf.connectNodes(n02, n00);
  779.         graf.connectNodes(n02, n32);
  780.         graf.connectNodes(n02, n05);
  781.         // 3/2
  782.         graf.connectNodes(n32, n05);
  783.         graf.connectNodes(n32, n30);
  784.         graf.connectNodes(n32, n35);
  785.         graf.connectNodes(n32, n02);
  786.         // 0/3
  787.         graf.connectNodes(n03, n05);
  788.         graf.connectNodes(n03, n00);
  789.         graf.connectNodes(n03, n33);
  790.         graf.connectNodes(n03, n30);
  791.         // 3/3
  792.         graf.connectNodes(n33, n03);
  793.         graf.connectNodes(n33, n30);
  794.         graf.connectNodes(n33, n35);
  795.         graf.connectNodes(n33, n15);
  796.         // 0/4
  797.         graf.connectNodes(n04, n05);
  798.         graf.connectNodes(n04, n00);
  799.         graf.connectNodes(n04, n34);
  800.         graf.connectNodes(n04, n31);
  801.         // 3/4
  802.         graf.connectNodes(n34, n35);
  803.         graf.connectNodes(n34, n30);
  804.         graf.connectNodes(n34, n04);
  805.         graf.connectNodes(n34, n25);
  806.         // 0/5
  807.         graf.connectNodes(n05, n35);
  808.         graf.connectNodes(n05, n00);
  809.         graf.connectNodes(n05, n32);
  810.         // 3/5
  811.         graf.connectNodes(n35, n30);
  812.         graf.connectNodes(n35, n05);
  813.         // 2/5
  814.         graf.connectNodes(n25, n20);
  815.         graf.connectNodes(n25, n05);
  816.         graf.connectNodes(n25, n34);
  817.         graf.connectNodes(n25, n35);
  818.         // 1/5
  819.         graf.connectNodes(n15, n33);
  820.         graf.connectNodes(n15, n10);
  821.         graf.connectNodes(n15, n05);
  822.         graf.connectNodes(n15, n35);
  823.  
  824.         BFS_Iterativen_Dlabocina_Multivalue(graf, 34, 4);
  825.     }
  826.  
  827.     public static LinkedList<Node> DFS_Iterativen_Dlabocina(Graph graf,
  828.             int value, int depth) {
  829.         // Kreiraj stek
  830.         LinkedList<Node> stek = new LinkedList<Node>();
  831.         // Kreiraj lista na iskoristeni
  832.         LinkedList<Node> iskoristeni = new LinkedList<Node>();
  833.         // Dodaj go temeto vo stekot
  834.         stek.add(graf.root);
  835.         System.out.println("Stavam " + graf.root);
  836.         // Dali e najdeno temeto?
  837.         boolean najdov = false;
  838.  
  839.         // Se dodeka stekot ima elementi
  840.         while (!stek.isEmpty()) {
  841.             // Dali bilo dodadeno vo stekot?
  842.             boolean promena = false;
  843.  
  844.             // Ako go najde, prekini so prebaruvanje
  845.             if (stek.peek().value == value) {
  846.                 System.out.println("Najdov!");
  847.                 najdov = true;
  848.                 break;
  849.             }
  850.  
  851.             // Proveri gi sosedite na najgorniot element vo stekot
  852.             System.out.println("Proveruvam sosedi na " + stek.peek());
  853.             for (int i = 0; i < stek.peek().getNeighbours().size(); i++) {
  854.                 // Dali toj sosed e iskoristen
  855.                 if (!iskoristeni.contains(stek.peek().getNeighbours().get(i))
  856.                         && stek.size() < depth) {
  857.                     // Postavi go kako iskoristen i stavi go vo stekto
  858.                     System.out.println("Stavam "
  859.                             + stek.peek().getNeighbours().get(i));
  860.                     iskoristeni.push((stek.peek().getNeighbours().get(i)));
  861.                     stek.push(stek.peek().getNeighbours().get(i));
  862.                     // Obelezi deka e napravena promena
  863.                     promena = true;
  864.                     break;
  865.                 }
  866.             }
  867.             // Ako nema promena, vadi od stekot
  868.             if (!promena) {
  869.                 System.out.println("Vadam " + stek.peek());
  870.                 stek.pop();
  871.             }
  872.         }
  873.  
  874.         // Ako ne e najdeno nisto, pisi soodvetna poraka
  875.         if (!najdov) {
  876.             System.out.println("Nema!");
  877.             return null;
  878.         }
  879.  
  880.         Collections.reverse(stek);
  881.         return stek;
  882.     }
  883.  
  884.     public static void DFS_Rekurziven_Dlabocina(Node nod, int value, int depth,
  885.             int maxdepth) {
  886.         System.out.println("Rabotam so " + nod.value);
  887.         if (nod.value == value) {
  888.             System.out.println("Najdov!");
  889.         } else if (depth < maxdepth) {
  890.             for (int i = 0; i < nod.neighbours.size(); i++) {
  891.                 DFS_Rekurziven_Dlabocina(nod.neighbours.get(i), value,
  892.                         depth + 1, maxdepth);
  893.             }
  894.         }
  895.  
  896.     }
  897.  
  898.     public static void BFS_Iterativen_Dlabocina(Graph graf, int value) {
  899.         // Kreiraj stek
  900.         LinkedList<Node> stek = new LinkedList<Node>();
  901.         // Kreiraj lista na iskoristeni
  902.         LinkedList<Node> iskoristeni = new LinkedList<Node>();
  903.         // Dodaj go temeto vo stekot
  904.         stek.add(graf.root);
  905.         System.out.println("Stavam " + graf.root);
  906.         // Dali e najdeno temeto?
  907.         boolean najdov = false;
  908.  
  909.         // Se dodeka stekot ima elementi
  910.         while (!stek.isEmpty()) {
  911.             // Dali bilo dodadeno vo stekot?
  912.             boolean promena = false;
  913.             boolean najdeno = false;
  914.  
  915.             // Proveri gi sosedite na najgorniot element vo stekot
  916.             System.out.println("Proveruvam sosedi na " + stek.getLast());
  917.             for (int i = 0; i < stek.getLast().getNeighbours().size(); i++) {
  918.                 // Dali toj sosed e iskoristen
  919.                 if (!iskoristeni
  920.                         .contains(stek.getLast().getNeighbours().get(i))) {
  921.                     // Postavi go kako iskoristen i stavi go vo stekto
  922.  
  923.                     System.out.println("Stavam "
  924.                             + stek.getLast().getNeighbours().get(i));
  925.                     iskoristeni.push((stek.getLast().getNeighbours().get(i)));
  926.                     stek.push(stek.getLast().getNeighbours().get(i));
  927.                     // Obelezi deka e napravena promena
  928.                     promena = true;
  929.  
  930.                     // Ako go najde, prekini so prebaruvanje
  931.                     if (stek.peek().value == value) {
  932.                         System.out.println("Najdov!");
  933.                         najdeno = true;
  934.                         najdov = true;
  935.                         break;
  936.                     }
  937.  
  938.                 }
  939.  
  940.             }
  941.  
  942.             // Ako e najdeno
  943.             if (najdeno) {
  944.                 break;
  945.             }
  946.  
  947.             // Ako nema promena, vadi od stekot
  948.             if (!promena) {
  949.                 System.out.println("Vadam " + stek.getLast());
  950.                 stek.removeLast();
  951.             }
  952.         }
  953.  
  954.         // Ako ne e najdeno nisto, pisi soodvetna poraka
  955.         if (!najdov)
  956.             System.out.println("Nema!");
  957.     }
  958.  
  959.     public static void BFS_Iterativen_Dlabocina_Multivalue(Graph graf,
  960.             int value, int value2) {
  961.         // Kreiraj stek
  962.         LinkedList<Node> stek = new LinkedList<Node>();
  963.         // Kreiraj lista na iskoristeni
  964.         LinkedList<Node> iskoristeni = new LinkedList<Node>();
  965.         // Pateka
  966.         LinkedList<pomosenNode> pateka = new LinkedList<pomosenNode>();
  967.         pateka.push(new pomosenNode(null, graf.root));
  968.         // Dodaj go temeto vo stekot
  969.         stek.add(graf.root);
  970.         System.out.println("Stavam " + graf.root);
  971.  
  972.         // Dali e najdeno temeto?
  973.         boolean najdov = false;
  974.  
  975.         // Se dodeka stekot ima elementi
  976.         while (!stek.isEmpty()) {
  977.             // Dali bilo dodadeno vo stekot?
  978.             boolean promena = false;
  979.             boolean najdeno = false;
  980.  
  981.             // Proveri gi sosedite na najgorniot element vo stekot
  982.             System.out.println("Proveruvam sosedi na " + stek.getLast());
  983.             for (int i = 0; i < stek.getLast().getNeighbours().size(); i++) {
  984.                 // Dali toj sosed e iskoristen
  985.                 if (!iskoristeni
  986.                         .contains(stek.getLast().getNeighbours().get(i))) {
  987.                     // Postavi go kako iskoristen i stavi go vo stekto
  988.  
  989.                     System.out.println("Stavam "
  990.                             + stek.getLast().getNeighbours().get(i));
  991.                     iskoristeni.push((stek.getLast().getNeighbours().get(i)));
  992.  
  993.                     for (int z = 0; z < pateka.size(); z++) {
  994.                         if (pateka.get(z).node.value == stek.getLast().value) {
  995.                             System.out.println(pateka.get(z));
  996.                             pateka.push(new pomosenNode(pateka.get(z), stek
  997.                                     .getLast().getNeighbours().get(i)));
  998.                             break;
  999.                         }
  1000.                     }
  1001.                     stek.push(stek.getLast().getNeighbours().get(i));
  1002.                     // Obelezi deka e napravena promena
  1003.                     promena = true;
  1004.  
  1005.                     // Ako go najde, prekini so prebaruvanje
  1006.                     if (stek.peek().value == value
  1007.                             || stek.peek().value == value2) {
  1008.                         LinkedList<pomosenNode> rev = new LinkedList<pomosenNode>();
  1009.                         pomosenNode tmp = null;
  1010.                         System.out.println("Najdov!");
  1011.                         for (int z = 0; z < pateka.size(); z++) {
  1012.  
  1013.                             if (pateka.get(z).node.value == value
  1014.                                     || pateka.get(z).node.value == value2) {
  1015.  
  1016.                                 tmp = pateka.get(z);
  1017.                                 while (tmp.parent != null) {
  1018.                                     rev.add(tmp);
  1019.                                     tmp = tmp.parent;
  1020.                                 }
  1021.  
  1022.                             }
  1023.  
  1024.                         }
  1025.                         rev.add(tmp);
  1026.                         Collections.reverse(rev);
  1027.                         System.out.println(rev.toString());
  1028.                         najdeno = true;
  1029.                         najdov = true;
  1030.                         break;
  1031.                     }
  1032.  
  1033.                 }
  1034.  
  1035.             }
  1036.  
  1037.             // Ako e najdeno
  1038.             if (najdeno) {
  1039.                 break;
  1040.             }
  1041.  
  1042.             // Ako nema promena, vadi od stekot
  1043.             if (!promena) {
  1044.                 System.out.println("Vadam " + stek.getLast());
  1045.                 stek.removeLast();
  1046.             }
  1047.         }
  1048.  
  1049.         // Ako ne e najdeno nisto, pisi soodvetna poraka
  1050.         if (!najdov)
  1051.             System.out.println("Nema!");
  1052.     }
  1053.  
  1054.     public static void DFS_Iterative_Deep(Graph graf, int value, int depth) {
  1055.         for (int i = 1; i <= depth; i++) {
  1056.             System.out.println("Proveruvam na dlabocina: " + i);
  1057.             if (DFS_Iterativen_Dlabocina(graf, value, i) != null)
  1058.                 break;
  1059.         }
  1060.     }
  1061.  
  1062. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!