Traveling Salesman Reference

Question

Can anyone recommend a reference which shows the amount of time required for the Traveling Salesman Problem (TSP) to be solved using brute force as the number of cities increase?

I have informally heard that a computer can not solve the TSP for more than 8 cities using brute force; and after 8 cities, the run time for the TSP becomes in years.

I am very curious to see a reference where a table is given that shows how long a computer takes to solve the TSP for a different number of cities, and then shows the estimated amount of time to find exact solutions as the number of cities grows to around 15 cities.

Can anyone please recommend something?

Note: I found something like this https://www.sciencedirect.com/topics/earth-and-planetary-sciences/traveling-salesman-problem ... but I would be interested in knowing how the time estimates are calculated.

Answer 1

As far as I know, the computation time heavily depends on which software/hardware to be used for that, and maybe there is not an exact reference to this. The brute force algorithm is the easiest algorithm to implement for Traveling Salesman Problem exact solutions. However, it also has the slowest time complexity because the algorithm requires every permutation of a solution to be checked. When every solution has been processed, the cheapest one is chosen. The brute force algorithm has exactly $n!$ permutations that need to be checked. Thus the time complexity is $O{(n!)}$. It turns out that there are exactly $n!$ = $1 \cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n$ different permutations of the numbers from $0$ to $n - 1$.

Also, for computation time, the following table would be interesting: