3 ms·
Provably optimal? I thought TSP was NP-Hard and could only ever be solved via heuristics
by alfiedotwtf 6y ago
Provably optimal? I thought TSP was NP-Hard and could only ever be solved via heuristics
- gopiandcode 6y agoNP-hard refers to solving the problem in the general case - for a given specific instance it may be possible to find an optimal solution more easily by exploiting specific features of the graph (for instance, a series of nodes arranged in a ring would have a trivial optimal solution).