3 ms·
TSP is NP-hard, like 2^N. The trick is that it's approximate not exact. This could be of interest compared to known heuristic algorithms.
by karmakaze 6y ago
TSP is NP-hard, like 2^N. The trick is that it's approximate not exact. This could be of interest compared to known heuristic algorithms.
- blamestross 6y agoIt is on a planar surface, with a low amount of points. Approximating it to arbitrary precision with 1 processor is polynomial. https://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean https://en.wikipedia.org/wiki/Travelling_salesman_problem#Eu...
- blamestross 6y ago> This could be of interest compared to known heuristic algorithms. The problem is that it isn't. Yes, a big enough cellular automaton can be used to solve problems, but the ratio of "processors" to "problem" isn't practical and we are not learning anything to improve heuristics because the "solution" here is only practical on a 2d surface.