Sometimes the state space is too large and we need to use smart algorithms to attempt the hard problem.
This assignment project consisted of attempting to solve the travelling salesman problem, the NP-Hard problem involves finding a minimal length route between a set of points that visits every point exactly once.
I explored a variety of approaches:
- Brute Force
- Best First Search
- Genetic Algorithm
- A* Search
- Simulated Annealing
The algorithms were implemented in Python for simplicity but highly optimised for both memory and complexity. We showed the space complexity limitations of an A* search approach and saw the strengths of a simulated annealing approach. Although the solutions were not close or proven optimal, we saw that with enough iterations of the genetic or simulated annealing approaches we were able to find short paths.