AU

Løsningens kunst


Selvom en bestemt gruppe matematiske problemer i teorien måske er umulige at løse, finder praktikere alligevel tilfredsstillende måder at løse disse problemer på. Matematikeren Jakob Nordström vil i sin forskning gerne binde teori og praksis bedre sammen.


Af Kristian Sjøgren


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.

The travelling salesman problem

Illustration: Thore Husfeldt, CC by-SA 3.0

The travelling salesman problem stiller det meget simple spørgsmål: Hvad er den korteste rute mellem en række byer, når man kender til afstanden mellem alle byerne, man kun må besøge byerne én gang, og man skal vende tilbage til den oprindelige by til sidst. Det er ikke svært at forestille sig, at mange fragtfirmaer, postomdelere osv. er interesserede i at finde det svar, fordi de på den måde kan spare på både tid og penge til benzin ved at benytte den korteste rute, når de skal bringe ud.

Skal man bringe ud til fire byer, kan man hurtigt regne sig frem til, hvad den hurtigste rute skal være. Sværere ser det dog ud, når vi snakker om tusindvis eller millioner af byer. Så står selv moderne supercomputere af i beregningerne. Alligevel findes der algoritmer, som sjusser sig frem til et svar, der ligger inden for én procent af det optimale.

Problemet har eksisteret siden 1832, hvor det blev beskrevet i en håndbog for handelsrejsende. Heri blev problemet eksemplificeret ved rejser gennem Tyskland og Schweiz. Problemet blev dog først formuleret matematisk i 1930 af Merrill M. Flood, der ledte efter løsninger til at organisere skolebussers ruter.

I 1990’erne udviklede fire matematikere et computerprogram, som nøjagtigt kunne udregne den optimale rute gennem et stigende antal byer. I 2006 slog computeren rekorden ved at beregne den optimale rute gennem 85.900 byer.

The travelling salesman problem er samme type problem som andre P vs. NP-problemer, der er et af de store matematiske problemer for det nye årtusinde. Kan en algoritme løse the travelling salesman-problem, kan den også effektivt løse andre P vs. NP-problemer.


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.

Millenniumproblemerne

Millenniumproblemerne er syv matematiske problemer, der i 2000 blev listet af Clay Mathematical Institute som problemer, som matematikere skulle forsøge at løse i det nye årtusinde. Enhver løsning til et af disse problemer udløser en præmie på en million dollar til den matematiker, som står bag løsningen.

Indtil videre er kun ét af problemerne blevet løst.

  • P vs. NP. Problemet kan formuleres som spørgsmålet, om der for alle problemer, hvor en algoritme kan verificere en løsning hurtigt, også findes en algoritme, der kan finde denne løsning hurtigt. Problemet er et af de vigtigste og åbne spørgsmål indenfor matematik og datalogi. Mange matematikere og dataloger forventer dog, at der ikke er en løsning på problemet, og at svaret på P vs. NP derfor er nej – de mangler bare at bevise det.
  • Navier-Stokes’ ligning beskriver bevægelsen af væsker under forskellige betingelser, eksempelvis i forhold til tyngdekraft, viskositet og tryk, men ligningen er ikke særligt velforstået, selvom den har mere end 200 år på bagen. Ingen af de nuværende matematiske værktøjer kan løse ligningen i alle tænkelige situationer, hvor blandt andet kaos ved opblanding af væsker spiller ind. Derfor ligger der en million dollar til den matematiker, som kan finde en måde at løse Navier-Stokes’ ligningen på i alle tilfælde.
  • Yang-Mills teori beskriver indenfor kvantemekanikken kvanteadfærden af elektromagnetisme og repræsenterer et af de store forståelsesspring inden for det subatomare. Alligevel har matematikere endnu ikke fået greb om matematikken bag teorien, selvom flere forsøg har vist, at teorien holder stik.
  • Riemann-hypotesen. Man kan ikke sige matematik uden også at sige primtal, fordi de har fascineret matematikere siden tidernes morgen. Matematikere har længe interesseret sig for at finde ud af, hvordan primtallene er distribueret i talrækken, og om der kan findes en formel for denne distribution. Riemann-hypotesen omhandler en bedre matematisk forståelse af, hvordan distributionen af primtallene er i talrækken. Der er en millenniumpris til den matematiker, som kan bevise hypotesen.
  • Birch og Swinnerton-Dyers formodning behandler særlige typer ligninger, som definerer elliptiske kurver over rationale tal. Formodningen er, at der findes en simpel måde at afgøre, om ligningen har et endeligt eller uendeligt antal løsninger. Løsningen skal være simpel, men det er langt fra simpelt at finde frem til den.
  • Hodges formodning antyder, at visse typer geometriske strukturer har et særligt nyttigt algebraisk modstykke, der kan bruges til bedre at studere og klassificere disse former. Find beviset for, at der findes disse særligt nyttige modstykker, og der ruller én mio. dollar ind på kontoen.
  • Poincaréformodningen er det eneste af millenniumproblemerne, der er blevet løst. Det blev det i 2003 af den russiske matematiker Grigori Perelman (som dog afslog at modtage præmien på en million dollar). Formodningen gik på, at det også gælder for højere dimensioner, at en sfære med en todimensionel overflade er karakteriseret ved at være kompakt og have en enkelt sammenhængende mængde.
Uddrag af Riemanns manuskript fra 1859, hvor han fremsætter sin hypotese.

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.  ♦