Løsningen på gåden kan hjælpe elbiler med at spare på batteriet og gøre livet sværere for valutaspekulanter i fremtiden. Opdagelsen har netop vundet prisen som bedste videnskabelige artikel og hædres denne uge på den mest prestigefyldte konference på området i USA.
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.
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, fortsætter 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.
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 er 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 er netop blevet afholdt i dagene mellem 31. oktober og 3. november 2022.
– Folk kom fra hele verden til den her konference for at se de bedste resultater blive præsenteret, siger Christian Wulff-Nilsen oven på konferencen.
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.
Fakta om single source shortest path-problemet
Målet i single source shortest path-problemet er at finde de korteste veje fra en given startknude til alle andre knuder i et netværk. Netværket er repræsenteret som en graf bestående af knudepunkter og forbindelser mellem disse kaldet kanter.
Hver kant har en retning (dette kan f.eks. bruges til at repræsentere ensrettede veje) samt en vægt, der udtrykker, hvor dyrt det er at rejse langs denne kant. Hvis alle vægte er ikke-negative, kan problemet løses i stort set lineær tid med en klassisk algoritme af Dijkstra. Det nye resultat løser problemet i næsten samme tid som Dijkstras algoritme, men tillader negative kantvægte.
Kontakt: Christian Wulff-Nilsen, Datalogisk Institut, SCIENCE, Københavns Universitet, mail: koolooz@di.ku.dk
