4 ms·
All 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!).
by gizmo686 5y ago
All 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.