
The 280-Year-Old Algorithm Inside Google Trips - ashishgandhi
https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html
======
MegaDeKay
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.

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

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

~~~
raverbashing
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

------
cjauvin
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](http://cjauvin.blogspot.ca/2012/02/implicit-bridges.html)

~~~
glaberficken
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](http://cjauvin.blogspot.pt/2012/02/eulerian-hoax.html)

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

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

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

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

------
wtbob
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!

~~~
thr0waway1239
How 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
I use that one all the time in crawl & nethack!

------
robinhouston
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](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!”

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

------
caf
_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?

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

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

------
priyankasingh
its amazing to think how talented our ancestors were

------
rdiddly
Spoiler alert: Euler

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

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

~~~
zump
Is there an exact solution to the TSP?

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

~~~
AstralStorm
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.)

------
bbcbasic
I read trips in the title as a verb.

------
mhandley
"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
How does a _cycle_ have a first and last node?

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

