TSP Approximation
← Back to Bitmask DP
Using bitmask DP to solve the Traveling Salesman Problem exactly in O(2^n * n^2) time. While still exponential, this is dramatically better than the naive O(n!) approach. For larger instances, approximation algorithms and heuristics are used.