Kaliningrad is a Russian seaport named for a Soviet revolutionary. It sits near the Baltic Sea, between Poland and Lithuania, and it’s a place where pre-Putin Russian leaders would occasionally threaten to install nuclear weapons. But in the 18 th century, it was a city called Knigsberg in the German kingdom of Prussia. And it was a math problem.
Knigsberg stretched across both banks of the river Pregel, and it included two islands in the middle of the river. Seven bridges connected these islands and the rest of Knigsberg, and for years, people wondered if they could stroll across all seven bridges without traversing any of them more than once.
Then, in 1736, the Swiss mathematician Leonhard Euler( pronounced oiler ) indicated it was impossible. The difficulty was that each landmass–the two islands and the two river banks–were touched by an odd number of bridges. If each was touched by an even number, a continuous stroll across all the bridges would have been doable. Euler called his run Geometriam Situs , or the Geometry of Place, and it was the beginning of what we now call graph hypothesi. After many years, with Prussia vanishing and Knigsberg morphing into Kalingrad and the Soviet Union giving way to Putin’s Russia, it produced an app from Google.
This week, Google unveiled a smartphone app that helps you plan your vacations. It’s called Trips, and among other things, it will automatically plan sightseeing trip-ups through the world’s big cities. You tell it you’ll be in Paris for eight hours, and it maps out a track from one notable sight to another, giving you just enough time to enjoy one before moving to the next. It does this with two things: scads of online data presenting sightseeing his mission to others in the past, and Euler’s Geometry of Place.
” If you know the places you want to visit, you can use algorithms built on top of Euler to figure out the best route ,” tells Google researcher Andrew Tomkins, who worked on the project.” Euler is a sub-routine for our itinerary run .”
In recent years, Google and other Internet operations like Facebook and Amazon have changed the way we live through the analysis of massive amounts of data. Inside Google Research, Tomkins was also part of the team that built Smart Reply, a Gmail tool that has learned to automatically respond to emails by investigate millions of existing replies, and so many others are doing similar work with not only email messages, but photos and spoken words and even computer viruses and targeted ads. But it’s worth remembering that none of this is magic--not even the deep neural networks that are built in the image of the human brain. At the bottom of it all, this is just good old fashioned math. Sometimes, it’s 280 -year-old math.
Under the covers, Trip does make use of neural networks, which is really merely very complex linear algebra. But the more important player is graph hypothesi. In graph hypothesi, the Knigsberg bridges are called edges and the landmasses are called nodes , and Google can apply this model to the cities where Trips maps out your daily sightseeing. The sights are the edges, and the roads between them are the nodes. Again, the basic problem is: can you visit all the edges without visiting any of them more than once? It’s a matter of even edges versus odd.
But it’s also more complicated than that. Google must also consider the appropriate means that may long you’ll need to travel from stop to stop, how much hour you’ll need for each, when sights are open and when they’re closed, and so on. As Tomkins explains, it morphs into another classic math problem–the one about the traveling salesman–and this requires another algorithm that builds on Euler’s graph theory. This one, “ve called the” Christofides algorithm, is a bit younger. It was published in the great year of 1976.
What Google is adding to all this is data–lots and lots of data. Thanks to location services built into Android phones, it knows how much time people spend at Big Ben and Parliament and Buckingham Palace. It knows which sites are must popular when.” There are a lot of people who have done this before ,” Tomkins tells.” We want to pool the collective wisdom .”
Which is great. But we have one question: can Google Trips plan us a trip-up across the bridges of Knigsberg? Tomkins tells Knigsberg isn’t on the listing of cities covered by Trips, and that attains sense. Knigsberg doesn’t exist anymore, and some of the bridges are no longer there. Which is too bad. We’d like to see Google try the impossible.