Lad os starte med et spørgsmål: Forestil dig, at du skal regne ud, hvad den optimale rute skal være for at levere 10 pakker på 10 forskellige adresser i København. Hvordan kan du gøre det med færrest muligt kørte kilometer?

Den letteste måde at løse det problem på er ved at prøve sig frem mellem de 3.628.800 forskellige muligheder. Det kommer givetvis til at tage noget tid, men det er alligevel muligt.

Nu er problemet bare, at udbringningsfirmaer sjældent skal uddele 10 pakker i København om dagen, men måske nærmere i omegnen af 10.000. Her er det umuligt at tjekke alle muligheder selv. Tallet er simpelthen for stort. For at være mere præcis er tallet i omegnen af 35.000 cifre langt, hvilket på et A4-ark med skriftstørrelse 11 svarer til omkring 10 sider. Det er et enormt tal!

Den naturlige tanke vil for de fleste af os derfor være at få en algoritme i en god computer til at regne det ud for os. Algoritmer, eksempelvis dem bag Googles internetsøgninger, kan trods alt filtrere mellem milliarder og atter af milliarder af søgeresultater og komme med lige netop det svar, som du skal bruge, inden for under en tiendedel af ét sekund. En lignende algoritme kan vel udregne, hvordan man hurtigst muligt får leveret en ladning pakker i hovedstaden?

Så let er det dog ikke, fortæller professor Jakob Nordström fra Datalogisk Institut ved Københavns Universitet. Problemet er, at computeren skal lave så vanvittigt mange beregninger, at tid bliver en faktor. Uddybning: Én milliard milliarder fylder i tal i omegnen af en halv linje på et A4-ark. Tallet for mulige postruter gennem København er meget, meget, meget… … meget større.

»Det er tal i en helt anden størrelsesorden. Lad os antage, at en algoritme skulle udregne den hurtigst mulige rute til at bringe 1.000 pakker ud. Så vil det tage en hurtig computer mellem 10 og 100 år at regne det ud, fordi den skal igennem så mange beregninger. Taler vi om 10.000 pakker eller måske 100.000 pakker, vil det tage endnu længere tid. Selv hvis hvert eneste atom i universet var en moderne supercomputer, som havde regnet på det her problem siden universets fødsel for 13 mia. år siden, ville de stadig kun have udregnet en fraktion af en fraktion af løsningen,« fortæller Jakob Nordström.

Jakob Nordström arbejder netop på at forstå lignende problemer og udvikle algoritmer, som kan løse dem.

Nogle problemer er meget svære at løse matematisk

Problemet med at udregne den optimale rute i forhold til at levere pakker kaldes for the travelling saleman’s problem inden for matematik og den teoretiske computervidenskab.

Det er et problem, som der meget tydeligt er en helt klar løsning på – altså at finde den optimale rute – men matematikere har endnu ikke været i stand til at udvikle den algoritme, som kan gøre det, uden at tid bliver et problem.

Umiddelbart er det let nok at udvikle en algoritme, som kan finde en løsning, hvis tid ikke er en faktor, men hverken Postnord, DHL eller DAO har tid til at vente til universets undergang med at få leveret folks indkøb fra Wish.com eller julegaven fra moster Oda. De skal ud med pakkerne i dag og har brug for lige nu og her at vide, hvordan de kan gøre det hurtigst muligt.

Problemet er heller ikke isoleret til pakkeudbringning. Et lignende problem står flyselskaber med, når de skal lave planer for deres fly og besætning. Her findes der heller ingen algoritme til at udregne den optimale måde at sende sine fly på vingerne, når faktorer som arbejdstimer, tid på jorden, antal fly og destinationer tages i betragtning.

Proteinkemikere står med det samme problem, når de skal udregne den optimale rækkefølge i forhold til at designe og folde proteiner. »Der findes nogle problemer, som vi er rigtig gode til at løse med algoritmer. Det gælder blandt andet søgninger og sorteringer, som vi kender det fra internetbrowsere. Der kan vores algoritmer filtrere i enorme mængder information og give os et svar med det samme. Så er der til gengæld problemer, som vi ikke er gode til at løse, når problemets størrelse vokser. Der har vi endnu ikke fundet gode algoritmer, og det er et reelt praktisk problem for meget industri,« forklarer Jakob Nordström.

Let at kontrollere – svært at beregne

Et interessant aspekt ved udfordringen med at finde gode algoritmer til at udregne optimale ruter for udbringning eller lette- og landetider for rutefly er, at det faktisk er meget let at få en computer til at verificere en løsning.

Hvis en pakkeudbringer skal levere 1.000 pakker i København indenfor otte timer, og man præsenterer en computer for en mulig løsning, kan computeren på et øjeblik fortælle, om den foreslåede rute faktisk er i stand til at få pakkerne ud til tiden. Computeren kaster bare et blik på den tid, som det tager at rejse fra destination til destination, og svaret kommer den lynhurtigt med.

Selvfølgelig kan der være forskelle i trafik, stoplys osv., men lad os for lethedens skyld forestille os, at det altid tager den samme tid at køre de samme stræk gennem København.

»Vores udfordring inden for denne gren af matematikken er, at vi ikke forstår, om problemer med disse egenskaber – selvom de er lette at verificere en løsning på, hvis vi først får den givet – også kan løses effektivt eller ej. Vi har studeret disse problemer og deres egenskaber længe, men vi er stadig ikke i nærheden af at kunne svare på det spørgsmål,« siger Jakob Nordström.

Hører til de største uløste matematiske spørgsmål

Jakob Nordström er langt fra den første matematiker til at rive sig selv i håret over dette problem. Det har været studeret siden 1970’erne. Amerikanske matematikere fik øjnene op for det i 1971, og sovjetterne fulgte med i 1973.

Ved årtusindeskiftet fremsatte en af verdens fremmeligste matematiske institutioner, Clay Institute, syv såkaldte “Millennium Prize Problems” for det nye årtusinde. De syv Millennium Prize Problems er matematiske problemer, som alle matematikere kan stræbe efter at finde en løsning på. Det ene af disse problemer er det såkaldte P vs. NP-problem, som i lægmandstermer lyder således:

Kan alle algoritmer, hvis svar kan verificeres af en computer hurtigt, også løses af en computer hurtigt?

»Svaret på det spørgsmål kender vi ikke endnu. Det kan være, at problemet slet ikke kan løses hurtigt af en computer, men det kan også være, at vi bare ikke har udviklet de rigtige algoritmer endnu. De fleste matematikere mener, at den første mulighed er den rigtige, men vi ved det simpelthen ikke,« siger Jakob Nordström.

Forskeren uddyber, at de forskellige problemers natur desuden er så ens, at hvis en matematiker finder en algoritme, som kan løse det ene af problemerne, eksempelvis det med ruteflyene, kan samme algoritme tilpasses til at kunne løse dem alle.

»Allerede for 50 år siden til foråret udkom den første videnskabelig artikel, som viste, at disse problemer var det samme problem, og at hvis en algoritme virker på det ene problem, virker den også på de andre. Siden er der publiceret hundredvis af forskningsartikler om emnet,« fortæller Jakob Nordström.

Teori og praksis smelter sammen

Jakob Nordströms forskningsfelt hedder Computational complexity theory og handler i store træk om at finde ud af, hvordan komplekse beregninger kan løses af en computer, og hvorfor nogle problemer ikke kan.

Det lyder grangiveligt meget teoretisk, men lad dig ikke narre. Jakob Nordström praktiserer nemlig sammensmeltning af praksis og teori.

De to parallelle tilgange til at løse problemerne for flyselskaberne og pakkeudbringerne har nemlig været notorisk dårlige til at snakke samme i fortiden. Det er også meget tydeligt, når man forlader forelæsningssalen på universitet og træder ud i den virkelige verden. »Når man sidder til forelæsninger i matematik og får præsenteret de her problemer, får man at vide, at de ikke kan løses, og at det hele er skidt. Men når man så kommer ud i den virkelige verden, er SAS stadig på vingerne, og pakkerne bliver stadig bragt ud. Ude i den virkelige verden lever matematiske praktikere nemlig rigtig godt af at udvikle algoritmer og finde løsninger på problemerne for de respektive firmaer, og de er rigtig gode til at komme meget tæt på at lave optimale ruter eller tidsskemaer. Det er på en måde absurd, at teoretikerne siger, at problemet ikke kan løses, og så løser praktikerne det alligevel på daglig basis,« siger Jakob Nordström.

Professoren uddyber, at der også er mange tilfælde, hvor problemer ikke kan løses, eller hvor det kan løses bedre, så der er behov for bedre algoritmer, så eksempelvis SAS kan lave endnu mere optimale planer for deres fly og mandskab og på den måde spare flere penge i driften.

»Der er mange nuancer her, og det er vigtigt at forstå, er det ikke er sort-hvidt det hele, men at der er en masse gråt også. Teoretikerne siger, at problemerne ikke kan løses, men praktikerne finder hele tiden eksempler på reelle problemer, der alligevel kan. Der ligger dog 50 års arbejde med disse algoritmer bag for at komme til det punkt, og der er stadig et incitament for at videreudvikle algoritmerne for at gøre dem bedre, eller så de kan løse problemer, som ikke kan løses med de nuværende metoder,« siger han.

Vil finde ud af, hvorfor nogle algoritmer virker

Jakob Nordström forklarer, at tilgangen til at lave gode algoritmer er, hvad der adskiller teoretikerne fra praktikerne. Teoretikerne siger, at det ikke kan lade sig gøre, men praktikerne finder på alle mulige krumspring for alligevel at komme frem med gode løsninger. De slår løs på problemet og prøver sig frem, indtil de har fundet løsninger, som virker i op til 99 procent af tilfældene, eller løsninger, der rammer rigtigt inden for en fejlmargin af én procent Løsningerne er altså gode, de er bare ikke optimale, og det er godt nok i mange tilfælde.

»Praktikerne udnytter egenskaber ved problemer fra “den virkelige verden” til at finde på smutveje eller smarte tricks, der ofte virker i praksis. Hvis sådan et trick eller en smutvej virker i 90 procent af tilfældene i praksis, er det en rimelig god løsning. Men teoretikerne leder efter algoritmer, der garanteret virker altid og er hurtige, og så kan de ikke bruge et trick, der kun virker i 90 procent af tilfældene,« siger Jakob Nordström.

En hjørnesten i Jakob Nordströms forskningsarbejde er netop at danne bro mellem teoretikerne og praktikerne. Et element i den brobygning er at undersøge, hvorfor praktikernes algoritmer virker og finde ud af, hvad deres begrænsninger er, og hvordan de kan videreudvikles til at blive endnu bedre. Teorien skal assistere praksis med at forstå, hvorfor en algoritme kan være god, selvom den ikke er optimal, samtidig med at praksis kan hjælpe teoretikerne med at stille interessante teoretiske spørgsmål, som kan hjælpe teoretikerne med at finde nye interessante retninger at arbejde i.

»Hvis vi skal lave fremskridt, er vi nødt til at forstå, hvorfor disse algoritmer virker, og hvordan vi kan forbedre dem. Jeg vil forstå, hvordan det er muligt, at disse algoritmer fungerer bedre, end teoretikerne mener, de bør gøre, og også hvorfor de så fejler, når de gør det,« siger Jakob Nordström.

Praktikere skal hjælpe teoretikere og omvendt

Denne del af Jakob Nordströms forskning skal man vist være matematiker for at forstå til bunds, men i store træk handler det om at analysere på strukturen af algoritmerne.

En algoritme til at løse et givet problem udnytter en eller anden metode, hvor den gennemgår forskellige trin i beregningen. Bagved disse trin findes “noget”, der guider disse trin og er årsagen til, at algoritmen virker, som den gør, når den arbejder sig gennem problemet.

Jakob Nordströms forskning går ud på at tage et skridt tilbage og destillere, hvordan denne analyse fungerer. Hvad er det, som algoritmen gør? Hvordan ræsonnerer den?

Når forskeren har en præcis matematisk beskrivelse af, hvad dette ræsonnement er, kan han studere det fra et matematisk synspunkt og benytte matematiske værktøjer til at få en tilbundsgående forståelse af, hvor stærk eller svag en algoritme er, hvad den kan gøre, og hvad dens begrænsninger er. Ved at analysere på denne matematiske essens i algoritmerne kan Jakob Nordström eksempelvis afgøre, hvorfor en given algoritme kan løse den ene type problemer, men ikke den anden.

»Det handler ikke kun om, at praktikerne kan hjælpe teoretikerne med at komme tættere på en algoritme, som kan finde den optimale løsning. Det handler også om, hvordan man kan bruge matematisk teori til at hjælpe praktikerne med at designe bedre algoritmer. Ved at tage den teoretiske tilgang til at analysere på strukturen af en algoritme og identificere, hvor den er svag, eller hvor den fejler i forhold til at kunne løse givne problemer, kan jeg gå tilbage til praktikerne og fortælle dem, hvorfor deres algoritme er dårlig til at løse givne problemer. Det kan hjælpe dem til at lave endnu bedre algoritmer, ligesom det kan hjælpe mig til at finde ud af, hvad der gør en algoritme til denne type problemer stærk eller svag,« forklarer Jakob Nordström.

Jakob Nordström uddyber, at hans arbejde ikke kun ligger i at fortælle praktikerne, hvordan de skal gøre deres algoritmer bedre. Han arbejder også selv på at udvikle verdensklasse-algoritmer til at løse disse ekstremt svære problemer.  ♦