SolvingSearchProblems/DFBnB.java at master · zafriryak/SolvingSearchProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Stack;


/**
 *
 * @author Zafrir
 */
public class DFBnB extends Algorithms {

    private CAreaMap cam;
    private double alpha;
    private Stack<Node> stack;

    public DFBnB(CAreaMap cam) throws FileNotFoundException {
        alpha = Double.POSITIVE_INFINITY;
        path = "";
        numOfVertexExp = 0;
        cost = 0;
        startTime = (double) System.currentTimeMillis();
        this.cam = cam;
        this.mat = cam.getMat();
        this.start = cam.getStartPoint();
        this.finish = cam.getFinishPoint();
        stack = new Stack<>();
        dfbnb();
    }

    private int heuristic(Node start) {
        int distance = (int) Math.sqrt(Math.pow(start.getX() - finish.getX(), 2) + Math.pow(start.getY() - finish.getY(), 2));
        return distance * 2;
    }


    private void dfbnb() throws FileNotFoundException {
        String ansPath="";
        int ansCost=0;
        boolean found=false;
        stack.push(start);
        start.setG(0);
        start.setDepth(0);
        Node son, node;
        ArrayList<Node> visited = new ArrayList<>();
        int f;
        ArrayList<Node> sons;
        while (!stack.isEmpty()) {
            node = stack.pop();
            numOfVertexExp++;
            visited.add(node);
            sons = cam.getAllSons(node);
            for (int i = sons.size() - 1; i >= 0; i--) {
                son = sons.get(i);
                if (!stack.contains(son) && !visited.contains(son)) {
                    if(son.getPriceOfMat()+node.getG()<son.getG()){
                        son.setParent(node);
                        son.setG(son.getParent().getG() + son.getPriceOfMat());
                        son.setDepth(son.getParent().getDepth()+1);
                    }
                    f = son.getG() + heuristic(son);
                    if (son.equals(finish)) {
                        if(f<=alpha){
                            alpha = f;
                            ansPath=makePath(son);
                            ansCost=cost;
                            found=true;
                        }
                    }
                    if (f < alpha) {
                        stack.push(son);
                    }
                }
                else{
                    for(int j=0 ; j<visited.size() ; j++){
                        if(visited.get(j).getDepth()>node.getDepth()){
                           visited.remove(j);
                            j--;
                        }
                    }
                }

            }
        }
        if(found){
            PrintWriter pw=new PrintWriter("output.txt");
            pw.write(ansPath.substring(0, ansPath.length()-1)+"\n");
            pw.write("Num: "+numOfVertexExp+"\n");
            pw.write("Cost: "+ansCost+"\n");
            pw.write(((System.currentTimeMillis()-startTime)*0.001)+" seconds"+"\n");
            pw.close();
            //System.out.println("dfbnb: ");
            //System.out.println("Nums: " + numOfVertexExp);
            //System.out.println(ansPath);
            //System.out.println("cost: " + ansCost);
            //System.out.println("time take: " + ((System.currentTimeMillis() - startTime) * 0.001) + "\n");
        }
        else{
            //System.out.println("no path");
            PrintWriter pw=new PrintWriter("output.txt");
            pw.write("no path");
            pw.close();
        }
    }
}