Originally posted by: beratpostalci
I have a solution tree `HashMap<Integer, ArrayList<Integer>> map` which represents paths between cities. Sample map is like: `{1=[3,5], 2=[4,5], 3[1], 4=[2], 5=[3,4]}` . I want to find an optimal path from this map by traversing each branch of it. If algorithm founds a full path it calculates path's total costs with calculateCost method and compares it with an upperBound value, if path's cost is less than upperBound then optimal path is found. I need to use backtracking to prune the branch. However my code is not working properly:
public static Double calculateCost(ArrayList<Integer> path, Integer[][] cost) {
Double totalCost = 0.0;
for(int i = 0; (i + 1) < path.size(); i++) {
totalCost += cost[path.get(i) - 1][path.get(i + 1) - 1];
}
return totalCost;
}
public static ArrayList<Integer> step(HashMap<Integer,
ArrayList<Integer>> paths,
ArrayList<Integer> nodes, Integer key ,
Integer[][] cost,
Double upperBound,
ArrayList<Integer> candidatePath,
Integer stepCnt,
boolean found) {
if(!found) {
if (nodes.contains(key)) {
if(key == 1 && nodes.size() > 0) {
if(nodes.size() == paths.size()) {
nodes.add(key);
if(calculateCost(nodes, cost) < upperBound) {
// optimal path found
candidatePath = nodes;
return nodes;
}
if(!candidatePath.isEmpty()) {
if(calculateCost(candidatePath, cost) > calculateCost(nodes, cost)) {
candidatePath = nodes;
}
} else {
candidatePath = nodes;
}
} else {
// need to prune the tree with backtracking
for(int i = 0; i < stepCnt; i++) {
if(nodes.size() > 0)
nodes.remove(nodes.size() - 1);
}
}
} else if (key != 1 && nodes.size() > 0){
// need to prune the tree with backtracking
for(int i = 0; i < stepCnt; i++) {
if(nodes.size() > 0)
nodes.remove(nodes.size() - 1);
}
}
return nodes;
}
nodes.add(key);
ArrayList<Integer> children = paths.get(key);
for (Integer child : children) {
stepCnt++;
step(paths, nodes, child, cost, upperBound, candidatePath, stepCnt, found);
}
}
return nodes;
}
public static void main(String args[]) {
ArrayList<Integer> nodes = new ArrayList<>();
ArrayList<Integer> candidatePath = new ArrayList<>();
Integer stepCnt = 0;
nodes = step(paths, nodes, 1, cost, upperBound, candidatePath, stepCnt, false);
}
For the paths parameter consider the sample map that I provide above. I researched and found Branch and Bound algorithm provides a solution for my problem but I cannot find a working implementation of it. My problem is explained in this video after 3:10 -->
video link