Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is not hard to explain. For a given set of cites, visit each city once (once and only once) and minimize the distance you travel. This deceptively simple problem is trivial given a small set of cities, however, as you add more cities the number of possible paths goes through the roof. It should come as no surprise that the TSP is classified as an NP-Hard problem, with the number of Hamiltonian paths being equal to n!/2 where n is equal to the number of cities in the problem.