Bagsiden: Dansk ruteplanlægger til Mælkevejen

Den gennemsnitlige afstand mellem stjernerne i Mælkevejen er ca. fem lysår, men da de 2.079.471 stjerner i Gaia-kataloget kun er en lille brøkdel af samtlige stjerner, giver det mening, at det svarer til en gennemsnitsafstand på ca. 50 lysår Illustration: Nasa Illustration: Nasa

Den rejsende sælgers problem er et af de mest klassiske optimeringsproblemer - det var været kendt siden 1832. Problemet består i at finde den korteste rute for en sælger, der skal besøge et antal byer og vende hjem til sit udgangspunkt.

Tidligere på året jublede japanske elektroingeniører fra Tokyo University of Science over, at de havde designet et specielt kredsløb, der på et øjeblik kunne løse problemet for op til 22 byer. Det var en klar forbedring af den hidtidige rekord på 16 byer.

Med en mere konventionel computer ville en sådan beregning tage omkring 1.600 år, og for 28 byer ville Jorden være forsvundet, før beregningerne var foretaget, har israelske forskere vurderet.

Men der findes heldigvis programmer, som kan komme med rigtig gode tilnærmede løsninger på langt kortere tid. Et af dem er udviklet af lektor emeritus Keld Helsgaun fra Roskilde Universitet.

Hans samarbejdspartner William Cook fra University of Waterloo i Canada beretter på sin hjemmeside, at med Keld Helsgauns LKH-program har de to forskere beregnet det absolut største rejsende sælgers problem, som består i at finde den korteste rundtur til de 2.079.471 stjerner i Mælkevejen, som er kortlagt af den europæiske Gaia-satellit.

LKH er i øvrigt en forkortelse for Lin-Kernighan- Helsgaun, idet Keld Helsgauns algoritme tager udgangspunkt i en algoritme udviklet af Brian Kernighan og Shen Lin.

Mælkevejen har en ­radius på 52.850 lysår. Den ­korteste tur rundt til de godt to milliarder stjerner er estimeret til at være næsten 100 millioner lysår – mere præcist 94.208.157 og et halvt. Helsgaun og Cook har tilmed bevist, at hvis det ikke er den absolut korteste rute, så afviger den mindre end en hundrededel promille fra den korteste – 697 lysår i absolutte tal. Det kan man sikkert godt leve med som rejseplanlægger. /ram

Illustration: Ingeniøren