Tech

Matematisk gennembrud: Dansk forsker har løst årtier gammelt problem

Forskere har i årevis knoklet med løse det matematiske problem. Nu er løsningen endelig fundet.

Foto: Colourbox

Forestil dig et meget kompliceret netværk, hvor punkter er forbundet med hinanden på kryds og tværs. Det kan for eksempel være internettet eller et vejnet fuldstændig proppet med rundkørsler og lyskryds.

Forestil dig så, at forbindelser i netværket bliver fjernet, for eksempel hvis routere går ned, eller veje bliver lukket på grund af trafikuheld.

I årtier har matematikere forsøgt at finde en metode til så hurtigt som muligt at beregne den korteste rute mellem to punkter i sådan et komplekst og foranderligt netværk af forbindelser og knudepunkter.

Nu har en dansk, en tysk og en amerikansk forsker opnået et gennembrud: De har lavet en algoritme, som er så hurtig og præcis til at beregne den korteste rute, at det ifølge forskernes beregninger ikke kan gøres bedre. Det skriver Videnskab.dk.

»Vi viser matematisk, at vi med vores algoritme kan komme ned på en beregningstid, der er optimal. Det betyder, at man ikke kan gøre det hurtigere. Hvis man går 1.000 år ud i fremtiden, kan man ikke gøre det bedre, end vi har gjort,« siger Christian Wulff-Nilsen, der er lektor i algoritmik på Datalogisk Institut på Københavns Universitet.

»Vores algoritme løser hele korteste-vej-problemet inden for den tid, algoritmen er om at kigge på hver eneste forbindelse i hele netværket én gang. Der findes ingen algoritmer, der kan gøre det hurtigere end det,« tilføjer han.

Læs også: Matematiker vinder over 18 millioner kroner

Resultatet er vitterligt et gennembrud

Gennembruddet får ros fra professor Rolf Fagerberg, som ikke selv har været involveret i forskningen, men har læst den videnskabelige artikel.

»Det er et forskningsfelt, hvor der har været utrolig meget aktivitet i de seneste årtier. En masse meget dygtige mennesker har arbejdet hårdt på at løse den type problemer,« siger Rolf Fagerberg, der er professor i datalogi på Syddansk Universitet.

»Så resultatet er vitterligt et gennembrud og et ordentligt skridt fremad inden for denne del af den matematiske grundforskning,« tilføjer han.

Læs mere på Videnskab.dk: Matematikere knækker gammel spaghetti-gåde

Christian Wulff-Nilsen har lavet algoritmen sammen med en ph.d.-studerende og en amerikansk kollega.

Forskerne har fremlagt gennembruddet på den meget anerkendte internationale datalogi-konference FOCS. I den forbindelse er beregningerne blevet kvalitetstjekket af fagfæller.

Artiklen er publiceret i samarbejde med videnskab.dk

BRANCHENYT
Læs også