We hebben het beste pad gevonden tussen de sterren. Het handelsreizigersprobleem, een beruchte wiskundige puzzel die de kortste route zoekt tussen vele locaties, is opgelost op de grootste schaal tot nu toe: de Melkweg.
Het handelsreizigersprobleem lijkt eenvoudig, maar het is een enorm lastige puzzel. Het draait om het vinden van de kortste route tussen vele locaties, waarbij je ze elk slechts één keer bezoekt en uiteindelijk terugkeert naar het beginpunt. Het kan worden opgelost voor bepaalde datasets, maar er is nog geen algemeen algoritme gevonden.
William Cook, wiskundige aan de Universiteit van Waterloo, en Keld Helsgaun, computerwetenschapper aan de Roskilde Universiteit, zijn er nu in geslaagd om de puzzel op de grootste schaal tot nog toe op te lossen.
94.208.157,5 lichtjaar
Hiervoor analyseerden ze gegevens van de Gaia-ruimtetelescoop, die de locaties van 2.079.471 sterren in de Melkweg gemeten heeft. De meest efficiënte route is ongeveer 94.208.157,5 lichtjaar lang, ontdekten de onderzoekers. Ze berekenden dat als er toch een kortere route is, deze niet meer dan een factor 0,0000074 kan afwijken. Dat komt neer op ongeveer 700 lichtjaar. Vervolgens brachten ze de route door de sterren in 3D in kaart.
‘Nu hoef je niet gelijk je warp-motor erbij te pakken’, zegt Cook. Zelfs met de snelheid van het licht zou het bijna honderd miljoen jaar duren om deze reis te maken.
Geen puur academische oefening
Toch is het oplossen van het handelsreizigersprobleem geen puur academische oefening. De methoden die Cook en Helsgaun gebruiken, kunnen ook worden toegepast op andere soorten datasets, zoals vluchtplanning en genetische kaarten. ‘Hoe groter het probleem dat je kunt oplossen, hoe dichter je bij de realiteit kunt komen, oftewel bij het modelleren van de werkelijke wereld’, zegt Cook.
Inmiddels heeft Gaia al meer dan 1 miljard sterren gemeten. De onderzoekers werken nu aan het vinden van de snelste route tussen al die sterren.
Quantum
‘Voor ons onderzoek propten we tweehonderd jaar rekentijd in twee jaar’, zegt Cook. In de toekomst zouden quantumcomputers dat kunnen versnellen. ‘Er zijn echter twee uitdagingen: je moet een goede oplossing vinden en vervolgens bewijzen dat niemand het beter kan’, zegt Cook. ‘Quantum computing zou dat eerste deel in principe heel goed kunnen doen als je een machine had die goed genoeg was.’
Voorlopig zijn quantumcomputers echter niet in staat om zo’n groot probleem op te lossen. Cook belooft dan ook een geldprijs aan iedereen die zijn route tussen de sterren kan verbeteren.
