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.
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...
> 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.
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.
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:
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)
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.
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.
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!
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.
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.
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.
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.)
"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.
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.
Someone in class responded immediately: "Build another bridge."
The prof congratulated him on his lateral thinking.