Traveling salesperson problem - jaredgorski.org

Traveling salesperson problem

algorithms

A salesperson must visit 5 cities, all at varying distances from each other. The salesperson doesn’t need to visit the cities in any particular order, but must visit all of them. What is the shortest possible distance the salesperson can travel to visit all 5 cities?

An algorithm:

  • Look at every possible path and pick the path with the lowest total distance
    • For 5 cities, there are 120 possible paths
    • For 6 cities, there are 5040 possible paths
    • For 30 cities, there are 2.6525285981219E+32 possible paths

This algorithm is O(n!) (factorial time/space) in Big O notation. This is a famous problem. There is no fast known algorithm to solve it.