Traveling Salesperson Dynamic Programming Lab

Github Classroom

You can clone the starter files for this lab at this GitHub Classroom link. Be sure to open the assignment in VSCode and setup up your virtual environment following these instructions.

Dynamic Programming Algorithm

The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimization graph problem. Given a complete graph with $n$ nodes and edge weights, the goal is to find a cycle that contains all $n$ nodes which minimizes the sum of the edge weights.

Since this problem is NP-hard, there is no known polynomial-time algorithm to find such a cycle. A brute-force search would require $O(n!)$ time, which grows too quickly with larger and larger input sizes. However, if we choose to search the solution space in a smarter way using dynamic programming, we are able to find a solution in $O(n^22^n)$ time!

for every subset S of the nodes in increasing size order:
    for every node i that isn't the cycle root:
        if the cycle root or i is not in S:
            continue

        if |S| = 2:
            costs[S, i] = distance(cycle root, i)
        else:
            costs[S, i] = min {C(S-{i}, j) + distance(j, i)} where j belongs to S, j != i and j != 1