News for hackers. Stuff that matters.
Re:Computer Scientists Break Traveling Salesperson Record by sigmaprimus on Thursday October 08, 2020 @10:20PM (#24726095)
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?
Re:Computer Scientists Break Traveling Salesperson Record by lamchob on Friday October 09, 2020 @05:18AM (#24728160)
Maybe, 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.
Re:Computer Scientists Break Traveling Salesperson Record by sigmaprimus on Friday October 09, 2020 @02:35PM (#24732935)
Interesting 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.
Re:Computer Scientists Break Traveling Salesperson Record by ellis-bell on Thursday October 08, 2020 @11:01PM (#24726310)
probably

circuit satisfiability and related hard problems are all reducible to each other