Trips

Hoe Google apps bouwt op basis van een 280 jaar oud wiskundig probleem

De nieuwe Google-app Trips, die deze week in de Play-store verscheen, helpt u tot in het kleinste detail sightseeing-trips plannen. Een vernuftig staaltje van de meest geavanceerde technologie, maar dan wel gebaseerd op een klassiek, 280 jaar oud wiskundig probleem.

Kaliningrad is vandaag een Russische zeehaven, vlakbij de Baltische Zee. Maar in de 18de eeuw raakte de stad wereldberoemd als Königsberg. De stad lag in het Duitse koninkrijk Pruisen en op haar grondgebied herbergde ze een heus wiskundig probleem.

Köningsberg strekte zich uit over de twee oevers van de rivier Pregel. Tot het grondgebied behoorden ook twee eilanden in het midden van de rivier. Zeven bruggen verbonden beide oevers en de twee eilanden. Jarenlang vroegen de inwoners van de stad zich af of ze alle zeven bruggen konden bewandelen, zonder dat ze er eentje meer dan één keer overstaken.

Het antwoord kwam in 1736, toen de Zwitserse wiskundige Leonhard Euler aantoonde dat dat onmogelijk was. Dat kwam, zo luidde zijn verklaring, omdat in elk stadsdeel een oneven aantal bruggen vertrok. Stond er een even aantal bruggen per stadsdeel, dan zou het een heel ander verhaal geweest zijn.

Dit probleem - dat Euler Geometriam Situs noemde - was het begin van wat we nu de grafentheorie noemen. En vele jaren later, nadat Pruisen verdween en Königsberg Kaliningrad werd, vormt het de basis van een app van Google. 

Gevecht met de tijd

De internetreus lanceerde deze week de app Trips, die u helpt met het plannen van uw citytrips in de grootste steden in de wereld. Brengt u bijvoorbeeld een bezoek aan Londen, dan geeft u in hoe lang u in de stad verblijft en serveert Trips u een route van de ene bezienswaardigheid naar de andere. Met net voldoende tijd om te genieten van hoogtepunten als de Big Ben, London Eye en St James's Park.

Daarvoor maakt de app gebruik van twee dingen: een heleboel online gegevens over citytrips die anderen in het verleden maakten, en de Geometriam Situs-theorie van Euler. "Als je weet welke plekken je wilt bezoeken, kan je algoritmes gebruiken die gebouwd zijn op Eulers theorie om de beste route te bepalen", zegt Google-onderzoeker Andrew Tomkins aan de nieuwssite Wired.

In de grafentheorie worden de bruggen van Königsberg 'zijden' genoemd, en de verschillende stadsdelen 'knopen'. In Trips zijn de bezienswaardigheden de zijden, en de routes ertussen zijn de knopen. Ook hier is het probleem: hoe bezoek je alle knopen zonder dat je er een meerdere malen bezoekt. En ook hier is het een kwestie van even en oneven zijden.

Share

In 'Trips' komt er nog een ander klassiek wiskundig probleem om de hoek loeren: het handelsreizigersprobleem

Maar in dit geval is het nog wat ingewikkelder. Google levert immers ook een gevecht met de tijd: hoeveel tijd heeft u nodig om zich van Westminster Abbey naar Buckingham Palace te verplaatsen? Hoeveel tijd spendeert u in Hyde Park, en wat zijn de openingsuren van Madame Tussauds?

En zo komt er nog een ander klassiek wiskundig probleem om de hoek loeren: het handelsreizigersprobleem. Bij dit probleem is het aantal steden gekend, net als de afstand tussen ieder paar van die steden. Om de kortste weg te berekenen, waarbij iedere stad exact één keer bezocht wordt, is er een ander algoritme vereist dat verder bouwt op de grafentheorie. Het algoritme van Christofides werd gepubliceerd in 1976.

Een laatste element dat Google hieraan toevoegt, zijn heel veel gegevens. Dankzij de locatievoorzieningen in zijn smartphones weet het bedrijf hoeveel tijd mensen spenderen aan Big Ben en Buckingham Palace, en op welk moment deze locaties het populairst zijn.

Een reis langs de bruggen van Königsberg behoort met Google Trips echter niet tot de mogelijkheden. Niet alleen bestaat Königsberg niet meer, sommige van de bruggen zijn ook al lang verdwenen.

nieuws

cult

zine