DIKU-forsker hyldes for suveræn løsning af algoritme-gåde fra 1950’erne

I over et halvt århundrede har forskere verden over haft en gevaldig hovedpine over et algoritmisk problem kaldet ”the single source shortest path problem”. Problemet handler i hovedtræk om at lave en matematisk opskrift, som mest optimalt kan finde den korteste rute mellem et punkt og alle andre punkter i et netværk, hvor der kan være forbindelser med negative vægte.

Lyder det indviklet? Muligvis. Men faktisk bruges den type beregninger i dag i en lang række apps og teknologier, som vi er fuldstændig afhængige af for eksempelvis at kunne finde vej, når vi lader Google Maps guide os gennem landskab og byer. 

Og nu er forskere fra Datalogisk Institut på Københavns Universitet altså lykkedes med at løse single source shortest path-problemet, som for mange forskere og eksperter har været en gåde indtil nu.

”Vi har fundet en algoritme, som løser problemet i stort set lineær tid, hvilket er det hurtigst mulige. Det er et grundlæggende algoritmeproblem som er studeret siden 1950’erne og som der undervises i over hele verden. Det var også var en af årsagerne til, at vi satte os for at løse det,” forklarer lektor Christian Wulff-Nilsen, der tydeligvis har svært ved at lade uløste problemer inden for algoritmernes verden ligge stille hen.

Hurtigere beregning af bedste rute for elbiler

Selvsamme Christian Wulff-Nilsen havde nemlig sidste år et andet stort gennembrud på samme område, Det tidligere resultat handlede om at finde korteste veje i netværk, der ændrer sig over tid. Løsningen af den seneste gåde bygger videre på det arbejde.

Forskeren vurderer, at løsningen af single source shortest path-problemet kan bane vejen for algoritmer, som på et øjeblik kan hjælpe elbiler med ikke bare at beregne den hurtigste rute fra A til B, men også den mest energieffektive.

”Vi tilføjer en dimension, som tidligere algoritmer ikke har. Denne dimension tillader os at kigge på det, vi kalder negative vægte. Et praktisk eksempel på dette kan være alle bakker i et vejnet, som er gode at kende, hvis man har en elbil, der lader op, når den kører nedad,” forklarer Christian Wulff-Nilsen. 

Også inden for skibstrafik og handel med valuta ser Christian Wulff-Nielsen anvendelsesmuligheder ved det nye resultat. På valutaområdet kan algoritmen nemlig bruges til hurtigt at opdage uhensigtsmæssig handel med valuta.     

”Algoritmen vil i princippet kunne bruges til at advare fx nationalbanker, hvis spekulanter spekulerer i at købe og sælge forskellige valutaer. Meget af den slags foregår med computere i dag. Men fordi vores algoritme er så hurtig vil den muligvis kunne bruges til at opdage smuthuller inden de bliver udnyttet,” siger Christian Wulff-Nilsen. 

Forskeren understreger at der i dag findes systemer til at beregne både valuta og ruter til elbilen. Men løsningen af single source shortest path-problemet har gjort forskerne i stand til at lave en suveræn algoritme, som bliver noget nær umulig at overgå i hurtighed. Samtidig er den meget enkel, hvilket gør den lettere at anvende i samfundet.   

Hædres i USA

Arbejdet med at løse problemet er ikke gået ubemærket hen og Christian Wulff-Nilsen og hans kolleger er allerede blevet kontaktet af folk rundt om i verden, som lykønsker forskerne og gerne vil vide mere om, hvordan de gjorde.

Samtidig hædres den videnskabelige artikel bag opdagelsen med en ”best paper award” på konferencen FOCS (Foundation Of Computer Science) i Denver, USA, som sammen med STOC er den mest prestigefyldte konference inden for teoretisk datalogi. Konferencen løber af stablen fra den 31 oktober til den 3. november 2022.   

”Folk kommer fra hele verden til den her konference for at se de bedste resultater blive præsenteret,” siger Christian Wulff-Nilsen.  

Forskningen er sket i et samarbejde mellem Christian Wulff-Nilsen fra Datalogisk Institut, Danupon Nanongkai fra Max Planck Institute og deres amerikanske kollega Aaron Bernstein fra Rutgers University.