Verify TSP

TSP takes factorial time to solve because we're forced to try every permutation of all the possible cities. For example, given 4 cities, A, B, C, D, we need to try:

A,B,C,D
B,A,C,D
C,A,B,D
A,C,B,D
B,C,A,D
C,B,A,D
C,B,D,A
B,C,D,A
D,C,B,A
C,D,B,A
B,D,C,A
D,B,C,A
D,A,C,B
A,D,C,B
C,D,A,B
D,C,A,B
A,C,D,B
C,A,D,B
B,A,D,C
A,B,D,C
D,B,A,C
B,D,A,C
A,D,B,C
D,A,B,C

That's 4! or 4*3*2*1 or 24 permutations.

TSP in NP

Although it takes factorial time to solve TSP, TSP is in NP because we can verify a solution much faster. Let's write a TSP verifier!

Assignment

Complete the verify_tsp function by implementing the algorithm below. Notice that it runs in polynomial time.

Pseudocode

Inputs:

paths: A matrix where each point represents the distance between the two cities. For example, paths[cityA][cityB] holds the distance from cityA to cityB. paths[cityA][cityB] = paths[cityB][cityA]
dist: The distance we are trying to find a path shorter than
actual_path: The path we are trying to verify

Algorithm:

Loop over each city in the actual path
Sum the distance between each city in the actual path
If the sum is less than dist, return True, otherwise return False