How many possible routes are there for 304 cities in the TSP?

For a Traveling Salesman Problem instance with 304 cities, there are approximately

2.3 x 10^624

possible unique routes. This number is derived from the factorial growth of permutations, specifically (304-1)! / 2, accounting for the fact that the starting city and direction do not matter for undirected cycles.

Conditions

The problem has 304 distinct cities.
Routes are considered as unique Hamiltonian cycles (direction and starting point do not matter).

Reasoning, step by step

Identify the number of cities, $n = 304$ .
Apply the formula for the number of unique undirected Hamiltonian cycles: (n-1)! / 2.
Calculate (304-1)! / $2 = 303$ ! / 2.
Approximate the result as $2.3 x 10^624$ .

Example

The video displays the text '304 Cities' and ' $2.3 x 10^624$ Possible Routes' on screen, illustrating the immense scale of the problem.

Common misconceptions

Believing that the number of routes grows polynomially with the number of cities.
Assuming that the starting city matters for the total number of unique routes in an undirected graph.

Watch the explanation

YouTubeTraveling Salesman Problem Visualization

2:08 – 2:18Watch this moment ↗

Explore next

Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.