Traveling Salesman Problem

 

1. Name: 

Traveling Salesman Problem (TSP)Algorithm

2. Image: 

3. Problem: 

The traveling salesman problem looks to find the shortest tour/path through a given set of n cities while visiting each city exactly once before returning to the city where the tour/path was started. Although the problem is framed with regards to a traveling salesman, it can certainly be contextually manipulated to solve similar problems in other industries or categories such as that of logistics and distribution.

4. Design: 

The traveling salesman problem based on our current study in the classroom is an algorithm that utilizes brute force, more specifically exhaustive search. Implementations vary widely and based on my research include both recursive and non-recursive implementations.

5. Data Structure: 

Implementation strategies for this algorithm vary, but most view the problem in terms of a graphing problem, which helps us to better frame what data structures, may be appropriate. In terms of a graph node, because each node could have up to n-1 edges connecting it to other nodes, it may be better to use a dynamic structure such as a linked list to store the edges within each node. This is what is known as an adjacency list. An alternative to an adjacency list would be an adjacency matrix. An adjacency matrix uses a two-dimensional array for storing the edges of the graph. Again, remember that these are just two collections that could be used for implementing the TSP algorithm.

6. Pseudocode: 

The simplest way of implementing an algorithm to solve the TSP problem is using a breadth-first traversal solution, which can be found below, and adding a few more pieces of information. The first is to store the path length from the starting vertex to this vertex, and the vertex that is the predecessor of this vertex in that path for each vertex during the traversal. The loop is then modified to terminate when the target vertex is reached. The path length for the shortest path is simply the path length to the predecessor of the target +1. If needed, backtracking along the chain of predecessors can be used to output the vertices along the shortest path.

A breadth-first traversal canbe constructed for a graph by using a queue and an un-ordered list. The queue (traversal-queue) is used to manage the traversal and the unordered list/result-list to build the result. The first step is to enqueue the starting vertex into the traversal-queue and mark the starting vertex as visited. Then begin a loop that will continue until the traversal-queue is empty. Within this loop, the first vertex is taken off of the traversal-queue and added to the rear of the result-list. Next, enqueue each of the vertices that are adjacent to the current one, and have not already been marked as visited, into the traversal-queue, mark each of them as visited, and then repeat the loop. This process is repeated for each of the visited vertices until the traversal-queue is empty. The ending result-list contains the vertices in breadth-first order from the given starting point.

7. Analysis: 

The traveling salesman problem when approached from a brute force/exhaustive angle results in a time complexity of (n-1)!, if the implementation utilizes an undirected graph, whereas a directed graph or halving of the results gives a time complexity of ½(n-1)!. This factorial complexity is due the permutational approach used to solve the problem. Permutations by definition are factorials. The TSP problem is said to be NP hard because even the best algorithms (e.g. Held-Karp algorithm) have only achieved a time complexity of O(n^22^n) .

8. Drawback: 

The biggest drawback of this algorithm is its factorial time complexity. As mentioned before, the TSP problem is currently classified as a NP hard problem and even those algorithmic solutions that aren’t factorial in time complexity very much border on the order offactorial. However, for small values of n, this algorithm is still extremely useful.

9. Source Code:

(Java)

http://www.sanfoundry.com/java-program-implement-traveling-salesman-problem-using-nearest-neighbour-algorithm/

(C)

http://programmingpraxis.com/2010/03/12/traveling-salesman-brute-force/

10. Application: 

The applications of this algorithm are enormous. Even with a large time complexity, distribution companies (UPS, Fedex,etc…) can take advantage of this algorithm to more efficiently plan their routes. Communication companies could benefit from the algorithm for routing purposes for both landline and wireless communications. From a biological perspective, open-heart surgeons could greatly benefit when performing bypass surgery, by using the algorithm to plan the most efficient arterial transplant locations. Pathing optimization is a huge area of study and almost any industry and category can benefit, as previously mentioned.