Under Construction: Consider this content a preview of the real thing which is coming soon (hopefully).
The Traveling Salesmen Problem (TSP) is without a doubt the most well-known riddle in computer science. It is in $NP$-hard; however, as discussed, this only means that an efficient algorithm for the general case has never been discovered. There are many tractable approaches.
The formulation of TSP is as follows: a salesperson must visit $n$ cities on a map; find the shortest (or cheapest) route that visits each city exactly once and ends in the same city in which it started. Formally stated, given a complete graph $G = (V, E)$ with non-negative integer costs $c(u, v)$ associated with each edge $(u, v) \in E$ find a Hamiltonian cycle (aka Hamiltonian tour) of $G$ with minimum cost.
A Hamiltonian cycle is a closed loop on an undirected graph where every vertex is visited exactly once. If a graph has more than one vertex and contains a Hamiltonian cycle, it’s known as a Hamiltonian graph. Every complete graph with more than two vertices is a Hamiltonian Graph. This is represented graphically below.
As mentioned earlier, this is an $NP$-hard problem. Every complete graph has $(n-1)!/2$ Hamiltonian cycles. Assuming a single cycle can be evaluated in linear time ($O(n)$), a brute-force search through all possible cycles has a runtime of $\Theta(n!)$. It’s not possible (assuming $P \neq NP$) to find a polynomial time algorithm; however, it is possible to do better than a naive brute-force search. Listed below are a few approaches:
- Dynamic Programming: The Bellman-Held-Karp algorithm is a dynamic programming algorithm that runs in $O(2^n n^2)$. Although not an ideal runtime, it enables far more use-cases than the brute-force version.
- Approximation: There are several approximation algorithms that give near-optimal answers in polynomial time.
- Cutting Planes (http://www.math.uwaterloo.ca/tsp/methods/dfj/index.html)
Applications
Under Construction
Asymptotic Complexity
Under Construction
Pseudo Code
Under Construction
Source Code
Relevant Files:
Click here for build and run instructions