4 ms·
I was just thinking on the TSP the other night, would a practical application of this problem(and solution) be to use it in processor circuit layout and trace r
by sigmaprimus 6y ago
I was just thinking on the TSP the other night, would a practical application of this problem(and solution) be to use it in processor circuit layout and trace routing? Then using the improved processor to solve the problem again?
- ellis-bell 6y agoprobably circuit satisfiability and related hard problems are all reducible to each other
- lamchob 6y agoMaybe, but a real challenge of circuit layout and routing is that you want to generate (mostly) planar graphs, since your options for intersecting connection lines are limited and expensive. For the TSP, this does not really matter since the problem is more abstract.
- sigmaprimus 6y agoInteresting point, TBH I had never considered applying the TSP to any more than two dimensions, as it becomes exponentially more difficult with each node added even within the same plane. I'm not even sure if adding more dimensions would make it more difficult or not but You have me thinking on that now, so thank You.