News for hackers. Stuff that matters.
Re:Electronic amoeba finds solution to traveling salesman pr... by hpcjoe on Sunday December 13, 2020 @02:11PM (#25409171)
Analog computers for the win.
Re:Electronic amoeba finds solution to traveling salesman pr... by blamestross on Sunday December 13, 2020 @02:17PM (#25409231)
Give me O(N) processors to solve an O(N^2) problem and I could do it in O(N) time too. The whole trope "slime mold solves TSP" is overblown.
Re:Electronic amoeba finds solution to traveling salesman pr... by karmakaze on Sunday December 13, 2020 @04:31PM (#25410489)
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.
Re:Electronic amoeba finds solution to traveling salesman pr... by blamestross on Sunday December 13, 2020 @05:13PM (#25410891)
> 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.

Re:Electronic amoeba finds solution to traveling salesman pr... by blamestross on Sunday December 13, 2020 @05:09PM (#25410859)
It 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#Eu...