I am trying to implement branch & bound search algorithm in java. I know its concept (how it works), but I am not sure how to implement it.
I found some examples on google but they are way more complex and I can't seem to understand them. I want to implement it in a simple way. Also most of them are not in java.
Following is the relevant method where my search starts (This is just a part of my code).
I think my for loop needs to get modified appropriately to store the frontier nodes and costs and then get the node with least cost and then perform the search again until the goal node is found adding the cumulative costs.
So I guess recursive method works best for this. But I am not sure how to implement.
The following is not giving me any compiling error but is giving me run time error as Node1 cannot be cast to java.lang.Comparable. Does anyone be kindly look into this issue? I have been trying to do it since hours but cant seem to find any solution.
ALSO, any small piece of code which directs me in a right path would be much helpful.
public void Search(Node1[] nodes, String startNode, int size){
List<String> frontierNodes = new ArrayList<String>();
Queue<Node1> frontierCosts = new PriorityQueue<Node1>();
for(int i=0; i<size;i++) {
if(startNode.equals(nodes[i].getStartNode())) { // user enters the startNode and goalNode
frontierNodes.add(nodes[i].getEndNode());
frontierCosts.add(new Node1(nodes[i].getCost()));
frontierCosts.peek();
System.out.println("Min cost" +frontierCosts.peek());
int nodesLength = nodes.length - (frontierNodes.size());
i--;
System.out.println("remaining search nodes length" +nodesLength);
//Search(nodes, frontierCosts.peek().getEndNode() ,nodesLength); // RECURSIVE CALL?
}
}
}
Following is the Node1 class which stores the file information
class Node1 {
String start, end;
double cost;
public Node1(String start, String end, double cost){
this.start = start;
this.end = end;
this.cost = cost;
}
public Node1(double cost) { // alternate constructor to store cost in priority queue
this.cost = cost;
}
public String getStartNode(){
return start;
}
public String getEndNode(){
return end;
}
public double getCost(){
return cost;
}
}
Following is the file format(startNode endNode cost)
A B 10
A C 12
B D 6
....
[EDIT]:
I want to implement branch and bound search, where the program asks the user to enter startNode and goalNode and then access the data from Node1 class (where the data from file is stored) and then program enters the search method (above method) passing all the nodes, startNode and length of nodes(size).
If the startNode matches any of the node1[].getStartNode, then it stores the corresponding expanded nodes in frontierNodes and their corresponding costs in frontierCosts in a priority queue (to pick the least cost).
Then the program peeks() the priority queue & selects the least cost node (front of queue) and then searches again (recursive call to above search method?) with that particular node as startNode and the search continues.
When the program reaches the new nodes, the cost at each new node should get the cumulative cost of the path visited so far and the program should output the path and the cost.
PriorityQueue needs the data structure that implements Comparable interface unless you pass in a Comparator as a constructor.
The change should be pretty straightforward.
class Node1 implements Comparable<Node1> {
String start, end;
double cost;
public Node1(String start, String end, double cost){
this.start = start;
this.end = end;
this.cost = cost;
}
public Node1(double cost) { // alternate constructor to store cost in priority queue
this.cost = cost;
}
public String getStartNode(){
return start;
}
public String getEndNode(){
return end;
}
public double getCost(){
return cost;
}
@Override
public int compareTo(Node1 o) {
return Double.compare(this.cost, o.cost);
}
}
Note that if you want the result to be deterministic and the cost is not unique, you might need to use start/end node as part of the comparison as well.
For your main logic, there are a couple things not quite right.