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 missiles. But in the 18th century, it was a city called Königsberg in the German kingdom of Prussia. And it was a math problem.
Königsberg 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 Königsberg, and for years, people wondered if they could walk across all seven bridges without crossing any of them more than once.
Then, in 1736, the Swiss mathematician Leonhard Euler (pronounced oiler) showed it was impossible. The trouble 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 walk across all the bridges would have been doable. Euler called his work Geometriam Situs, or the Geometry of Place, and it was the beginning of what we now call graph theory. After many years, with Prussia vanishing and Königsberg 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 trips through the world's big cities. You tell it you'll be in Paris for eight hours, and it maps out a path 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 showing sightseeing visits by 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," says Google researcher Andrew Tomkins, who worked on the project. "Euler is a sub-routine for our itinerary work."
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 analyze 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 just very complex linear algebra. But the more important player is graph theory. In graph theory, the Königsberg 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 how long you'll need to travel from stop to stop, how much time 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, 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 says. "We want to pool the collective wisdom."
Which is great. But we have one question: can Google Trips plan us a trip across the bridges of Königsberg? Tomkins says Königsberg isn't on the list of cities covered by Trips, and that makes sense. Königsberg 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.
