Bitmask DP (Tiny TSP)

Michael Held & Richard Karp, 1962

Michael Held and Richard Karp’s dynamic programming treatment of the traveling salesman problem keeps costs for visiting a subset of cities, ending at a particular vertex, reusing smaller masks in a Bellman recursion. With n = 4 the full table fits on screen: rows are bitmasks (must include city 0), columns are the tour endpoint, inactive combinations are dimmed, the active relaxations glow gold, and the final row highlights before reporting the best tour cost including the return edge to 0.