Page 8 - Grafentheorie HS 5 Handelsreizigersprobleem

HS 5 Handelsreizigersprobleem

Het ultieme record
William Cook, wiskundige aan de Universiteit van Waterloo, en Keld Helsgaun, computerwetenschapper
aan de Roskilde Universiteit, zijn er nu in geslaagd om het handelsreizigersprobleem op de grootste
schaal tot nog toe op te lossen: de melkweg.

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 voor de sterren in 3D in kaart.
Zelfs met de snelheid van het licht zou het bijna honderd miljoen jaar duren om deze reis te maken.
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.

‘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.

t
e
n
.
o
l
e
h
t
a
m
.
w
w
Interactieve versie: http://www.math.uwaterloo.ca/tsp/star/star10k.html w

© 2021 Ivan De Winne ivan@mathelo.net 7