KU-forsker hyldes for løsning af gammel matematisk gåde
fugleperspektiv på kompliceret vejsystem

Opdagelsen kan ifølge Christian Wulff-Nilsen i praksis blandt andet bruges til at hjælpe elbiler med ikke bare at beregne den hurtigste rute på vejene, men også den mest energieffektive. (Foto: Shutterstock)

Opdagelsen kan ifølge Christian Wulff-Nilsen i praksis blandt andet bruges til at hjælpe elbiler med ikke bare at beregne den hurtigste rute på vejene, men også den mest energieffektive. (Foto: Shutterstock)

01 november 2022

Forskere verden over har haft hovedpine over en algoritmisk gåde, der hedder ‘single source shortest path’-problemet, i flere år. 

Det handler i hovedtræk om at finde den korteste rute mellem et punkt og andre punkter i et netværk, hvor der findes negative variable (se en uddybende forklaring længere nede i artiklen).

Nu har den danske forsker Christian Wulff-Nilsen og hans kolleger fra Datalogisk Institut på Københavns Universitet dog formået at løse gåden, og det har udløst hæder rundt omkring i verden.

Det skriver Københavns Universitet i en pressemeddelelse.

Forskningen bygger på et tidligere videnskabeligt gennembrud fra 2021, som Christian Wulff-Nilsen faktisk selv står bag. Det har Videnskab.dk skrevet en artikel om, som du kan læse her.

christian wulff-nilsen pressefoto

Christian Wulff-Nilsens forskning udløste blandt andet prisen for ‘Best Paper Award’ på konferencen Foundation Of Computer Science i Denver, USA, som er den mest prestigefyldte konference inden for teoretisk datalogi. (Foto: Københavns Universitet)

Han forklarer i pressemeddelelsen, at de nu har tilføjet en dimension til den gamle forskning, der kan give nogle helt nye muligheder.

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

Opdagelsen kan blandt andet også få en betydning for handel med valuta. Her kan algoritmen nemlig bruges til at advare for eksempel nationalbanker, hvis spekulanter spekulerer i at købe og sælge forskellige valutaer.

Kort om ‘single source shortest path’-problemet:

  • Målet i single source shortest path-problemet er at finde de korteste veje fra et givent punkt til alle andre punkter i et netværk.
  • Netværket består af knudepunkter og deres forbindelser.
  • Hver forbindelse har en retning, hvilket for eksempel kan repræsentere ensrettede veje, og en variabel, der udtrykker, hvor dyrt det er at rejse med den forbindelse. Hvis alle variable er over nul, kan problemet løses i stort set lineær tid med en klassisk algoritme.
  • Det nye resultat løser problemet i næsten samme tid som en klassisk algoritme, men tillader nu altså også negative variable.

Kilde: Science.ku.dk

jso

Ovenstående er udvalgt og resumeret af Videnskab.dk. Gå til den oprindelige kilde for flere detaljer.