Travelling Salesman Problem
Travelling Salesman Problem
Authors: Daphne Chiu, Jack Griffiths, Melody Lan
What is the problem?
Given a list of cities and the distances between each pair of cities, we want to write a Haskell program to find the shortest possible route that visits each city and returns to the origin city. More information on travelling salesman problem can be found on Wikipedia.
We will solve this problem with a brute force algorithm which will consider all possible routes and choose the shortest route. However, another problem that we will encounter when solving the TSP with a brute force function is that the program crashes when we try to solve the TSP with more than 8 towns. We will address this problem as a part of "something extra".
The TSP is an NP-complete problem, meaning there is no known heuristic that is guaranteed to always give the best solution in a reasonable amount of time. Only the brute force guarantees the best solution every time.
Our functions were implemented based on the instructions of Eerke Boiten's Travelling Salesman Heuristics: Exercises in Haskell. All solutions are our own.
What is the something extra?
On top of using functional programming to solve the travelling salesman problem (TSP), we will address the problem which arises when trying to solve a TSP consisting of 8 or more towns with brute force. Therefore, we will be implementing the brute force solution plus 2 different heuristics which will be able to solve the TSP with more than 8 towns. We will compare the algorithm efficiency of each method to show the need for the 2 heuristics.
What did we learn from doing this? you include the evidence for your claims.
Haskell is useful for solving complex problems by building up from small functions. We built up a solver for TSP problems by starting with matrix functions, then abstracting them to represent distances between cities etc. We also learned that choosing the right algorithm for the job makes all the difference. In our code, there is the 'tsp' function, which does not scale well. For an 8x8 matrix, it took over 20 minutes to return a result, where the 'nn' function, which returns the same results, took way under a second to compute.