KU-forskere hædret for at løse algoritmegåde

I over et halvt århundrede har forskere fra hele verden forsøgt at løse et algoritmisk problem kaldet “the single source shortest path problem”. Problemet handler i hovedtræk om at udarbejde 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.

Den type beregninger bruges i dag i en lang række apps og teknologier, som vi er fuldstændig afhængige af for eksempelvis at kunne finde vej.

Nu er forskere fra Datalogisk Institut på Københavns Universitet altså lykkedes med at løse single source shortest path-problemet. 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.

Den videnskabelige artikel bag opdagelsen er blevet hædret med “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.

Lektor Christian Wulff-Nilsen vurderer, at løsningen 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. Også inden for skibstrafik og handel med valuta ser Christian Wulff-Nilsen anvendelsesmuligheder. På valutaområdet kan algoritmen nemlig bruges til hurtigt at opdage uhensigtsmæssig handel med valuta.

Han understreger, at der i dag allerede 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.