TSP
Travelling Salesman Problem
Authors: Alec, Ray
What is the problem?
Travelling Salesman Problem (TSP) is a problem in which a travelling salesman needs to visit all the cities in a given set with the shortest path. TSP is an NP-complete problem, which means that there is no algorithm that can find the optimal solution within polynomial time. Brute force search is the only way that guarantees an optimal solution; however, there are many algorithms that can find effectively short or close to optimal solutions.
We will use Eerke Boiten's Travelling Salesman Heuristics: Exercises in Haskell as a bases for our implementations.
What is the something extra?
We will implement an algorithm which the user can input an arbitrary amount of cities and get the shortest path, We will implement and test out different algorithms and compare the results, including brute force, local search, heuristics, and multiple fragment. We will also add visual parts to show the tours.
What did we learn from doing this?
We learned first hand how functional programming can achieve the same goal/ solve the same problem with less code, less complexity than other programming languages. We also learned how to manipulate matrix and utilize matrix in Haskell to solve problems.