Wrapping up Path-finding with the Traveling Salesman Problem

My previous blogs on pathfinding have covered Dijkstra's shortest first path  (SPF) algorithm and the A* algorithm. Those discussions did not cover the computational complexity of these algorithms. That will be discussed now. In addition I'll discuss the Traveling Salesman problem.

The Dijkstra SPF algorithm is known as a Greedy algorithm. At each new vertex the next vertex is chosen using the minimum distance or weight. Given the set of vertices V and weights E the complexity is Θ((V + E)*log(V)). It is solvable in polynomial time, i.e. Θ(n**k). The A* algorithm applies a heuristic to Dijkstra's algorithm to reduce the number of computations and hence is also solvable in polynomial time.

Computational Complexity

As an introduction to computational complexity review the chart below, courtesy of bigocheatsheet.com. Note: click on all figures to expand.

Figure 1 Complexity

Traveling Salesman Problem

I want to contrast the previous algorithms with the The Traveling Salesman Problem (TSP). The TSP can be stated as "Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point."

The Naive solution to the TSP

1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate the cost of every permutation and keep track of the minimum cost permutation.
4) Return the permutation with minimum cost.

The naive solution can be viewed as a decision tree. Starting at the top with the given source node there are (n-1) paths that can be taken. Once a path is taken there is one fewer node and we are left with (n-2) paths. As we traverse down the tree this progression continues and the total number of decisions can be seen to be (n-1)!.

The time complexity of the naive TSP solution is Θ((n-1)!). That's about as bad as it can get! This grows faster than exponential with a constant base and hence is not polynomial time. As example with n=5 nodes there are 24 possible routes and for only n=10 nodes there are 362880 possible routes. Θ((n-1)!) is clearly not sustainable.

Dynamic Programming

Using a dynamic programming (DP) approach (Bellman-Held-Karp) the TSP solution can be solved in Θ(n²*2ⁿ). This is still exponential and not polynomial time. The TSP problem today remains NP-hard despite the progress of Bellman-Held-Karp in 1962. The key to the DP approach is that if you look at the naive decision tree there are many duplicate decisions farther down in the tree. Each of these duplicates can be viewed as a sub-problem that can be solved once.

Figure 2 compares the computational complexity of the naive and DP TSP algorithms.

Figure 2 - Naive & DP Complexity

The example solved here for the TSP problem is shown in Figure 3.

Figure 3 - Graph for TSP example

The objective is to start at node '0' and visit each node just once then return to node '0'. As background we will first use the graph as a shortest path problem from '0' to '9' the Dijkstra solution is path 0-3-4-8-9 with a total distance of 36. Note as part of the Dijkstra solution the minimum distance from '0' to each node is calculated a part of the solution.

As a TSP problem the input data is represented as a n x n cost matrix C. The entry C(i,j) is the cost to move along edge i to j. Likewise, C(j,i) is the cost to move along the edge from j to i (see code listing starting at line 114. For edges that don't exist my entry for that element is 'inf' where inf = math.inf.

 

Figure 4 - Graph for Solved TSP

As a Dijkstra SPF problem each node is visited once in the computation and each edge is visited once.

Observe that the TSP problem statement starts at node '0' and the next node visited must be either '1', '2' or '3'. Note also from the ending criteria the last node visited must also be '1', '2' or '3' before returning direct to '0'. The closed path of edges marked in red is a Hamiltonian cycle, specifically it is the minimum cost Hamiltonian cycle. Each node is visited just once and it doesn't matter which node you start on, the total cost remains the same. In this example the cycle is [0, 3, 4, 5, 7, 9, 8, 6, 1, 2] and the total cost is 92.

TSP Code with Dynamic Programming

held-karp-tsp

Final Comments

Note that the three algorithms, Dijkstra SPF, A* and TSP can all be applied in similar instances. For example a warehouse problem in which robots move material from a source location to a terminal location. My examples have shown the material can be moved from a starting location to a destination location using either Dijkstra SPF or A* and can be done in polynomial time. On the other hand if a large batch of material is to be delivered to multiple workstations in an optimal manner without repeating locations then the problem becomes a Traveling Salesman Problem and cannot be solved in polynomial time. In fact given a large enough number of workstations (n~20) there may not be enough computing power to even compute a solution with the fastest computers. Another application of the TSP algorithm is to minimize the CNC table movement of a PCB drilling machine.

Some recent approaches on the TSP problem apply a heuristics to put an upper bound on the optimal solution, but still do not find the optimal solution. For example the result of a heuristic algorithm might be a number that represents 123/122 of the true optimum.

ref: Gary Pollice, Stanley Selkow, George Heineman, "Algorithms in a Nutshell", O'reilly Media, June 2009.

Please leave a comment if you liked this blog or have suggestions for new material.