Når datamaskina gjev opp

TEKST: KJERSTIN GJENGEDAL

Det å finne eller forbetre problemløysande algoritmar er jobben til Forskingsgruppa for algoritmeanalysar og kompleksitetsteori ved Institutt for informatikk ved Universitetet i Bergen (UiB). Algoritmegruppa er med på Christiekonferansen 2013 i Grieghallen, der gruppa har ein informasjonsstand.

Tenk deg at du har 20 menn og 20 kvinner oppstilte framfor deg. Oppdraget ditt er å arrangere eit massebryllaup, sånn at det etter bryllaupet ikkje finst eit einaste mann-/kvinnepar som begge skulle ønskt at dei hadde fått kvarandre, framfor den partnaren dei fekk. Greier du det, har du løyst det såkalla «stabile ekteskap»-problemet.

Finn din ektefelle med algoritme

I 1962 presenterte økonomane David Gale og Lloyd Shapley ein algoritme, eller ein stegvis framgangsmåte, som løyser «stabile ekteskap»-problemet. Algoritmen involverer to steg (først frieri frå mennene, deretter anten «nei» eller «ok, med mindre det kjem nokon betre» frå damene), som blir repeterte heilt til alle har fått ein partnar. Shapley fekk, saman med Alvin Roth, nobelprisen i økonomi i 2012 for teoretisk og empirisk arbeid med denne algoritmen.

Algoritmen garanterer at alle får ein partnar og at ekteskapet blir stabilt, men ikkje at alle får den dei helst vil ha. Ikkje desto mindre kan løysinga på problemet overførast til ei rekkje verkelege situasjonar, som når ein skal matche medisinstudentar med sjukehus eller nyredonorar med ­pasientar, for å nemne nokre kjende døme.

For vanskeleg for datamaskina

– Hos oss arbeider vi helst med dei problema vi kallar vanskelege. Det finst nokre problem som ingen i verda har funne gode algoritmar for. Problem som det ville ta ei datamaskin tusenvis av år å finne den beste løysinga på, seier professor Pinar Heggernes.

Algoritmar kan settast i hop på ulike måtar, og det er viktig å finne den raskaste måten.

– Men det er ingen vits i å ta tida med ei stoppeklokke, for då viser ein berre kor lang tid det tek å køyre algoritmen på akkurat denne datamaskina, akkurat no, seier forskar Daniel Lokshtanov.

Istaden nyttar ein storleiken på inndata som indikator. Dagens datamaskinar gjer typisk opp mot ein milliard utrekningar per sekund. Men dersom algoritmen ikkje er god nok, aukar køyretida maskina treng for å løyse eit problem mykje raskare enn mengda med inndata.

– Så dersom algoritmen ikkje er effektiv, kan køyretida brått auke frå eitt sekund til tre dagar når inndatamengda til dømes doblar seg i storleik, fortel Lokshtanov.

Lett spørsmål, vanskeleg svar

Difor finst det ei mengd problem som ser overkomelege ut på overflata, men som i realiteten er umoglege å løyse.

– Sei at du har ei mengde på tusen menneske, og mellom dei tusen vil du finne den størst moglege gruppa med menneske som alle kjenner kvarandre. Det er eit slikt vanskeleg problem. Det er lett å spørje alle dei tusen kven dei kjenner. Og det er lett å plukke ei tilfeldig gruppe og sjekke om dei kjenner kvarandre. Men den einaste algoritmen vi har for å finne den største gruppa som kjenner kvarandre, er å plukke alle moglege utval og sjekke dei, og det tek for lang tid, seier Heggernes.

Desse vanskelege problema, som blir kalla NP-komplette problem (sjå fakta) kan sjå heilt ulike ut, men dei har fellestrekk som gjer at dersom eitt vert løyst, er alle løyst. Mykje pengar og ære ventar på den som greier å vise at NP-komplette problem kan løysast raskt med ei datamaskin - eller eventuelt å vise at desse problema ikkje har noka rask løysing. Det amerikanske Clay-instituttet har lova ein million dollar til den som kjem med det matematiske provet på at problema anten kan eller ikkje kan løysast. Mange prov kjem inn til instituttet kvart år, men førebels har ingen av dei vist seg å halde etter grundig inspeksjon.

Ryddar opp med algoritmar

– Alle innan vårt felt drøymer om å finne svaret på dette, for det har så utruleg store praktiske konsekvensar. Til dømes så er tryggleikssystema i nettbankane basert på at ein legg til grunn at slike vanskelege problem er uløyselege innan rimeleg tid.Så dersom nokon greier å vise at dei har ei enkel løysing likevel, er brått heile tryggleiken borte. Samstundes ville jo ei heil rad vanskelege oppgåver brått vere enkle å få til, forklarar Heggernes. 

Fram til eit slikt prov blir lagt fram, skjer det likevel mykje forsking på korleis ein kan handtere dei vanskelege problema, slik at dei blir litt mindre vanskelege. Professor Fedor Fomin har fått ei stor løyving frå det europeiske forskingsrådet for å arbeide med nettopp dette. Det finst mange algoritmar som har til oppgåve å rydde opp i inndatasettet, luke vekk unødvendig informasjon og utelukke kombinasjonar som er så usannsynlege at dei er irrelevante. Nokre algoritmar fungerer godt, andre mindre godt.

– Målet vårt er å forstå algoritmane teoretisk, så vi kan vite korleis dei kjem til å oppføre seg og korleis dei kan bli betre, fortel Fomin.

Løysingar på transportproblem

Som dei andre forskarane i algoritmegruppa, arbeider han ikkje med praktiske problem, men med matematiske representasjonar av problemet. Ein slik representasjon kan til dømes likne eit rutekart med flydestinasjonar. Transportruteproblem hamnar fort i den vanskelege NP-kategorien. Eit flyselskap vil gjerne maksimere profitten ved å kjøpe så få fly som råd og løne så få pilotar som råd. Du vil òg sette opp flyrutene slik at flya alltid er fulle. Då skal det ikkje så mange destinasjonar til før problemet blir uløyseleg.

Slike sett med inndata, som viser objekt med sambandsliner imellom, blir kalla grafar. Ulike problem kan representerast med ulike grafar, og mykje av forskinga ved algoritmegruppa går ut på å karakterisere grafane og finne ut kva strukturen deira kan fortelje om kor lett eller vanskeleg problemet er å løyse. Viser det seg at grafen representerer eit problem som er NP-komplett, kan ein kanskje finne algoritmar som reknar ut tilnærmingsløysingar. Det er trass alt betre med ei omtrentleg løysing, som gjer at du kan drive flyselskapet ditt i dag, framfor ei optimal løysing, som ligg hundrevis av år inn i framtida.

Med hjernen som datamaskin

Ironisk nok er ikkje datamaskiner spesielt viktige i algoritmeforsking. Både Heggernes, Fomin og Lokshtanov bruker mesteparten av tida på å tenke, skrive og lese artiklar om andre sine resultat. Aller best fungerer det å tenke i lag med andre.

– Vi har ofte gjester; flinke folk som kjem hit og arbeider i lag med oss ei veke eller to. Vi diskuterer mykje, og det er det ofte lettare å gjere andlet til andlet enn på e-post, seier Heggernes.

Ein skulle kanskje tru at det er liten vits i å forske på slike metodar. Kvifor ikkje berre vente til datamaskinene sin reknekapasitet er blitt stor nok til at dei kan sjekke alle moglegheitene? Men dei NP-komplette problema er av ein slik karakter at datamaskinene aldri vil bli kraftige nok til å løyse dei. Store datamaskiner krev mykje energi til kjøling for å unngå at dei blir overoppheta, og ifølgje algoritmeforskarane meiner somme at vi snart nærmar oss dei naturlege grensene for kor små maskinkomponentane kan bli.

Samstundes aukar datamengdene raskare enn reknekrafta. Når alle opplysingar skal lagrast og registrerast i tilfelle dei kan brukast til noko, blir det endå viktigare å ha gode algoritmar. Ikkje berre for å hente ut informasjon frå datamaterialet, men også for å lagre materialet på ein slik måte at det blir lettare å finne fram i det.

– Den viktigaste grunnen til at det går raskare å løyse problem med datamaskinar i dag enn tidlegare, er at algoritmane er blitt betre, ikkje at reknekapasiteten til maskinene har auka, hevdar Daniel Lokshtanov.

Sjølv om algoritmeforskarane jobbar med matematiske modellar, ligg det alltid i bakhovudet at algoritmane deira skal ha ein praktisk funksjon. Det er lett å bli oppglødd over eit fint matematisk resultat, men dersom det ikkje kan brukast til noko, vil det fort ende opp i ein skuff og bli gløymt.

– Til sjuande og sist bør resultata våre kunne brukast i eit dataprogram. Vi kan definere problem som gjev vanskelege teoretiske resultat og som kan sjå veldig flotte ut, men det vil berre ha verdi dersom den teoretiske innsikta hjelper oss til å forstå noko meir i tillegg. Noko som har praktiske implikasjonar, seier Heggernes.

Sjå video med algoritmeprofessor Pinar Heggernes.

Denne artikkelen står også på trykk i Hubro 01/2013. Du kan tinge eit abonnement ved å sende oss ein e-post.