3 ms·

As a complete amateur I was wondering if it could be possible to use that property of light ("to always choose the most optimal route") to solve the traveling s

by r34 3y ago

As a complete amateur I was wondering if it could be possible to use that property of light ("to always choose the most optimal route") to solve the traveling salesman problem (and the whole class of those problems as a consequence). Maybe not with an algorithmic approach, but rather some smart implementation of the machine itself.

nkozyra 3y ago
This sounds a bit like LIDAR implementations, I assume you mean something similar at a smaller scale, where physical obstacles provide a "path" representation of a problem space?
- r34 3y ago
  Yup, something like that came to my mind first: create a physical representation (like a map) of the graph you want to solve and use physics to determine the shortest path. Once you have it you could easily compute the winning path's length etc.
shiandow 3y ago
If somehow you can ensure that light can only reach a point by travelling through all other points then yes. It's basically the same way you could use light to solve a maze, just flood the exit with light and walk in the direction which is brightest. Works better for mirror mazes.
pvg 3y ago
Google up 'soap film steiner tree' for a fun, well-known variant of this.
- jerf 3y ago
  Then follow it up with https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf . While reality can "solve" these problems to some extent it turns out that people overestimate reality's ability to solve it optimally.
richk449 3y ago
Sounds like some of the trendy analogy computing approaches, like this one for example: https://www.microsoft.com/en-us/research/uploads/prod/2023/05/Analog-Iterative-Machine-AIM-using-light-to-solve-quadratic-optimization-problems-with-mixed-variables.pdf https://www.microsoft.com/en-us/research/uploads/prod/2023/0...
samatman 3y ago
This is pretty likely, it's been done with DNA: https://pubmed.ncbi.nlm.nih.gov/15555757/ https://pubmed.ncbi.nlm.nih.gov/15555757/ Physics contains a lot of 'machinery' for solving for low energy states.

by r34 3y ago

nkozyra 3y ago

This sounds a bit like LIDAR implementations, I assume you mean something similar at a smaller scale, where physical obstacles provide a "path" representation of a problem space?

r34 3y ago
Yup, something like that came to my mind first: create a physical representation (like a map) of the graph you want to solve and use physics to determine the shortest path. Once you have it you could easily compute the winning path's length etc.

shiandow 3y ago

If somehow you can ensure that light can only reach a point by travelling through all other points then yes. It's basically the same way you could use light to solve a maze, just flood the exit with light and walk in the direction which is brightest. Works better for mirror mazes.

pvg 3y ago

Google up 'soap film steiner tree' for a fun, well-known variant of this.

jerf 3y ago
Then follow it up with https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf . While reality can "solve" these problems to some extent it turns out that people overestimate reality's ability to solve it optimally.

richk449 3y ago

Sounds like some of the trendy analogy computing approaches, like this one for example: https://www.microsoft.com/en-us/research/uploads/prod/2023/05/Analog-Iterative-Machine-AIM-using-light-to-solve-quadratic-optimization-problems-with-mixed-variables.pdf https://www.microsoft.com/en-us/research/uploads/prod/2023/0...

samatman 3y ago

This is pretty likely, it's been done with DNA: https://pubmed.ncbi.nlm.nih.gov/15555757/ https://pubmed.ncbi.nlm.nih.gov/15555757/ Physics contains a lot of 'machinery' for solving for low energy states.