The Travelling Salesman Problem (TSP) is a famous optimisation problem studied in computer science. In the TSP, the salesman must visit every city in a connected road network once only, by the least-cost distances, and return to their starting city.
It belongs in the NP-Class.
Problem Description(s)
Decision Version:
Given a complete graph with a cost , is there a Hamiltonian circuit whose total cost is
The decision version of the TSP is considered much easier to solve than the optimisation version. To verify this problem:
A proof is given. Proof in this case is a tour. For it to be in NP, we must be able to verify this proof with a deterministic algorithm in polynomial time. So first we have to check, whether every city is only visited once. This can be done at most in . Next we need to calculate the distances and sum them up. This can be done as well at most in . The last step is to check whether the calculated length is ≤k. The whole process would require a polynomial time →. - CS Stack Exchange
Therefore the problem is in NP. The problem also falls in NP-Complete due to a proof that finding Hamiltonian circuits is NP-Complete
Optimisation Version:
Given a complete graph , find the minimum cost to complete a Hamiltonian Circuit.
It is important to note that the optimisation problem can be transformed into a decision problem. This problem is NP-Hard because it is considered just as hard, if not harder, than every problem in NP.
Solutions
Exhaustive/Brute-force approach
- Start by choosing a random start node from nodes. possible choices
- Then choose the next node from adjacent nodes, not including the start node. choices
- Keep doing this.
Brute-force results in paths being generated, where is the number of nodes in the graph.
Dynamic Programming approach:#todo
2-opt Algorithm#todo
Analysis
Time Complexity
| Approach | Time Complexity |
|---|---|
| Brute-Force |