Dansk datalog har udviklet suveræn algoritme til at finde den korteste vej

Når vi skal et nyt sted hen, overlader de fleste af os det efterhånden til computeralgoritmer at finde den bedste rute, hvad enten det er GPS’en i bilen, Rejseplanen eller Kort-app’en på telefonen. Men nogle gange viser det sig, at den rute, man bliver foreslået, ikke helt flugter med virkeligheden. For hverken vejnet, trafiknet eller andre slags netværk er nemlig statiske. Den bedste rute kan pludselig blive den langsomste, fx fordi der har dannet sig bilkø på grund af vejarbejde eller en trafikulykke.

Hvad mange nok ikke tænker over er, at der ligger kompliceret matematik bag de ruteforslag, vi får i sådan en situation. Den software, man bruger, forsøger nemlig at løse en variant af det klassiske algoritmiske problem om ”den korteste vej”, nemlig den korteste vej i netværk, der ændrer sig. I 40 år har forskere arbejdet på at finde en algoritme, der kan løse denne matematiske gåde optimalt. Og nu er det lykkedes Christian Wulff-Nilsen fra Datalogisk Institut på Københavns Universitet at knække nødden i samarbejde med to kolleger.

”Vi har udviklet en algoritme, som vi nu har det matematiske bevis for er bedre end alle de hidtidige algoritmer og det tætteste på optimal, som det nogensinde vil være muligt at komme, om vi så ser 1000 år ud i fremtiden,” siger lektor Christian Wulff-Nilsen fra Datalogisk Institut. Resultaterne blev præsenteret på den prestigefyldte konference FOCS 2020.

Optimalt vil i denne sammenhæng sige den algoritme, som bruger så lidt tid og så lidt computerhukommelse som muligt på at beregne den bedste rute i netværket. Det gælder altså ikke kun vejnet eller trafiknet, men kan lige så vel være internettet eller andre typer netværk.

Netværk som grafer

Forskerne har baseret deres algoritme på såkaldte dynamiske grafer. En graf er i denne sammenhæng en abstrakt repræsentation af et netværk, der består af kanter (som fx kan repræsentere veje) og knudepunkter (som fx kan repræsentere vejkryds). Når en graf er dynamisk betyder det, at den kan ændre sig over tid. Den nye algoritme håndterer ændringer bestående af slettede kanter – det kan fx svare til, at et stykke af en vej pludselig er utilgængeligt på grund af vejarbejde.

”Den store fordel ved at se netværk som en abstrakt graf er, at den kan bruges til at repræsentere et hvilket som helst slags netværk. Det kan lige så vel være internettet, hvor man gerne vil sende data via så kort en rute som muligt, en menneskehjerne eller netværket af venne-relationer på Facebook. Det gør graf-algoritmer anvendelige i mange sammenhænge,” forklarer Christian Wulff-Nilsen.

Traditionelle algoritmer går ud fra, at grafen er statisk, hvilket jo sjældent gør sig gældende i den virkelige verden. Så når denne slags algoritmer skal bruges i et netværk, der forandrer sig, er de nødt til at startes op forfra hver gang, der opstår bare en lille ændring i grafen. Og det er spild af tid.

Mere data kræver bedre algoritmer

Det at finde bedre algoritmer er ikke kun noget, der kan være nyttigt, når vi rejser. Det er noget, som er nødvendigt på stort set alle de områder, hvor vi producerer data, påpeger Christian Wulff-Nilsen:

”Vi er i en tid, hvor vores datamængder vokser og vokser, mens udviklingen af vores hardware ikke kan følge med. For at kunne håndtere al den data, som vi producerer, er vi nødt til at udvikle smartere software, der kræver mindre køretid og hukommelse. Derfor har vi brug for smartere algoritmer,” siger han.

Han håber, at det bliver muligt at anvende denne algoritme eller nogle af teknikkerne bag den i praksis, men understreger at dette er det teoretiske bevis, og at det først ville kræve eksperimenter.

Emner