I 1959 blev den korteste vej fra Rotterdam til Groningen fundet. I dag er det næsten umuligt at fare vild

Et problem, som de fleste – matematikere eller ej – kan forstå, er at finde vej. Løsningen på problemet er også relativt simpel: Man vil gerne komme fra det ene sted til det andet hurtigst muligt. I dag er det utrolig nemt, uanset hvor i verden, man befinder sig, hvis bare man har adgang til en GPS eller Google Maps. På et par millisekunder kan man finde den korteste vej til Faxe Ladeplads eller Frankrig, på gåben, cykel, med offentlig transport eller i bil.

Det skyldes en algoritme til at finde den korteste rute, som matematikeren og datalogen Edsger W. Dijkstra udviklede i slutningen af 1950’erne.

Trods den varige indflydelse af Dijkstras arbejde, var det ikke særligt anstrengende. Som han selv beskrev det i et interview fra 2001: “En morgen var jeg ude at handle i Amsterdam sammen med min forlovede, og da vi var trætte, satte vi os på en caféterrasse for at drikke en kop kaffe, og jeg sad bare og tænkte over, om jeg kunne gøre det, og så udviklede jeg algoritmen til den korteste rute.”

På dette tidspunkt handlede nærmest alt om hardware, og man tenderede til at undervurdere vigtigheden af software.

Faktisk designede Dijkstra også denne algoritme på grund af et splinternyt stykke hardware, nemlig computeren ARMAC. “Vi skulle lave en demonstration [af den nye computer]. ARRA havde nogle år tidligere været så upålidelig, at den eneste sikre demonstration, vi turde lave, var generering af tilfældige tal, men med den mere pålidelige ARMAC kunne jeg prøve noget mere ambitiøst,” forklarede han i det samme interview.

I 1959 udkom hans algoritme, der ifølge Dijkstra selv viste sig at være meget vellykket. Så vellykket, at det stadig er hans grundidé, som vi bruger til at finde den korteste rute i dag.

Dijkstras algoritme er en grafalgoritme, og en graf består af punkter, også kaldet knuder, forbundet af linjer, også kaldet kanter. Det er også det, som man kalder en grådig algoritme, det vil sige, at den ved hvert enkelt trin vælger den bedste mulige løsning.

“Du har en graf, og du har en startposition i grafen, og du vil gerne finde afstanden – fra startpositionen og så til en anden given position eller bare fra startpositionen og til alle andre punkter i grafen. Dijkstras oprindelige algoritme handler om at finde den korteste vej til alle mulige punkter,” forklarer Eva Rotenberg, som er professor ved IT-Universitetet i København og har beskæftiget sig med grafalgoritmer såsom Dijkstras.

Så lad os sige, at jeg er i byen A. Fra byen A til byen B er der en lige vej, der tager 5 minutter, og den lige vej fra byen A til byen C tager tilsvarende 10 minutter. Byerne er grafens punkter, vejene er grafens kanter, og tiden mellem punkterne er vores afstandsmål. Den korteste vej fra A til B må selvfølgelig være den lige vej, og denne kant kan grådigt tilføjes til vores løsning: det kan aldrig betale sig at gå via C.

Lad os nu forestille os, at der fra byen B til byen D er der en lige vej på 14 minutter, og fra byen B til byen E er der tilsvarende 7 minutter. Så har vi følgende byer, vi endnu ikke kender afstanden til: C, D og E, med afstand fra A værende henholdsvis 10, 5+14=19 og 5+7=12. Det grådige valg er nu at fastlåse den korteste vej til C, som vi kan nå på samlet 10 minutter fra startpositionen A.

“Hvis der findes en vej, du kan nå på 10 minutter, så giver det ikke mening at udforske de veje, der kommer op på en samlet rejsetid på 14 eller 12 minutter fra startpositionen. Og så bliver du ved med hele tiden at tilføje det punkt, der samlet set er tættest på startpunktet,” siger Rotenberg.

Til sidst har jeg en samlet graf, hvor jeg kan finde den hurtigste vej fra startpositionen til ethvert andet punkt.

Mindst muligt kompleks

Edsger W. Dijkstras algoritme var en god algoritme, fordi den løste et problem rigtigt og simpelt – den kunne beskrives som værende elegant. Og det skyldes faktisk selve måden, som den var blevet lavet på, fortalte han i interviewet fra 2001: “En af grundene til, at det blev så godt, var, at jeg designede den uden blyant og papir. Uden blyant og papir er man nærmest tvunget til at undgå alle unødvendige komplikationer.”

Selvom algoritmer virker og kan være utrolig komplekse, så er målet, når man designer dem, at de udover at løse det givne problem, skal være praktisk muligt og mindst muligt komplekse.

“Det er det, der driver mig,” siger Eva Rotenberg.

“Altså simplifikation. Matematikere har altid gjort det, dataloger har også gjort det længe, men det er at tage noget, hvor alle ved, at den eksisterende løsning er kompliceret, men virker, og prøve at lave en simpel konstruktion, som er nemmere at forklare og nemmere at implementere eller generalisere. Alle de ting går hånd i hånd. Hvis du laver noget, der er simplere, så er det nemmere at forstå, det er nemmere at læse, det er nemmere at tjekke, at det er korrekt, og det er nemmere at søsætte det i praksis.”

Som computere udbredes i 1960’erne og 1970’erne, bliver det en disciplin og en videnskab at designe algoritmer og vurdere deres design. To af de grundlæggende parametre er henholdsvis tids- og pladskompleksitet. Tidskompleksitet handler om antallet af trin i den trinvise procedure, mens pladskompleksitet drejer sig om, hvor meget hukommelse algoritmen skal bruge for at kunne køre.

Selvom Dijkstras algoritme var god, kunne den godt blive bedre. Og det blev den i første omgang, da en række forskere ændrede på det algoritmiske design. De fastholdt Dijkstras grundidé om den grådige algoritme, men ændrede datastrukturen. Det betød, at algoritmen var mere kompleks at implementere, men til gengæld blev meget hurtigere.

Der skete flere forbedringer i slutningen af det 20. århundrede, men forskerne begyndte at tænke, at de var nået til vejs ende. “Forskningen var i bero i meget lang tid. Mange tænkte, at der ikke fandtes nogen bedre løsning,” har Ran Duan, som er datalog ved Tsinghua-universitetet i Beijing, udtalt til Wired.

Det der stod i vejen var den såkaldte “sorteringsflaskehals”. Først i 2025 lykkedes det et forskerhold fra Tsinghua University i Beijing at klemme sig igennem denne flaskehals. Det skyldtes ikke teknologisk udvikling, men kreativ tænkning.

Som Mikkel Thorup, der er professor i datalogi ved Københavns Universitet, også sagde til samme artikel Wired: “Det her kunne lige så godt være blevet opdaget for 50 år siden, men det blev det ikke. Det gør det så meget mere imponerende.”

Grønne algoritmer

Mens effektive algoritmer løser problemer hurtigere, kan algoritmisk design i sig selv være afgørende i forhold til et af de største problemer: Klima- og miljøkrisen.

Ifølge en ny rapport fra FN’s tænketank UN University vil verdens datacentre i 2030 have et strømforbrug, der er næsten tre gange så stort som Pakistan, Bangladesh og Nigerias tilsammen, mens vandforbruget vil svare til 1,3 milliarder menneskers årlige forbrug.

Algoritmisk effektivitet kan spille en rolle, fordi hver eneste trin i en algoritme kræver strøm til processoren, mens hukommelsen koster strøm, når data gemmes og tilgås.

Rapporten fremhæver ligeledes algoritmisk effektivitet som en af byggestenene til et balanceret KI-økosystem, men advarer samtidig: “Hvis en mindre miljøpåvirkning pr. anvendelse fører til en stigning i forbruget, kan den samlede miljøpåvirkning stadig stige – en rebound-effekt, der ofte betegnes som Jevons paradoks.”

Jevons paradoks blev formuleret af den engelske økonom William Stanley Jevons i midten af 1800-tallet, hvor briterne pludselig var meget bekymrede for, at kullet, som drev den industrielle revolution, på et tidspunkt ville slippe op. Løsningen på dette, tænkte englænderne, ville være ny teknologi, som gjorde forbruget mere effektivt, og på denne måde kunne man spare på de dyrebare sorte sten.

Det ville bare ikke være det, som ville ske, mente Jevons. “Det er en fuldstændig misforståelse at tro, at en effektiv brug af brændstof er det samme som et lavere forbrug. Det modsatte er sandheden,” konkluderede Jevons i 1865.

Nu, et par århundreder senere, hvor techindustriens energiforbrug kun går en vej – opad – ser vi dette paradoks i praksis. /Emilie Ewald