Gennembrud: Dansk forsker løser årtier gammelt matematisk problem
I et lille hjørne af matematikken har forskere knoklet i årevis på at løse et grundvidenskabeligt problem. Nu er det lykkedes.
kortest rute matematisk problem matematik netværk grafer

Digitale netværksforbindelseslinjer i Hong Kong Downtown. (Foto: Shutterstock)

Digitale netværksforbindelseslinjer i Hong Kong Downtown. (Foto: Shutterstock)

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. 

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

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. 

Christian Wulff-Nilsen har lavet algoritmen sammen med en phd-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 - se faktaboks herunder.

Konference tæller som en publikation

Indenfor de fleste videnskabelige discipliner udgiver forskere deres resultater i videnskabelige tidsskrifter. Tidsskrifterne får uafhængige fagfæller til at kvalitetstjekke forskningen, før det bliver publiceret.

På den måde sikrer tidsskrifterne, at forskningen er i orden, før det bliver delt. Læs mere om den såkaldte peer review-proces i denne artikel.

Indenfor datalogi er det anderledes:

Datalogi- og algoritmeforskere fremlægger typisk deres forskning på store, internationalt anerkendte konferencer.

Konferencearrangørerne sørger for, at forskningen bliver peer reviewed før fremlæggelsen. Det er også konferencen, der publicerer de fremlagte studier. 

Datalogikonferncen FOCS er en af to hovedkonferencer indenfor faget.

Studiet ligger desuden offentligt tilgængeligt på en preprint-database.

Et klassisk matematisk problem

At beregne den korteste vej mellem to punkter i et netværk er et helt klassisk matematisk problem, som findes i mange forskellige varianter. 

»Den klassiske variant er den, hvor man antager, at der ikke er uregelmæssigheder, og at netværket ikke forandrer sig. Allerede i 1950’erne begyndte man at lave algoritmer, der kunne løse det problem,« fortæller Christian Wulff-Nilsen.  

»I 80’erne begyndte man så at spørge sig selv: Kan man gøre det bedre? Og så startede et helt nyt forskningsfelt, hvor man arbejder med dynamiske netværk, der ændrer sig over tid,« forklarer han. 

Vejnet er et konkret eksempel på netværk, som ændrer sig: Når veje bliver spærret på grund af trafikuheld, vejarbejde eller maratonløb, forandrer netværket sig.

I dag bruger vi GPS’er til at finde vej. GPS’erne bruger computeralgoritmer til at regne ud, hvilken rute ud af flere mulige der er kortest, selv om en vej bliver lukket.

Algoritmen håndterer de tungeste netværk

Vejnet er dog relativt simple, fordi de fleste vejkryds kun består af fire veje. Hvis nettet var mere indviklet, og hvis der konstant blev fjernet veje, ville traditionelle algoritmer stå af: 

Algoritmerne ville lave mange fejl, eller de ville være ekstremt langsomme til at beregne den korteste vej. Det skyldes ifølge Christian Wulff-Nilsen, at de skal finde en ny løsning helt fra bunden, hver gang et komplekst netværk ændrer sig.

»GPS-software kan heller ikke håndtere andre typer netværk end vejnet. Vores algoritme kommer udenom begge problemer,« siger han. 

I algoritmik - en videnskabelig disciplin, der ligger i krydsfeltet mellem matematik og datalogi - kaldes komplekse netværk for grafer. 

»Vejnet er typisk ikke de tætteste grafer, for et knudepunkt i et vejkryds har kun fire forbindelser. Men forestil dig, at du har ti knudepunkter, som er forbundet til ni andre. Så er det et tæt netværk,« siger Christian Wulff-Nilsen.

»Vores algoritme håndterer de netværk, der er tungest at arbejde med. Det vil sige grafer, som er meget tættere end vejnet,« tilføjer han.

Et skub på en 3.000 år gammel mur

Udfordringen med at beregne den korteste rute i meget komplekse netværk, der forandrer sig, kendes af matematikere som ‘Decremental Single-Source Shortest Path-problemet.’. 

Matematikmuren

Rolf Fagerberg sammenligner fremskridt i matematisk grundforskning med at skubbe til en mur: 

»Når muren bevæger sig, afsløres ny viden. Forskere undersøger muren for, hvor den er blød og kan flyttes, enten ved hjælp af eksisterende matematiske værktøjer eller ved hjælp af nye værktøjer, som man udvikler i processen,« siger Rolf Fagerberg. 

»De nye værktøjer kan være lige så vigtige som det egentlige resultat, fordi værktøjerne måske kan bruges andre steder på muren,« tilføjer han.

Men hvad kan løsningen på problemet egentlig bruges til i praksis? Nok ikke ret meget på nuværende tidspunkt, siger Rolf Fagerberg. 

»Det er grundforskning i den forstand, at praktisk anvendelse ikke nødvendigvis er tæt på. Men i et hjørne af den matematiske videnskab er det et stort skridt frem,« siger han. 

Til forskel fra den type forskning, hvor man starter et projekt med henblik på at løse et helt konkret, praktisk problem, er formålet med grundforskning udelukkende at gøre os klogere og rykke videnskaben fremad. Det kan du læse om i artiklen Hvad er grundforskning?

Rolf Fagerberg bruger en mur, der rykker sig, som et billede på, hvordan matematisk videnskab gennem årtusinder har bevæget sig fremad: 

»Matematik har eksisteret i mere end 3.000 år. Gennem rigtig mange år har vi skubbet muren langt ved at løse flere og flere problemer. Forskerne bag det nye resultat kan siges at have skubbet et hjørne af muren et godt stykke,« siger han og tilføjer:

»Metoderne, de her har opfundet, kan samles op af andre forskere, der arbejder med grafer og netværk, så forskningsfeltet kan rykke sig endnu mere. Både de nye resultater og de nye værktøjer fra grundforskningen er så til rådighed for forskere, som arbejde på at løse konkrete, praktiske problemer.«

Videnskab.dk Podcast

Lyt til vores seneste podcast herunder eller via en podcast-app på din smartphone.

Danske corona-tal

Videnskab.dk går i dybden med den seneste corona-forskning. Læs vores artikler i temaet her.

Hver dag opdaterer vi også de seneste tal.

Dyk ned i grafer om udviklingen i antal smittede, indlagte og døde i Danmark og alle andre lande.

Ny video fra Tjek

Tjek er en YouTube-kanal om videnskab, klima og sundhed henvendt til unge.

Indholdet på kanalen bliver produceret af Videnskab.dk's Center for Faglig Formidling med samme journalistiske arbejdsgange, som bliver anvendt på Videnskab.dk.


Ugens videnskabsbillede

Se flere forskningsfotos på Instagram, og læs her om, hvordan forskerne tog billedet af atomerme.