This program was developed for a university assignment. The assignment task was to write a program in C++ that solved the travelling salesman problem given a list of cartesian coordinates representing cities. The task explored various approaches to solving the problem, both analytically and approximately.

 

The first exact method used was a simple brute force search using the Euclidean distance between coordinates. This method was then optimized into a recursive brute force algorithm which formed the second exact method explored. The recursive algorthim uses an array of boolean variables to keep track of the visited cities which is copied in each recursive call to indicate progress. 

 

The recursive brute force algorithm was again optimized into a dynamic programming algorithm which was the third exact method. In addition to replacing the array of boolean from the previous algorithm to a bitmask, this algorithm also introduced memorization into the code. This meant that all previous calculation were stored in memory and the code first checked to see if the current calulation had already been performed. While this increased the memory requirements, it significantly improved the time efficiency.

 

Finally, a fourth method that found approximate solutions to the TSP was also explored. This algorithm combined the minimum spanning tree algorithm and a depth first traversal algorithm to solve the problem. The calculation of the MST required a disjoint set data structure which had to be coded from scratch.

This screenshot shows the program solving the travelling salesman problem with 14 cities. The coordinates were randomly generated by the program. The optimal tour is calculated using the dynamic programming algorithm while the approximate tour uses MST and DFT as mentioned above.