The 280-Year-Old Algorithm Inside Google Trips
research.googleblog.com
The 280-Year-Old Algorithm Inside Google Trips
1–10 of 38 posts
Re: The 280-Year-Old Algorithm Inside Google Trips
#2Well, 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!
Re: The 280-Year-Old Algorithm Inside Google Trips
#3Spoiler alert: Euler
Re: The 280-Year-Old Algorithm Inside Google Trips
#4Spoiler alert: Euler
Ummm 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.
Re: The 280-Year-Old Algorithm Inside Google Trips
#5Here, 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?
Re: The 280-Year-Old Algorithm Inside Google Trips
#6Here, 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]
Re: The 280-Year-Old Algorithm Inside Google Trips
#7Spoiler alert: Euler
Ummm 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.
Guilty 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.
Re: The 280-Year-Old Algorithm Inside Google Trips
#8Well, 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!
Pick 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-compu...
Re: The 280-Year-Old Algorithm Inside Google Trips
#9The 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.
Re: The 280-Year-Old Algorithm Inside Google Trips
#10I read trips in the title as a verb.