Travelling Salesman Problem

For exact TSP on a modest number of cities, use Held-Karp dynamic programming rather than brute-force permutations. Fix city zero. Let dp[mask][last] be the minimum cost to start at zero, visit exactly the cities in mask, and finish at last. Initialize the mask containing zero, then for every state append each city not in mask: update dp[mask | bit(next)][next] from dp[mask][last] + cost[last][next]. The answer is the best full-mask state plus the edge back to zero. Store predecessors if the route is needed. This is O(n^2 2^n) time and O(n 2^n) space, so state the practical limit and use heuristics or approximation only when exactness is not required. Check missing edges, asymmetric costs, two cities, and overflow sentinels.