Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The 280-Year-Old Algorithm Inside Google Trips

research.googleblog.com

Post reply on HN
Print view View original

31–38 of 38 posts

Re: The 280-Year-Old Algorithm Inside Google Trips

#31

Post by glaberficken »

cjauvin wrote: post #13

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

Re: The 280-Year-Old Algorithm Inside Google Trips

#32

Post by XJOKOLAT »

mavhc wrote: post #23
NicoJuicy wrote: post #19

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 sel…

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.

Re: The 280-Year-Old Algorithm Inside Google Trips

#33

Post by glaberficken »

zump wrote: post #18
rdiddly wrote: post #7

Earlier quoted context omitted.

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?

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

Re: The 280-Year-Old Algorithm Inside Google Trips

#34

Post by 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).

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

Re: The 280-Year-Old Algorithm Inside Google Trips

#35

Post by wtbob »

thr0waway1239 wrote: post #26
wtbob wrote: post #2

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!

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!

Re: The 280-Year-Old Algorithm Inside Google Trips

#36

Post by AstralStorm »

beagle3 wrote: post #20
zump wrote: post #18

Earlier quoted context omitted.

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.)
Post reply on HN