4 ms·
The information needed to solve the tsp problem is not the distances matrix. It’s the set of Hamiltonian paths in your graph. And that scales factorially with t
by whatever1 5y ago
The information needed to solve the tsp problem is not the distances matrix. It’s the set of Hamiltonian paths in your graph. And that scales factorially with the number of cities.
It is the subtour elimination (remove cycles) that makes the tsp problem difficult. Not the connectivity.
- gizmo686 5y agoAll the information about the Hamiltonian paths is encoded in your N verticies and N^2 edges. Your arguement suggests the best solution to TSP runs in Θ(n!). However https://en.m.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm https://en.m.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm can solve TSP in Θ(2^n n^2)
- whatever1 5y agoWhich means that many of Hamiltonian paths are strictly dominated than others, so you don’t have to evaluate them at all. Same as in sorting you don’t have to evaluate all of the possible pairs. I did not imply that all information is useful. I proposed that probably there is a lower bound of information that you definitely need to find the optimal solution to the tsp.