Branch and Bound for TSP explores partial tours and computes lower bounds on final cost. Partial paths that cannot beat the best complete tour found so far are pruned.
int tspBB(vector<vector<int>>& cost) {
int n = cost.size(), best = INT_MAX;
vector<bool> used(n, false);
used[0] = true;
function<void(int,int,int)> dfs = [&](int u, int cnt, int curr) {
if (cnt == n) {
if (cost[u][0]) best = min(best, curr + cost[u][0]);
return;
}
if (curr >= best) return;
for (int v = 0; v < n; v++) {
if (!used[v] && cost[u][v]) {
used[v] = true;
dfs(v, cnt + 1, curr + cost[u][v]);
used[v] = false;
}
}
};
dfs(0, 1, 0);
return best;
}Nodes represent partial tours; depth equals number of visited cities.
Lower/upper bounds cut large parts of permutation tree.
Search remains exact; pruning only removes provably suboptimal branches.
Quiz coming soon for this algorithm.