3 ms·

My favorite “impossibly difficult” computing problem that’s unsolved (brute force required) by digital but solved by analog is in finding the shortest path from

My favorite “impossibly difficult” computing problem that’s unsolved (brute force required) by digital but solved by analog is in finding the shortest path from A to B, wherein you just apply electricity to the start and endpoint and let the neon glow demonstrate the optimal solution. For example: https://www.nature.com/news/2002/020520/full/news020520-12.html https://www.nature.com/news/2002/020520/full/news020520-12.h...

taktoa 8y ago
I'm pretty sure the actually difficult (i.e.: not handled by the heuristics TSP solvers use in practice) examples for TSP are impractical to convert to a physical object, and I'm not sure that physics would actually do a good job with them. Remember, it's the principal of _stationary_ action, not _least_ action, so it's basically a greedy search.
yorwba 8y ago
Finding the shortest path from A to B is very much a solved problem, e.g. Dijkstra's algorithm can do it in quadratic time on arbitrary graphs. The article tries hard to pretend that the analog method presented could solve traveling salesman problems, but the actual paper only talks about ordinary shortest path problems. I don't see how it could be extended to TSP either, since it's hard to make electrons actually visit all destinations you want to cover when there's a shorter route available.
krastanov 8y ago
While this is certainly a great trick (my favorite version of it is the use of soap bubbles to solve the traveling salesman problem) this solution is certainly no better than what you would achieve with an optimization that runs on a digital computer (and very often it is much worse, given the advances in numerical optimization). There is one very general problem with these "analog" solutions to optimization problems: nature (i.e. the analog computer) quickly finds a local minimum and it does not bother to find a global one (or as the sibling mentioned, it finds a stationary solution, not the true minimal solution). There are tricks you can use to try to search for a better minimum, but all of these tricks are applicable to the digital computer as well. Which is really exciting: you get to talk about annealing and how it works the same in metallurgy and in numerical optimization. Even more fascinating, you get to talk about how a whole host of diseases are inherently due to this "failure of convergence" of analog computers: prion diseases would not exist if analog computers (our cells) folded their proteins to the true minima.
leggomylibro 8y ago
Apparently the Navy also used mechanical 'computers' on old battleships to calculate firing solutions. Sailors would adjust cranks and shafts to set the input values, and those inputs were connected to cams which were machined in the shape of solutions to the equations that needed to be solved. You can watch an old training video about it from the '50s: https://youtu.be/s1i-dnAH9Y4 https://youtu.be/s1i-dnAH9Y4
- benj111 8y ago
  Bombers too. https://en.m.wikipedia.org/wiki/Norden_bombsight https://en.m.wikipedia.org/wiki/Norden_bombsight

taktoa 8y ago

I'm pretty sure the actually difficult (i.e.: not handled by the heuristics TSP solvers use in practice) examples for TSP are impractical to convert to a physical object, and I'm not sure that physics would actually do a good job with them. Remember, it's the principal of _stationary_ action, not _least_ action, so it's basically a greedy search.

yorwba 8y ago

Finding the shortest path from A to B is very much a solved problem, e.g. Dijkstra's algorithm can do it in quadratic time on arbitrary graphs. The article tries hard to pretend that the analog method presented could solve traveling salesman problems, but the actual paper only talks about ordinary shortest path problems. I don't see how it could be extended to TSP either, since it's hard to make electrons actually visit all destinations you want to cover when there's a shorter route available.

krastanov 8y ago

While this is certainly a great trick (my favorite version of it is the use of soap bubbles to solve the traveling salesman problem) this solution is certainly no better than what you would achieve with an optimization that runs on a digital computer (and very often it is much worse, given the advances in numerical optimization). There is one very general problem with these "analog" solutions to optimization problems: nature (i.e. the analog computer) quickly finds a local minimum and it does not bother to find a global one (or as the sibling mentioned, it finds a stationary solution, not the true minimal solution). There are tricks you can use to try to search for a better minimum, but all of these tricks are applicable to the digital computer as well. Which is really exciting: you get to talk about annealing and how it works the same in metallurgy and in numerical optimization. Even more fascinating, you get to talk about how a whole host of diseases are inherently due to this "failure of convergence" of analog computers: prion diseases would not exist if analog computers (our cells) folded their proteins to the true minima.

leggomylibro 8y ago

Apparently the Navy also used mechanical 'computers' on old battleships to calculate firing solutions. Sailors would adjust cranks and shafts to set the input values, and those inputs were connected to cams which were machined in the shape of solutions to the equations that needed to be solved. You can watch an old training video about it from the '50s: https://youtu.be/s1i-dnAH9Y4 https://youtu.be/s1i-dnAH9Y4

benj111 8y ago
Bombers too. https://en.m.wikipedia.org/wiki/Norden_bombsight https://en.m.wikipedia.org/wiki/Norden_bombsight