6 ms·
The 280-Year-Old Algorithm Inside Google Trips
- wtbob 10y agoWell, that's completely and totally awesome — frankly, Cristoferides's algorithm is even cooler than Euler's. I wish I had it at hand last time I was in Europe. I wonder what other algorithms could make my life better, if only I knew of them!
- garrettgrimsley 10y agoPick up a copy of The Algorithm Design Manual or CLRS, they're great! MIT OCW also has a great deal of content covering algorithms. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/ https://ocw.mit.edu/courses/electrical-engineering-and-compu...
- thr0waway1239 10y agoHow about the right hand rule for getting out of a maze? http://math.nmsu.edu/~pmorandi/CourseMaterials/Mazes.html http://math.nmsu.edu/~pmorandi/CourseMaterials/Mazes.html
- wtbob 10y agoI use that one all the time in crawl & nethack!
- rdiddly 10y agoSpoiler alert: Euler
- heimatau 10y agoUmmm no. You read only the first few sentences. Google sought out to also solve the TSP and used the 50 year old Christofides algorithm which is built on top of Euler's bridge problem (graph theory) solution.
- rdiddly 10y agoGuilty as charged - and worse: all I cared about was the source of the 280 years figure, as used in the disingenuous and clickbaity phrase "280-Year-Old Algorithm." I was being all meta. Edit: Also a variation on the TSP was part of my senior project so I am forever traumatized.
- zump 10y agoIs there an exact solution to the TSP?
- beagle3 10y agoOf course. But it's O(n*2^n) at best, IIRC (The trivial is O(n!) - just test all orders) There are simple <=2x and slightly more complicated <=1.5x guaranteed approximate solutions on metric spaces, but on most spaces there aren't even approximate solutions.
- AstralStorm 10y agoIt so happens that a map is a metric space. Euclidean metric. If you want to include transport, change it to optimal travel time metric. (Requires evaluating optimal travel time in the tested vicinity first. There are nice and fast algorithms to do it, starting with variants of A* and IDDFS.)
- glaberficken 10y agoIf you have interest in this, I suggest this amazing iPython notebook by Peter Norvig: http://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb http://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb
- caf 10y agoHere, we use the same techniques to learn about common visit sequences that we can stitch together into itineraries that feel good to our users. Isn't this going to have a kind of self-reinforcing, positive feedback effect?
- deleted 10y ago[deleted]
- jtchang 10y agoThe traveling salesman problem comes up quite often when programming. I'm actually surprised how well written Cristoferides's algorithm was on this blog post. Usually most algorithm explanations are super hard to follow.
- bbcbasic 10y agoI read trips in the title as a verb.
- MegaDeKay 10y agoIn one of my Engineering classes back in the day, our prof told us about the Euler algorithm and that it was impossible to stay off the island in the middle if you could only cross each bridge once and if there were an odd number of bridges. Someone in class responded immediately: "Build another bridge." The prof congratulated him on his lateral thinking.
- jsmthrowaway 10y agoIn this case, both figuratively and literally lateral. I always appreciate three hours of deep compsci thinking interrupted by someone outside saying "why wouldn't we just run an extra cable?" or something. I'm glad your professor encouraged it, because it is very often useful.
- contingencies 10y agoBusiness-wise: lease a ferry!
- mseebach 10y agoI think the biggest "aha-moment" (I believe the kids say "mind blowing" these days) in my entire education was the final few slides of the final class of "Introduction to Algorithms and Data Structures". Basically, if you're able to loosen the constraints of the problem, to solve for the specific case, not the general, by making assumptions about your input data set (perhaps it's almost sorted already) or accepting an only almost-correct solution (say, for travelling salesman, you just want a solution reasonably close to the best, it matters less if it is the best) you can make your algorithms orders of magnitude faster/simpler/better.
- tmptmp 10y ago>>The prof congratulated him on his lateral thinking. May be this is lateral thinking to some people but it's actually changing the problem and not solving the original problem. I can always to pretend to solve the problem by just changing it. Respectfully submitted.
- 10y ago
- bobbles 10y agoThen im sure stage 2 is 'pay $X and guarantee you'll appear on someones itinerary as a suggestion!' Then they have the problem of so many people using an itinerary that it starts warping its own data and thinking places are more popular than they should be based on people getting there from their own recommendations. cool problems to solve though
- cjauvin 10y agoA couple of years ago, I explored the Seven Bridges of Konigsberg problem with a set of interactive processing.js applets.. it might be of interest to some here to feel the impossibility of the task, before understanding it with the classic proof: http://cjauvin.blogspot.ca/2012/02/implicit-bridges.html http://cjauvin.blogspot.ca/2012/02/implicit-bridges.html
- glaberficken 10y agoThank you for this! loved the interactive puzzles. Mind boggling how such a basic geometric shape can be impossible to solve using the simple rule (talking about the triangle puzzle in your follow up page) http://cjauvin.blogspot.pt/2012/02/eulerian-hoax.html http://cjauvin.blogspot.pt/2012/02/eulerian-hoax.html
- NicoJuicy 10y agoLol ... And the crowd has a lot more wisdom to offer in the future. For example, we noticed that visits to Buckingham Palace spike around 11:30 and stay a bit longer than at other times of the day. This seemed a little strange to us, but when we looked more closely, it turns out to be the time of the Changing of the Guard. We’re looking now at ways to incorporate this type of timing information into the itinerary selection algorithms.
- mavhc 10y agoQuestion is, should you visit somewhere when it's not too busy, or when it is because something's happening?
- XJOKOLAT 10y agoNice to have the choice, either way. Have this one for free: I recall visiting Wat Po one evening an hour before closing around sunset. Not only was it unbelievably peaceful and quiet, the guards let us in for free. Love the idea of Google Trips, but it misses the point and beauty of travelling serendipity ... which is arguably the most valuable part of travel. To freely explore and discover. (Edit: accepted, those on a very tight schedule would appreciate this.) Otherwise travel is just a to-do list. Like work. Or an alt-pokemon-go experience. Maybe I'm being unfair.
- mhandley 10y ago"Euler noticed that if all the nodes in the graph have an even number of edges (such graphs are called “Eulerian” in his honor) then, and only then, a cycle can be found that visits every edge exactly once." Unfortunately the article is not quite correct. All non-terminal nodes must have an even number of edges, but the first and last nodes in the cycle can have an odd number.
- detaro 10y agoHow does a cycle have a first and last node?
- mhandley 10y agoYes, you're correct - I shouldn't have said "cycle". I was refering to an Eulerian path, which is all you need to solve the Bridges of Konigsberg problem as it is described in the article. A cycle adds the constraint that the path starts and finishes at the same place, and then all the nodes must have even degree. But you don't need a cycle to just cross all the bridges once.
- priyankasingh 10y agoits amazing to think how talented our ancestors were
- robinhouston 10y agoThere was an interesting comment on Twitter from Bill Cook. He’s one of the leading experts on the Travelling Salesman problem, and also the author of an excellent popular book on the subject (http://press.princeton.edu/titles/9531.html http://press.princeton.edu/titles/9531.html). > Stunning news that Google Trips uses Christofides TSP algorithm. Not a good choice in any practical case. https://twitter.com/wjcook/status/778323119345901568 https://twitter.com/wjcook/status/778323119345901568 He did follow up by saying “Fortunately, Dave Applegate moved to Google Research NYC last month!”
- paulus_magnus2 10y agodoes this mean Google owes us royalties for using IP they didn't create (public domain)
- hrgeek 10y agoIt's interesting that google is now better at planning what you should do than you are.