Computer Scientists Break Traveling Salesperson Record(quantamagazine.org)
quantamagazine.org
Computer Scientists Break Traveling Salesperson Record
https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/
187 comments
Meanwhile in an agile dev team.... "can you optimize it in the next sprint?"
“so you don’t have anything to demo, then?”
Interestingly, I demoed and shipped a wayfinding solution for a mobile app earlier this year, where I just brute forced the shortest paths between all pairs ~200 "intersections" in the area of interest for this event, and just stored the answers in a KV store based on the intersections (then does some cheesy last 20m stuff to route you to and from the nearest intersections to your location and destination).
In a limited-enough space (like an event), this works out just fine. I'm glad I'm not the guy who needs to solve GoogleMap's routing problems though. I wonder if they have a huge BigTable store of every street intersection pair on the planet and a recalculated best route between them? I _hope_ they do something smarter than my "works in my constrained requirements space" brute-force hack...
In a limited-enough space (like an event), this works out just fine. I'm glad I'm not the guy who needs to solve GoogleMap's routing problems though. I wonder if they have a huge BigTable store of every street intersection pair on the planet and a recalculated best route between them? I _hope_ they do something smarter than my "works in my constrained requirements space" brute-force hack...
Route-finding is much simpler than traveling salesperson.
The hard part for real-world directions is getting the cost-function right. Older map systems used to make some very questionable assumptions that made them quite inaccurate (one example; assume all highway miles are equal; some were 55MPH and have traffic lights, railroad crossings and stop-signs others were 65 with no at-grade intersections -- today even higher speed limits are seen as the lingering effects of the national speed-limit have worn off).
The hard part for real-world directions is getting the cost-function right. Older map systems used to make some very questionable assumptions that made them quite inaccurate (one example; assume all highway miles are equal; some were 55MPH and have traffic lights, railroad crossings and stop-signs others were 65 with no at-grade intersections -- today even higher speed limits are seen as the lingering effects of the national speed-limit have worn off).
We have a related problem in the UK. Sometimes very small "country lanes" have no explicit speed limit, so defaults to national speed limit of 60mph, which you would have to be suicidal to drive at (or just hate your car), but Google maps still often route finds along these roads.
An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A
An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A
Except that Google uses an average of the recorded speed of vehicles using a road segment, linked to time of day, and not the speed limit.
This. Google has a major advantage in that they have a massive dataset. They can use their data to improve the cost function even in real time to detect traffic.
... which, given that most people are speeding, makes their estimates completely unrealistic if you want to actually obey the law.
So they should add a "route options" -> "follow speed limits" checkbox, or track your speed compared to the average driver.
Winding British country lanes aren’t a bug, they’re a feature!
As someone that sees 65 as an overly cautious limit and not precisely born in the US, what do you mean by the effects have worn off?
Up until around 1990 or so 55MPH was the maximum speed limit; this was originally to conserve fuel. Up until 1995 55MPH was the maximum except for roads very far from population centers.
Even after 1995, many states were very slow to raise the speed limit (I lived near the Maryland/Virginia boarder and remember Maryland did well before Virginia), and when they did raise the speed limit it was by small amounts.
Today, you can drive from Los Angeles to New York and not hit any significant stretches of freeway with speedlimits under 65, and west of the Mississipi river, you will spend most of it at 70mph or higher.
On top of that, the actual speed that will get you pulled over can be much higher (In CA you are very unlikely to get pulled over for single-digit MPH speeding on a freeway, making a 65 speed limit a de-facto 74; in the northeast US it's not uncommon to get pulled over for going just 5MPH over the posted limit).
Even after 1995, many states were very slow to raise the speed limit (I lived near the Maryland/Virginia boarder and remember Maryland did well before Virginia), and when they did raise the speed limit it was by small amounts.
Today, you can drive from Los Angeles to New York and not hit any significant stretches of freeway with speedlimits under 65, and west of the Mississipi river, you will spend most of it at 70mph or higher.
On top of that, the actual speed that will get you pulled over can be much higher (In CA you are very unlikely to get pulled over for single-digit MPH speeding on a freeway, making a 65 speed limit a de-facto 74; in the northeast US it's not uncommon to get pulled over for going just 5MPH over the posted limit).
> Up until around 1990 or so 55MPH was the maximum speed limit
The NMSL (National Maximum Speed Limit) was enacted in 1973, modified in 1987 to allow 65 mph speed limits on rural interstates, and repealed in 1995.
Many states in the southeast, midwest and west raised their posted speed limits very soon after the NMSL was repealed. States in the northeast took a bit longer to update their laws to remove their state maximum speed limit.
The NMSL (National Maximum Speed Limit) was enacted in 1973, modified in 1987 to allow 65 mph speed limits on rural interstates, and repealed in 1995.
Many states in the southeast, midwest and west raised their posted speed limits very soon after the NMSL was repealed. States in the northeast took a bit longer to update their laws to remove their state maximum speed limit.
chuckles in german
Edit: to add value to the conversation: in germany I find googles estimates on long car trips quite accurate. And I'm actually a very erratic driver, sometimes taking every hole in traffic I can to get ahead, just slowing down to speed limit+20km/h where there is a speed trap, sometimes just cruising 80km/h on open autobahn getting overtaken by cargo trucks
Edit: to add value to the conversation: in germany I find googles estimates on long car trips quite accurate. And I'm actually a very erratic driver, sometimes taking every hole in traffic I can to get ahead, just slowing down to speed limit+20km/h where there is a speed trap, sometimes just cruising 80km/h on open autobahn getting overtaken by cargo trucks
> chuckles in german
FWIW, Advisory speed-limits on autobahn are similar to the western US statutory speed limits (130km/h == 80mi/h). That being said, 200km/h and no other moving violations would quite possibly get you thrown in jail in "The land of the free"
FWIW, Advisory speed-limits on autobahn are similar to the western US statutory speed limits (130km/h == 80mi/h). That being said, 200km/h and no other moving violations would quite possibly get you thrown in jail in "The land of the free"
When my local public transport (bus+train) did a major-ish route overhaul, routing directions on Maps glitched out for a couple days and showed large "black spots" (maybe 5-15mi in size?) where regions of generally accurate/useful routing were slapstuck together with large straight lines that cut diagonally through backyards, houses, major highways, etc (and sadly didn't account for runway room so weren't even flyable). So in a scenario where you were zoomed out enough to see 2-3 towns, you'd get a complex route shape in one part of the map, another complex route shape in another part of the map, then one single "nope I can't do this" giant line connecting the two regions. The giant line often connected to the complex shapes at awkward angles, eg 60-70°.
Unfortunately IIRC most of the screenshots I took show my actual address/immediate surrounding area etc, so they'd be fairly heavily censored. If anyone [is actually reading this and] is especially interested, I can try braving my scary not-organized screenshot archive and try and find them.
Unfortunately IIRC most of the screenshots I took show my actual address/immediate surrounding area etc, so they'd be fairly heavily censored. If anyone [is actually reading this and] is especially interested, I can try braving my scary not-organized screenshot archive and try and find them.
Check out google-ortools which does just this.
"This sounds like a ten-pointer."
Lately it feels like agile is where innovation goes to die :(
Nobody needs too "innovate" another stupid CRUD app though...
I kinda feel all the _actual_ innovation is doing things that align with Agile's underlying principals of valuing individuals/working-software/response-to-changes over processes/documentation/plans - while all th3e people who _talk_ about doing "Agile" rarely follow those principals, and mostly just mean "We have meetings we call 'standups', and negotiated deadlines that we call 'sprints'".
I kinda feel all the _actual_ innovation is doing things that align with Agile's underlying principals of valuing individuals/working-software/response-to-changes over processes/documentation/plans - while all th3e people who _talk_ about doing "Agile" rarely follow those principals, and mostly just mean "We have meetings we call 'standups', and negotiated deadlines that we call 'sprints'".
I agree. It’s sad. Agile principles are awesome, but by the time you run them through many company’s implementations of Scrum or SAFe or (God forbid) Jira, you may as well just do waterfall.
I don’t think waterfall is necessarily bad, that agile is always right, or that there aren’t other good practices. But practicing waterfall and calling it “agile” is rarely going to end well for anyone.
I don’t think waterfall is necessarily bad, that agile is always right, or that there aren’t other good practices. But practicing waterfall and calling it “agile” is rarely going to end well for anyone.
We do Scrum at my office. But really, it's just applying sprints to waterfall. We do get some shorter feedback loops to improve features before going live. But the whole scope is still set at the start of the project, and that scope needs to be completed at the end of it.
And to be very honest. It doesn't work if the people in the team don't think Agile. Your team needs to be able to self-reflect and try to improve themselves just as they'll do with client work in a sprint.
And to be very honest. It doesn't work if the people in the team don't think Agile. Your team needs to be able to self-reflect and try to improve themselves just as they'll do with client work in a sprint.
I mean it is a ️️hot-take but I don't regard scrum as any sort of subset of agile. Rather scrum emerged when big companies wanted to basically do what they were already doing, but call it agile. A framework emerged to teach these companies a “safe word” rendition of agile, don't worry it's only agile until you say “banana.”
You cannot appoint somebody to the strange title of “scrum master” (which I guess makes the rest of us scrum slaves?) to lead a process of “daily scrum” where we look together at a kanban board and make sure that we are “sprinting” and then turn around to insist that you value “individuals and interactions over processes and tools,” which is ¼ of the Manifesto. You have voted with your intention and your vote was to value your process and tools over trusting the individual developers and letting them have direct interactions with your customers.
Even the word “sprint.” I used to play Ultimate in one of the teams in the Dutch national league, it is a sprinting sport. The word “sprint” means exhaustion. It means stopping. If you jog around in Ultimate you lose, you have to rest, sprint, rest, sprint. If your model is “always sprinting” then do not tell me that you value “individuals and interactions.” And if you do value the latter please either (a) remove the metaphor “sprint” from your process or (b) add “rest weeks” after each sprint to “clean up” the mess you made! Anything else is lying to yourself.
The phenomenon of estimating “story points” is even worse, no? It is intrinsically about processes and tools and the idea of a developer having a phone call or face-to-face with the client directly to see if this feature request is actually accurate, deciding that it is not, and trashing it to open a different request... it's not just “do we claim those juicy story points when this happens?” but also “was part of your measure of ‘complexity’ the complexity of determining that the Ask did not meet the Need?” ...And so the fundamental idea of estimating a “todo” does not fit well with agile, whereas you can estimate “in progs” and “done” just fine.
And before you say “no by the time we estimate we should already know that we want the feature, devs should never have to talk to clients,” please be aware that this response explicitly abdicates another ½ of the Agile manifesto, “customer collaboration over contract negotiation” and “responding to change over following a plan.” The whole point of the Agile manifesto is that your kanban board is stale. Not because it's a kanban board, but because it is written down. Like one of the four principles (the last ¼ not covered in the above ¾) is explicitly anti-literary.
This is sort of “no true Scotsman” of me but my read is that the moment Agile was systematized, it died a little on the inside. It was a “screw your systems!” reaction that then got steamrollered by the real world, where “bullshit jobs” and middle management reign even though they bespeak a bureaucratic feudalism rather than a lean-and-mean capitalism.
You cannot appoint somebody to the strange title of “scrum master” (which I guess makes the rest of us scrum slaves?) to lead a process of “daily scrum” where we look together at a kanban board and make sure that we are “sprinting” and then turn around to insist that you value “individuals and interactions over processes and tools,” which is ¼ of the Manifesto. You have voted with your intention and your vote was to value your process and tools over trusting the individual developers and letting them have direct interactions with your customers.
Even the word “sprint.” I used to play Ultimate in one of the teams in the Dutch national league, it is a sprinting sport. The word “sprint” means exhaustion. It means stopping. If you jog around in Ultimate you lose, you have to rest, sprint, rest, sprint. If your model is “always sprinting” then do not tell me that you value “individuals and interactions.” And if you do value the latter please either (a) remove the metaphor “sprint” from your process or (b) add “rest weeks” after each sprint to “clean up” the mess you made! Anything else is lying to yourself.
The phenomenon of estimating “story points” is even worse, no? It is intrinsically about processes and tools and the idea of a developer having a phone call or face-to-face with the client directly to see if this feature request is actually accurate, deciding that it is not, and trashing it to open a different request... it's not just “do we claim those juicy story points when this happens?” but also “was part of your measure of ‘complexity’ the complexity of determining that the Ask did not meet the Need?” ...And so the fundamental idea of estimating a “todo” does not fit well with agile, whereas you can estimate “in progs” and “done” just fine.
And before you say “no by the time we estimate we should already know that we want the feature, devs should never have to talk to clients,” please be aware that this response explicitly abdicates another ½ of the Agile manifesto, “customer collaboration over contract negotiation” and “responding to change over following a plan.” The whole point of the Agile manifesto is that your kanban board is stale. Not because it's a kanban board, but because it is written down. Like one of the four principles (the last ¼ not covered in the above ¾) is explicitly anti-literary.
This is sort of “no true Scotsman” of me but my read is that the moment Agile was systematized, it died a little on the inside. It was a “screw your systems!” reaction that then got steamrollered by the real world, where “bullshit jobs” and middle management reign even though they bespeak a bureaucratic feudalism rather than a lean-and-mean capitalism.
Is there some sort of guidance/explanation you could point to for implementation of "proper" agile development? I'm really interested in learning more about it :)
So the vision statement is on agilemanifesto.org and to a lesser extent the "principles behind the agile manifesto" on the same page.
What I am challenging in the above is that there is a "lip service" given rather than a deep assimilation. So when the principles say "business people and developers must work together daily throughout the project" they mean that there should be an open-door policy, “hey Amanda I am working on the Estimating-Work-in-Process application and I was wondering what you do with ____” “Oh, that is not supposed to be possible,” type of interactions. The ‘lip service’ is “your boss will answer any questions at daily stand-up.”
Because these interactions are routine, the idea of needing constant scheduling and progress updates ideally ‘should be’ a lesser issue. People want progress updates to make sure that you are not spending all your time on Reddit, they will be able to see that more readily if they see you working.
The core of agile is anti-establishment thinking. One of the principles is “The best architectures, requirements, and designs emerge from self-organizing teams. At regular intervals, the team reflects on how to become more effective, then tunes and adjusts its behavior accordingly.” Elsewhere Don Wells elaborates on it, “Don't panic. With professional software engineers on our project we can relax knowing that the team will do what is needed to get the job done. Any activity needed with any combination of people will just get done without any further scheduling or ceremony. This is the spirit and benefit of a self organizing team.”
And so a fundamental idea of agile, perversely enough, is that you’re not going to have one size fits all, there is no one ‘proper implementation.’ There is just the way that you made it work. If you have different personalities it’s gonna express differently.
I am not being facetious here, though I realize it sounds kind of like it! Adam Savage had a great video a little while back about something unrelated—weathering prop money—where he took live questions from the audience, and one question was about “the best way” to make that money look bloody, and he answered in true artisan style:
> So, your question though, “what is the best way”... The answer is, there is no, there is no best way! There is the way you figure out how to do it. Yeah! That’s really the thing. It may be that you’ve gotta, like, take a brush and kinda work at a whole bunch of different bills, and then take the stack and then effect the stack, right?, I think that’s like a multi-stage process, and then you should do some tests with different paints and see, like, under the lighting conditions these will be seen—I don’t know if it’s for a theater or a film—does it communicate? Does it tell you that it’s bloody, dirty money? That’s the question to be asking, you gotta hold it up, look at it, [mimes looking at it and pausing and thinking] “does that sell to me?”—and ask other people, “does this sell?”... and like most of the time they’re gonna go, “no,” and you’re gonna keep on going. But it’s trial and error.
And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work” and the answer is usually “no, Leah is totally burned out after she had to work 60+ hours of straight development that one week,” or “Alvin is having trouble with nobody inviting him in, he wants to start contributing to this project and everybody is like ‘nah man we got it’ and he is being excluded” and you’re gonna have to reshape. There is a necessary aspect of vulnerability in other words in any proper development strategy whether top-down design-first waterfall or agile or something else.
There is no one agile software development process. There is a set of agile software development values. It is a values-driven approach, “how are we living up to our self-commitments today?” rather than “did I follow the appropriate procedure?” And thus it is quite anarchist at its fundamental core. This is probably why I am ragging on scrum in the end, scrum came in and said “there is a non-anarchist way to do agile” and I am sitting here like “uh, do you know what you just said?”
With that said, all the usual caveats, I understand that you want to be able to state what all is likely to be in an upcoming release and what all isn’t and this requires creating estimates and so forth. But perhaps the most damning thing is when estimates turn into deadlines. When an estimate becomes a deadline it gets padded and re-padded, then the urgency of the feature gets de-emphasized because you have such an abundance of time to do it in, so you spend a bunch of time up-front completing your “design doc” about what you are about to build and then someone asks to weigh in and “approve it” and you have reinvented waterfall.
What I am challenging in the above is that there is a "lip service" given rather than a deep assimilation. So when the principles say "business people and developers must work together daily throughout the project" they mean that there should be an open-door policy, “hey Amanda I am working on the Estimating-Work-in-Process application and I was wondering what you do with ____” “Oh, that is not supposed to be possible,” type of interactions. The ‘lip service’ is “your boss will answer any questions at daily stand-up.”
Because these interactions are routine, the idea of needing constant scheduling and progress updates ideally ‘should be’ a lesser issue. People want progress updates to make sure that you are not spending all your time on Reddit, they will be able to see that more readily if they see you working.
The core of agile is anti-establishment thinking. One of the principles is “The best architectures, requirements, and designs emerge from self-organizing teams. At regular intervals, the team reflects on how to become more effective, then tunes and adjusts its behavior accordingly.” Elsewhere Don Wells elaborates on it, “Don't panic. With professional software engineers on our project we can relax knowing that the team will do what is needed to get the job done. Any activity needed with any combination of people will just get done without any further scheduling or ceremony. This is the spirit and benefit of a self organizing team.”
And so a fundamental idea of agile, perversely enough, is that you’re not going to have one size fits all, there is no one ‘proper implementation.’ There is just the way that you made it work. If you have different personalities it’s gonna express differently.
I am not being facetious here, though I realize it sounds kind of like it! Adam Savage had a great video a little while back about something unrelated—weathering prop money—where he took live questions from the audience, and one question was about “the best way” to make that money look bloody, and he answered in true artisan style:
> So, your question though, “what is the best way”... The answer is, there is no, there is no best way! There is the way you figure out how to do it. Yeah! That’s really the thing. It may be that you’ve gotta, like, take a brush and kinda work at a whole bunch of different bills, and then take the stack and then effect the stack, right?, I think that’s like a multi-stage process, and then you should do some tests with different paints and see, like, under the lighting conditions these will be seen—I don’t know if it’s for a theater or a film—does it communicate? Does it tell you that it’s bloody, dirty money? That’s the question to be asking, you gotta hold it up, look at it, [mimes looking at it and pausing and thinking] “does that sell to me?”—and ask other people, “does this sell?”... and like most of the time they’re gonna go, “no,” and you’re gonna keep on going. But it’s trial and error.
And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work” and the answer is usually “no, Leah is totally burned out after she had to work 60+ hours of straight development that one week,” or “Alvin is having trouble with nobody inviting him in, he wants to start contributing to this project and everybody is like ‘nah man we got it’ and he is being excluded” and you’re gonna have to reshape. There is a necessary aspect of vulnerability in other words in any proper development strategy whether top-down design-first waterfall or agile or something else.
There is no one agile software development process. There is a set of agile software development values. It is a values-driven approach, “how are we living up to our self-commitments today?” rather than “did I follow the appropriate procedure?” And thus it is quite anarchist at its fundamental core. This is probably why I am ragging on scrum in the end, scrum came in and said “there is a non-anarchist way to do agile” and I am sitting here like “uh, do you know what you just said?”
With that said, all the usual caveats, I understand that you want to be able to state what all is likely to be in an upcoming release and what all isn’t and this requires creating estimates and so forth. But perhaps the most damning thing is when estimates turn into deadlines. When an estimate becomes a deadline it gets padded and re-padded, then the urgency of the feature gets de-emphasized because you have such an abundance of time to do it in, so you spend a bunch of time up-front completing your “design doc” about what you are about to build and then someone asks to weigh in and “approve it” and you have reinvented waterfall.
You thoroughly explained exactly what I meant in my comment.
I've only seen scrum implemented as a planning tool. But the teams aren't truly agile.
> And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work”
This is exactly what I meant with needing the team to be able to self-improve based on experiences. You can trial-and-error velocities all you want. But if you don't employ that same agility on a deeper level it's never going to work anyway.
I've only seen scrum implemented as a planning tool. But the teams aren't truly agile.
> And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work”
This is exactly what I meant with needing the team to be able to self-improve based on experiences. You can trial-and-error velocities all you want. But if you don't employ that same agility on a deeper level it's never going to work anyway.
I have a hunch that one of the reasons "Agile" becomes ruined is the complexity of the stack most teams are using. IIRC, the stories/tasks were originally meant to be able to be completed by anyone on the team with little help from specialists/others within a reasonable time (..including UI?). When the Frontend Engineer needs to wait on Design, coordinate with Backend (ex: discussing API), or even wait for the S3 bucket to be up, mini-waterfalls will be the easiest path to take.
Waterfall is actually agile, if one bothers to read the original paper properly, regardless of its bad name.
The whole idea of waterfall as I know it is to have large-ish iterations (typically a couple months), which comprise of analysis, dev and testing stages. Is this different from what you have in mind?
That is page one of the waterfall document, there are other pages though.
https://pragtob.wordpress.com/2012/03/02/why-waterfall-was-a...
https://pragtob.wordpress.com/2012/03/02/why-waterfall-was-a...
Ah, not to worry. Modern agile is just waterfall, but with shorter timelines to maximize overhead costs and minimize productivity. It makes sense when you realize that we pay employees for days to elapse.
Two weeks ago I heard a colleague say: "I'm a scrum master in a waterfall project". That was my last week at that IT consulting company and really confirmed my choice to switch to a career with more purpose.
Is that a euphemism for unemployed?
"Well, let's not risk going live with the new version for such a small improvement. You know, premature optimizations are the root of all evil!"
Just do a PoC, and we'll improve it later.
Ok boss. We'll keep a cache of the best known route for the most common queries or fallback onto the existing algo.
> Yet this minuscule improvement breaks through both a theoretical logjam and a psychological one. Researchers hope that it will open the floodgates to further improvements.
Please don't take quotes out of context
Please don't take quotes out of context
That's precisely why I put Here's hoping for a flood of further improvements.
This wasn't intended to be read as sarcastic. It really is a great development. It's still amusing that the number is so tiny.
This wasn't intended to be read as sarcastic. It really is a great development. It's still amusing that the number is so tiny.
ah sorry I read the whole thing in a sarcastic voice
Honestly this sounds like taken from The Onion.
While it is wonderful they are getting closer to solving it, if your problem is a simple and practical you can try some alternative algorithms. For fun, I used pytspsa [0] which uses the simulated annealing method to solve the TSP and applied it to BOTW.
Simulated annealing was inspired by thermodynamic free energy involved in crystal formation from annealing metal. [1]
I combined it with a Breath of the Wild waypoint generator [2] to make my way around the map [3] in a mostly optimal fashion for my trip about Hyrule.
If you ever have a toy problem or even a real one, I suggest experimenting with pytspsa to see and understand in a concrete way the problem is solved.
[0] https://github.com/ildoonet/simulated-annealing-for-tsp
[1] https://en.wikipedia.org/wiki/Simulated_annealing
[2] https://github.com/MrCheeze/botw-waypoint-map
[3] https://user-images.githubusercontent.com/2829875/28661246-0...
Simulated annealing was inspired by thermodynamic free energy involved in crystal formation from annealing metal. [1]
I combined it with a Breath of the Wild waypoint generator [2] to make my way around the map [3] in a mostly optimal fashion for my trip about Hyrule.
If you ever have a toy problem or even a real one, I suggest experimenting with pytspsa to see and understand in a concrete way the problem is solved.
[0] https://github.com/ildoonet/simulated-annealing-for-tsp
[1] https://en.wikipedia.org/wiki/Simulated_annealing
[2] https://github.com/MrCheeze/botw-waypoint-map
[3] https://user-images.githubusercontent.com/2829875/28661246-0...
Ah, I used Ant Colony Optimization to solve it a long time ago. I love simulated annealing, but in many cases the swarm based methods seem to perform better.
This is great, thanks for sharing!
I had good results with genetic algorithms as well.
I had good results with genetic algorithms as well.
There are also TSP-specific heuristics that work well in practice on a lot of large instances, often finding the optimal solution pretty quickly (but with no guarantees of optimality). The first I believe was the Lin-Kernighan heuristic from 1973 (the same Kernighan as the 'K' in K&R C, incidentally). There are fast implementations of some modern improved versions, e.g.: http://akira.ruc.dk/~keld/research/LKH/
I believe that this is about a different type of TSP problem, where the distances between cities are defined by the geometric distance from their coordinates in some plane (or on a sphere). This is a simpler problem than when the distances are specified as (whole) numbers.
Geometric distance implies symmetry, asymmetric TSP can be converted to symmetric by doubling the number of vertices.
I coded a version of SA for TSP in the early 90s. I iterated until the probability of a hardware error was greater than having a sub-optimal solution. It took just a couple of seconds, and that speed was due to visually displaying the algorithm as it executed.
Looking at the BOTW solution is doesn't seem to take into account the fact that a straight line is not the fastest solution. Climbing is incredibly slow, swimming is slow and perilous, in some places such as the dark forest you can only enter/exit in one place, not randomly, you can travel faster on roads.
I guess later in the game one doesn't mind randomly walking right by the castle just because it is the shortest path, just going to eat some time dealing with each guardian of course.
Same for swimming across a the river twice around a bend rather than just following the coastline.
Also there are 226 waypoints, the linked map is missing a lot...
I am not sure what it is trying to show. Was this the waypoints you had not done at the end of the game?
I guess later in the game one doesn't mind randomly walking right by the castle just because it is the shortest path, just going to eat some time dealing with each guardian of course.
Same for swimming across a the river twice around a bend rather than just following the coastline.
Also there are 226 waypoints, the linked map is missing a lot...
I am not sure what it is trying to show. Was this the waypoints you had not done at the end of the game?
Hey man, this is just a person’s fun and imaginative side project. Is there a reason you’re offering such serious and negative critical commentary on this?
I think the parent wanted to point out that this is about a completely different problem. The algorithm mentioned works on cities that are defined with coordinates in some plane and where the distances between two points is defined as the geometric distance. The article talks about the problem where the distances between cities are given (and not based on their coordinates). The later is a much harder problem.
The original paper mentioned in the article [1] deals with metric TSP, so a triangle inequality must be satisfied. This means that you can actually find a space where the points will be the coordinates.
Anyway, the grandparent solves the Euclidean TSP which is still an NP-complete problem. I will be reluctant to say that it is an easier problem in a general sense. I agree though that there are better and easier approximations for it.
[1] https://arxiv.org/abs/2007.01409
Anyway, the grandparent solves the Euclidean TSP which is still an NP-complete problem. I will be reluctant to say that it is an easier problem in a general sense. I agree though that there are better and easier approximations for it.
[1] https://arxiv.org/abs/2007.01409
> proved that an algorithm devised a decade ago beats Christofides’ 50% factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.
That is 0.0000000000000000000000000000000002% better than the existing solution.
That is 0.0000000000000000000000000000000002% better than the existing solution.
So much less than the 0.01% of the variation in identical computers due to 100ppm crystal variation. Also less than the 0.0001% variation due to the temperature in the room changing 1 degree.
Wonder if it's less than the probability of getting hit by a cosmic ray flipping a bit somewhere in the implementation and changing the result.
This is very interesting.
Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?
Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?
XEONs use a 100MHz referenced called "BCLK" and scale this up to the different frequencies it needs internally (core, dram, pci, etc.). Typically this info is found in the datasheet, but only the DC parameters (voltage min/max) etc were found in the first datasheet I found. Timing is so important that often processor manufacturers will have an apnote discussing it in detail, often with suggested parts and circuit layouts.
https://www.intel.com/content/www/us/en/products/docs/proces...
https://www.intel.com/content/www/us/en/products/docs/proces...
That’s might be all they were able to prove, although in practice the results may be much better.
Is it a probabilistic improvement, like over millions of iterations?
It does mention choosing tree paths at random... so couldn't that be an improvement by chance?
It does mention choosing tree paths at random... so couldn't that be an improvement by chance?
No, they don't just random sample the base trees and hope for a better result. Their "actual work" is providing a 80 page proof for their improvement.
Are you missing two zeros or am I counting incorrectly? The paper claims an improvement of 10-36 or smaller
Percent moves two zeros over factor
The paper is really nicely written: https://arxiv.org/abs/2007.01409
It's lengthy and full of some quite technical sections, but those are interspersed with sections sketching the high-level intuition and proving more informal versions of the technical theorems in simplified cases. An example is on p. 19, section 3.1, "Ideas underlying proof of Theorem 3.1".
It's lengthy and full of some quite technical sections, but those are interspersed with sections sketching the high-level intuition and proving more informal versions of the technical theorems in simplified cases. An example is on p. 19, section 3.1, "Ideas underlying proof of Theorem 3.1".
"A (Slightly) Improved Approximation Algorithm for Metric TSP" is a pretty funny headline.
Nathan Klein's talk is also nice: https://www.youtube.com/watch?v=TE6puoxv2wY
Very tangential, I was a physics major, and learned about Traveling Salesperson when in college at UCSD - I looked it up in the library and there was like, an entire hallway of books/research on this problem and it blew my mind. It really put into perspective how much work had gone into that single problem. I think the shelf was larger than the solar physics papers on file in a nearby area.
Oh man, it's actually a real improvement! I was afraid it was more pop sci, but not this is pretty cool.
I think this is the paper? https://arxiv.org/abs/2007.01409
I think this is the paper? https://arxiv.org/abs/2007.01409
Heh. For some definitions of "real".
> they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.
> they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.
Looks like a real number to me
“The algorithm we study is very similar, except we choose a random spanning tree based on the standard linear programming relaxation of TSP.”
That’s so subtle to suggest but incredible hard to prove
https://arxiv.org/abs/2007.01409
That’s so subtle to suggest but incredible hard to prove
https://arxiv.org/abs/2007.01409
So, how many kms would be to visit the 1,904,711-city instance throughout the world?[1] I'm already packing.
[1]: http://www.math.uwaterloo.ca/tsp/world/
[1]: http://www.math.uwaterloo.ca/tsp/world/
It looks like it's predicated on an assumption that "nodes with odd numbers of edges have short edges." It's novel, but not reliable. I do love the breakdown and effort though - very useful.
> It's novel, but not reliable.
Isn't that really the best we can hope for? It's an NP-complete problem, but we can still realistically hope that researchers might discover efficient algorithms for solving subsets of the problem space, hopefully broad subsets.
If we get to the point that 90% of travelling salesman problems can be solved quickly, and the remaining 10% can quickly be approximately solved (to within 5% percent of the optimum solution, say), that would be pretty great, even if we never 'really' crack NP-complete problems. (Which, of course, might not even be possible.)
As an example, a smart TSP algorithm should be able to very quickly solve problems where all nodes fall on points in a circle.
(Disclaimer: this stuff isn't my wheelhouse, corrections welcome.)
Isn't that really the best we can hope for? It's an NP-complete problem, but we can still realistically hope that researchers might discover efficient algorithms for solving subsets of the problem space, hopefully broad subsets.
If we get to the point that 90% of travelling salesman problems can be solved quickly, and the remaining 10% can quickly be approximately solved (to within 5% percent of the optimum solution, say), that would be pretty great, even if we never 'really' crack NP-complete problems. (Which, of course, might not even be possible.)
As an example, a smart TSP algorithm should be able to very quickly solve problems where all nodes fall on points in a circle.
(Disclaimer: this stuff isn't my wheelhouse, corrections welcome.)
> It's an NP-complete problem
Finding the optimal solution is NP-complete, but approximations are not necessarily so:
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co...
Finding the optimal solution is NP-complete, but approximations are not necessarily so:
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co...
Right, I should have made that point more clear.
The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems.
Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.
The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems.
Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.
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?
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.
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.
probably
circuit satisfiability and related hard problems are all reducible to each other
circuit satisfiability and related hard problems are all reducible to each other
Or use deep learning to generate solutions 2 orders of magnitude faster with some minor accuracy loss.
https://arxiv.org/pdf/1905.05567.pdf
https://arxiv.org/pdf/1905.05567.pdf
Apparently, heuristics are still better than DL-based solutions for the TSP
From the paper you linked:
heuristics based solutions are still superior to deep learning based solvers regarding accuracy and execution time for larger problem sizes.
From the paper you linked:
heuristics based solutions are still superior to deep learning based solvers regarding accuracy and execution time for larger problem sizes.
Pretty much any decent off the shelf algorithm is faster than deep learning if you allow it the same accuracy loss.
This is kind of a hijack, but it's at least related: Are there any websites/apps that can approximate a solution for road destinations in the real world?
For example, given a list of cities, an approximate solution on actual roads to visit all of them once?
For example, given a list of cities, an approximate solution on actual roads to visit all of them once?
I'd say this is pretty decent but it's not a proper TSP app, since it expects the first and last points as fixed but has the option to change the order of the other stops
https://www.mapquest.com/routeplanner
https://www.mapquest.com/routeplanner
Yeah this is not what I meant at all. I'm looking for something that me, a normal boring non-tech end user can use.
So I guess if you're not a developer, the answer is "no".
Someone should make a front end for this.
Someone should make a front end for this.
While not entirely obvious on Google Maps you can add multiple stops and reorder them for fastest route (including traffic which you might not be able to get w/ OR-Tools), https://support.google.com/maps/answer/144339
For people that want to argue about salesperson vs salesman you may be comforted to know that you don't need to, it's already being done!
https://en.wikipedia.org/wiki/Talk:Travelling_salesman_probl...
https://en.wikipedia.org/wiki/Talk:Travelling_salesman_probl...
What of the people wanting to argue about the two different (correct) spellings of 'travelling/traveling' used in this thread?
That was just them describing random internal wikipedia things with a debate about google scholar. There wasn't really a debate there...
If you search the page for "salesperson" there are other debates.
It reminds me of when at some point in the 90s everyone decided to stick it to jesus by changing B.C. to B.C.E.
> In 1856, Rabbi and historian Morris Jacob Raphall used the abbreviations CE and BCE in his book Post-Biblical History of The Jews
Older than you’d think.
Older than you’d think.
elygre(2)
growlist(3)
...
> “This is a result I have wanted all my career,” said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s
I love this. Oh to be a theoretician.
Here's hoping for a flood of further improvements.