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

21–30 of 38 posts

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

#21

Post by perfmode »

yomly wrote: post #16
tmptmp wrote: post #15

Earlier quoted context omitted.

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

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

#22

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

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

#23

Post by mavhc »

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?

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

#24

Post by detaro »

mhandley wrote: post #22

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

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

#25

Post by mhandley »

detaro wrote: post #24
mhandley wrote: post #22

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

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

#26

Post by thr0waway1239 »

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

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

#27

Post by raverbashing »

yomly wrote: post #16
tmptmp wrote: post #15

Earlier quoted context omitted.

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

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

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

#28

Post by mseebach »

jsmthrowaway wrote: post #14
MegaDeKay wrote: post #11

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.

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.

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

#29

Post by lordnacho »

tmptmp wrote: post #15
MegaDeKay wrote: post #11

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.

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

https://en.wikipedia.org/wiki/Kobayashi_Maru
Post reply on HN