Travelling Salesman Problem
| Artificial Intelligence module, Computer Science 2018. You can find the code by clicking the Github icon. -> |  |
Overview
Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible path that visits every city only once and returns to the origin. The problem is a famous NP hard problem. There is no polynomial time known solution for this problem.
The project aims to build a system in Java that solves travelling salesman problems. The travelling salesman problem is to go to each city exactly once and return to the start. Solving the problem should give a path and the length of the path. There are optimal solutions, that is solutions with the shortest path.
Algorithms Used
Depth First Search
The DFS is the most fundamental search algorithm used to explore nodes and edges of a graph. It runs with a time complexity of O(V+E) and is often used as a building blocks in other algorithms. A Depth First Search plunges depth first into a graph without regard for which edge it takes next until it cannot go any further, at which point, it backtracks and continues.
For the coursework, the use of the DFS is basic. It prints out a single path starting from a starting city. It doesn’t necessarily take the optimal path, but it goes through all the cities and returns to the origin.
Dijkstra’s Algorithm
Dijkstra’s algorithm is a Single Source Shortest Path algorithm for graphs with non-negative edge weights. You maintain a distance array, with length n (n = number of nodes) and the distance to every node is initiated as infinite.
A separate array, parent, is created. Value of parent[n] for a specific node, n, stores parent node of n in shortest path tree. Parent of origin node is -1. Whenever we find shorter path through a node, we make it the parent of current node. This, joined with the nearest neighbor technique, is used as a partially effective way of finding the shortest path. It does get close, but it isn’t always right.
Brute Force
The Brute Force technique consists of methodically computing all possible candidates for the solution and checking the cost of each possible tour, returning to the origin. It does achieve the optimum path, but it is very computationally expensive. This runs with a time complexity of O(n!), where n is the number of nodes in the graph.
Dynamic Approach
The Dynamic Programming solution to the TSP significantly improves the Brute Force technique, taking it from O(n!) to O(n^2*2^n). The main idea is to compute the optimal solution for all the sub paths of length n (n = number of nodes), while using information from the already known optimal partial tours of length n-1.
To compute this, we need to store two things from each case: Set of visited nodes in the sub path, Index of last visited node in the path. The best way to represent the set of visited nodes is to use a single 32-bit integer (as stored in the cache table).
Training Data
Test Data
The test data provided were four text files. The Dynamic Approach did prove to work consistently in this space, given a larger amount of data. However, after forty points, it did seem to give a little trouble.
Conclusion
While there are numerous solutions and algorithms to work through this problem, there is no one right answer and all depends on the search space and depth. The Traveling Salesman Problem (TSP) is believed to be an intractable problem and have no practically efficient algorithm to solve it.
References
Baeldung. (2018). The Traveling Salesman Problem in Java | Baeldung. [online] Available at: https://www.baeldung.com/java-simulated-annealing-for-traveling-salesman [Accessed 10 Dec. 2018].
Bari, A. (2018). 4.7 Traveling Salesperson Problem - Dynamic Programming. [online] YouTube. Available at: https://www.youtube.com/watch?v=XaXsJJh-Q5Y [Accessed 11 Nov. 2018].
Fiset, W. (2018). Graph Theory Playlist - YouTube. [online] YouTube. Available at: https://www.youtube.com/playlist?list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P [Accessed 12 Oct. 2018].
GeeksforGeeks. (2018). Printing Paths in Dijkstra's Shortest Path Algorithm - GeeksforGeeks. [online] Available at: https://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/ [Accessed 9 Dec. 2018].
GeeksforGeeks. (2018). Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming) - GeeksforGeeks. [online] Available at: https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ [Accessed 9 Dec. 2018].
Google+, f. (2018). Applying a genetic algorithm to the traveling salesman problem. [online] Theprojectspot.com. Available at: http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5 [Accessed 03 Dec. 2018].
Programming-algorithms.net. (2018). Travelling salesman problem. [online] Available at: http://www.programming-algorithms.net/article/48915/Travelling-salesman [Accessed 9 Dec. 2018].
Saurel, S. (2018). Calculate shortest paths in Java by implementing Dijkstra’s Algorithm – All for Android, Android for All. [online] Ssaurel.com. Available at: https://www.ssaurel.com/blog/calculate-shortest-paths-in-java-by-implementing-dijkstras-algorithm/ [Accessed 9 Dec. 2018].
0 comments:
Post a Comment