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 podcasts herunder. Du kan også findes os i din podcast-app under navnet 'Videnskab.dk Podcast'.

Videnskabsbilleder

Se de flotteste forskningsfotos på vores Instagram-profil, og læs om det betagende billede af nordlys taget over Limfjorden her.

Ny video fra Tjek

Tjek er en YouTube-kanal om videnskab henvendt til unge.

Indholdet på kanalen bliver produceret af Videnskab.dk's videojournalister med samme journalistiske arbejdsgange, som bliver anvendt på Videnskab.dk.

Hej! Vi vil gerne fortælle dig lidt om os selv

Nu hvor du er nået helt herned på vores hjemmeside, er det vist på tide, at vi introducerer os.

Vi hedder Videnskab.dk, kom til verden i 2008 og er siden vokset til at blive Danmarks største videnskabsmedie med omkring en million brugere om måneden.

Vores uafhængige redaktion leverer dagligt gratis forskningsnyheder og andet prisvindende indhold, der med solidt afsæt i videnskabens verden forsøger at give dig aha-oplevelser og væbne dig mod misinformation.

Vores journalister fortæller historier om både kultur, astronomi, sundhed, klima, filosofi og al anden god videnskab indimellem - i form af artikler, podcasts, YouTube-videoer og indhold på sociale medier.

Vi stiller meget høje krav til, hvordan vi finder og laver vores historier. Vi har lavet et manifest med gode råd til at finde troværdig information, og vi modtog i 2021 en fornem pris for vores guide til god, kritisk videnskabsjournalistik.

Vores redaktion gør en dyd ud af at få uafhængige forskere til at bedømme betydningen af nye studier, og alle interviewede forskere citat- og faktatjekker vores artikler før publicering.

Hvis du går rundt og undrer dig over stort eller småt, vil vi elske at høre fra dig og forsøge at give dig svar med forskernes hjælp. Send bare dit spørgsmål til vores brevkasse Spørg Videnskaben.

Vi håber, at du vil følge med i forskningens forunderlige opdagelser her på Videnskab.dk.

Få et af vores gratis nyhedsbreve sendt til din indbakke. Du kan også følge os på sociale medier: Facebook, Twitter, Instagram, YouTube eller LinkedIn.

Med venlig hilsen

Videnskab.dk