Disse studentene løser Google-utfordringer

I ikke alt for fjern fremtid vil kanskje den personlige bilen være byttet ut med en flåte selvkjørende drosjer. Slik kan samfunnet klare seg med langt færre biler, og potensielt hente store samfunnsøkonomiske gevinster. Men da gjelder det at det kommer en slik selvkjørende bil presis når man trenger den, uten store forsinkelser; i årets Hash Code var over 80 studenter og profesjonelle samlet for å pønske ut algoritmer som matcher biler med kunder mest mulig optimalt.

Det ble en spennende kveld for deltagerne, da de etter beste evne og intuisjon skulle matche selvkjørende biler med ulike kunders posisjon og behov. Et kort øyeblikk hadde faktisk et lag med studenter fra UiB den beste løsningen av alle lagene i hele verden! Dessverre varte det ikke ut konkurransen, men vi skal likevel være svært fornøyd med at de to beste lagene i Norge begge var fra Bergen.

• Vi arrangerer flere programmeringskonkurranser, noen av dem er åpne for alle. Se oversikten her!

Gode resultater for Bergen

Universitetet i Bergen og Google Development Group Bergen (GDG Bergen) gjentok dermed suksessen fra i fjor, og ble på nytt den overlegent beste huben i landet, både blant lagene på toppen og i antall påmeldte lag. Med hele 85 deltakere var årets Hash Code faktisk en av de største konkurransene UiB har arrangert noensinne; studentene var i klart flertall, men også et par profesjonelle våget å utfordre dem. Og i motsetning til i fjor var det de profesjonelle som trakk det lengste strået i år: Gratulerer til laget kveik and juniper fra Havforskningsinstituttet som stakk av med seieren!

Det var riktignok langt fra opplagt at det var slik det skulle gå, og studentene lå langt foran da scoreboardet ble fryst den siste timen før konkurranseslutt. Da hadde studentene i git push --force regjert den nasjonale topplisten i lang tid allerede, og bak dem fulgte det flere andre studentlag tett i tett. Men det betyr strengt tatt lite når det bare behøvdes et lite øyeblikks genialitet hos kveik and juniper for å skape et kjempehopp i poengsum. Vel blåst!

Utfordrende oppgave

Hva er så denne utfordringen med å matche biler til kunder? Kan man ikke bare sende den nærmeste ledige bilen til en gitt kunde? Det er jo en mulig strategi, men kanskje er det en bedre løsning å sende en annen selvkjørende bil, som riktignok er lengre unna, men som er i et område hvor det ikke er noen andre relevante turer for øyeblikket. Da kan den første bilen ta en annen tur i en annen retning i stedet.

Den neste naturlige strategien man vurderer, er kanskje at en gitt selvkjørende bil blir tilegnet den nærmeste tilgjengelige kunden. Men på samme måte kan det være at det egentlig er bedre å la en annen selvkjørende bil ta den nærmeste turen, og selv ta en som er litt lengre unna. Så det er heller ikke optimalt.

Det viser seg at problemet med å velge hvilke kunder som får hvilke selvkjørende biler, er et såkalt NP-komplett problem, noe som betyr at alle måter å løse problemet optimalt på sannsynligvis krever eksponesiell kjøretid - noe vi ikke har tid til å vente på med mindre vi hadde startet programmet lenge før universets begynnelse. Det som derimot er raskt og enkelt, er å finne ut hvor lenge hver av kundene må vente gitt at vi allerede vet hvilken bil som skal kjøre hvilke kunder. Dermed kan en dommer enkelt regne ut kvaliteten på en gitt løsning - og det er altså slik Google deler ut poengene i konkurransen.

Å takle de vanskeligste spørsmålene

Problemet med å matche biler med turer er et eksempel på et NP-komplett problem. Dette er problemer som man sannsynligvis ikke kan løse på en effektiv måte med mindre noen beviser at P=NP. Det er desverre slik at NP-komplette problemer likevel dukker i svært mange praktiske sammenhenger, og det at man ikke kan håpe på en effektiv algoritme for å løse problemet optimalt, betyr jo ikke at man bare må gi opp.

• Les mer om NP-komplette spørsmål på Wikipedia

Ved Institutt for Informatikk ved Universitetet i Bergen har vi flere forskningsgrupper som på ulike måter forsøker å hanskes med NP-komplette problemer; i bioinformatikk arbeides det med flere slike problemer som er knyttet til biologi og medisin, og hvor en 'god nok' løsning kan bidra til å løse kreftgåten eller lære oss om andre sykdommer. I optimeringsgruppen arbeides det med generelle angrepsmetoder mot NP-komplette problemer, og innefor algoritmer jobber vi mye med hvordan man også teoretisk kan analysere slike problemer. Innenfor sikkerhet forsøker man å det motsatte, å konstruere krypeteringer hvor det er NP-komplett å knekke koden, og aller helst så vanskelig at teknikkene de andre gruppene utvikler ikke er gode nok.

En viktig lærdom å ta med seg, er at NP-komplette problemer sannsynligvis vil dukke opp om man lager noe nytt, og man er nødt til å håndtere dem. Å ta til takke med en banal løsning (eller ingen løsning) fordi problemet er NP-komplett, er ikke godt nok - dersom man jobber litt med problemet, vil man sannsynligvis kunne få til mye.