4 ms·
'Electronic amoeba' approximates traveling salesman problem in linear time
- rusticpenn 6y agohttps://www.nature.com/articles/s41598-020-77617-7seems https://www.nature.com/articles/s41598-020-77617-7seems to have more information. I am still not sure how the electronic amoeba works though.
- tgv 6y agoNote: "seems" is not part of the URL. You can also use https://doi.org/10.1038/s41598-020-77617-7 https://doi.org/10.1038/s41598-020-77617-7 It seems to work via n^2 non-linear, interconnected processes; details of the formula for a single process are in the article; it looks like a set of non-linear equations with n^2 variables. It's hard to tell from scanning the article how thoroughly they've tested the problem space, but all kinds of approximations are known for TSP. I recall being told in class about a simple geometric one that was (apparently) proven to get to within 10% or so of the optimal solution, if the distances were L2.
- aaron695 6y agoCyberpunk-ish video they put out explaining it - https://www.youtube.com/watch?v=NKxmO-oXF6o https://www.youtube.com/watch?v=NKxmO-oXF6o I assume by the increasing computer size instead, you can solve it in linear time.