Dynamic programming (DP) solves the Traveling Salesman Problem (TSP) by breaking it into smaller subproblems and building solutions recursively. We define as the minimum cost of starting at city , visiting all cities in set , and returning to the origin. The steps are as follows:
- Base Case: If no cities remain to visit, return directly to the origin:
- Recursive Case: If there are cities left to visit in , choose the next city with the minimum cost:
- Final Solution: Starting at the origin, compute the minimum cost to visit all cities:
Dynamic programming reduces computations from (brute force) to , significantly improving efficiency. However, since TSP is an NP-hard problem, it still has exponential growth.
Despite its complexity, the DP approach to TSP is widely applied in fields such as logistics, robotics, and bioinformatics, highlighting its practical value and mathematical elegance.