The 280-Year-Old Algorithm Inside Google Trips | Hacker News Reader

The 280-Year-Old Algorithm Inside Google Trips

research.googleblog.com

178 pointsashishgandhi36 comments

In 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.

In 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.

Business-wise: lease a ferry!

I 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.

>>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.

Isn't changing the problem usually quite an elegant way to solving a problem..? I don't have any examples to hand, but I'm pretty sure being able to rerepresent or slightly change a problem has been applied to great success. In the applied sciences at least...

In the article:

> We take all the destinations that have an odd number of connections in this tree (Euler proved there must be an even number of these), and carefully pair them up. Because all the destinations now have an even number of edges, we’ve created an Eulerian graph, so we create a route that crosses each edge exactly once.

Yes

For theoretical problems sure, you want to solve that problem, though a lot of solutions rely on analyzing a partial graph with some edges removed

For practical problems, changing the problem might be much cheaper/easier than keeping to the original one

https://en.wikipedia.org/wiki/Kobayashi_Maru

A 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

Thank 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

Lol ...

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.

Question is, should you visit somewhere when it's not too busy, or when it is because something's happening?

Nice 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.

Then 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

Well, 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...

How about the right hand rule for getting out of a maze?

http://math.nmsu.edu/~pmorandi/CourseMaterials/Mazes.html

I use that one all the time in crawl & nethack!

There 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).

> Stunning news that Google Trips uses Christofides TSP algorithm. Not a good choice in any practical case.

https://twitter.com/wjcook/status/778323119345901568

He did follow up by saying “Fortunately, Dave Applegate moved to Google Research NYC last month!”

The 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.

Here, 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?

It's interesting that google is now better at planning what you should do than you are.

does this mean Google owes us royalties for using IP they didn't create (public domain)

its amazing to think how talented our ancestors were

Spoiler 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.

Is there an exact solution to the TSP?

Of 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.

It 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.)

If you have interest in this, I suggest this amazing iPython notebook by Peter Norvig:

http://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb

I read trips in the title as a verb.

"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.

How does a cycle have a first and last node?

Yes, 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.

Reply on news.ycombinator.com