// Time Complexity: O(V!)
// Space complexity: O(V)
unsigned int Graph::runTSPBranchAndBound(TSPState state) const {
int pathSize = state.path.size();
int vertices = getVertices();
if(pathSize == vertices) {
int lastUsedPos = state.path.back();
unsigned int totalCost = state.currCost + getDistance(lastUsedPos, 0);
return totalCost < state.bestCost ? totalCost : state.bestCost;
}
for(int i = 0; i < vertices; i++) {
if(state.visited[i]) {
continue;
}
// key diff from brute-force version
int currDist = getDistance(state.path.back(), i);
int newCost = state.currCost + currDist;
if(newCost >= state.bestCost) { // cleaning unnecessary paths (prune = Branch-and-Bound)
continue;
// if I use a specific graph where pruning never happens, it becomes as bad as brute force because
// it ends up exploring the entire search space without cutting any branches
// fortunately, this is not the case in most situations
}
state.currCost += currDist;
state.visited[i] = true;
state.path.push_back(i);
state.bestCost = std::min(state.bestCost, runTSPBranchAndBound(state));
state.path.pop_back();
state.visited[i] = false;
state.currCost -= currDist;
}
return state.bestCost;
}