Etikettarkiv: Datavetenskap

Allt större flugsmällor för allt mindre flugor

Varning: Detta inlägg innehåller extremt dålig Java-kod.
Läs på egen risk.

Den som nån gång har läst Reddit-sidan ProgrammerHumor har kanske lagt märke till tendenserna att hitta på alldeles absurda lösningar till mycket simpla problem eller koncept.
Till exempel, för cirka 9 månader sedan var volume sliders ett återkommande skämt och därav skapades många vackra implementationer, bl.a:

 

Mer nyligen var temat om hur man ”effektivast” kollar om ett givet heltal är jämnt eller udda. Funktioner som åstadkommer detta är lättare att implementera än volume sliders, så motiverad av mina nyfunna kunskaper i Tira (Tietorakenteet ja algoritmit) bestämde jag mig naturligtvis för att testa några i Java. Metoderna nedan är inspirerade av både ProgrammerHumor och egna idéer. Några av dem kan kräva kunskap om Java eller talteori för att förstå, så en TL;DR i meme- format finns längst ner för dem som inte bryr sig om tekniska detaljer.

Metod 1: Divisionsrest

Kolla talets divisionsrest med 2. Om resten är 0, så är talet jämnt, annars udda.

  • Tråkig normie lösning
  • Använder inte ens rekursion
public boolean isEven1(int n) {
    return n % 2 == 0;
}
Metod 2: Sista siffran

Vi undersöker talets sista siffra. Om den är 1, 3, 5, 7 eller 9 är talet udda, annars jämnt. Javas indexOf()- metod för listor returnerar -1 ifall det sökta objektet inte hittas i listan. Då gör vi ju så klart en lista av de udda siffrorna och kollar om metoden ger -1 för talets sista siffra.

  • Behöver inte utföra nån äcklig aritmetik
  • Konstant tidskomplexitet, fortfarande helt för effektiv
public boolean isEven2(int n) {
    List<Character> lastDigits
        = Arrays.asList('1', '3', '5', '7', '9');
    String number = Integer.toString(n);
    char last = number.charAt(number.length() - 1);
    
    return lastDigits.indexOf(last) == -1;
}
Metod 3: Induktion

Vi använder oss av matematisk induktion. Allmänt gäller att 0 är ett jämnt tal, efter varje jämnt tal följer ett udda, och efter varje udda följer ett jämnt. Vi bygger alltså iterativt upp en array av booleans tills vi nått det n:te elementet, som vi returnerar. Dock för att undvika en OutOfMemoryError måste vi tyvärr fuska lite och emellanåt skriva över gamla värden.

  • O(n) tidskomplexitet. Från Tira vet vi ju att O(n) är bra.
  • Induktionen kräver antagandet att 0 är ett jämnt tal.  Detta kan verifieras med en av de andra metoderna.
public boolean isEven3(int n) {
    n = n < 0 ? -n : n;        //gör n positivt
    int idx = 0;
    boolean isCurrentEven = true;
 
    boolean[] evenOdd = new boolean[10000];
    while (idx <= n) {
        if (idx == 10000) {
            idx -= 10000;
            n -= 10000;
        }
 
        evenOdd[idx] = isCurrentEven;
        isCurrentEven = !isCurrentEven;
        idx++;
    }
    return evenOdd[idx - 1];
}
Metod 4: Overflow

Alla vet ju att rekursion är bra, så här har vi en härlig blandning av rekursion och error handling.

Vi antar som baskunskap att Javas Integer.MAX_VALUE,
dvs. 2^31 – 1, är ett udda tal. Detta kan igen verifieras med någon annan metod.
Om  n = 2^31 – 1 är n udda. Annars kallar vi rekursivt på funktionen med parametern n + 2. Så klart, om n är ett jämnt tal borde den eventuellt hoppa över 2^31 – 1 och orsaka en OverflowException. Men eftersom Java hanterar den här situationen utan att klaga, måste vi använda Math.addExact()- metoden som explicit ger en Exception ifall vi går över 2^31 – 1.

Rekursionen upprepas i värsta fall ca 2^30 gånger, så en StackOverflowError orsakas långt före det. Vid detta skede avbryter vi rekursionen och startar om med en hjälpvariabel som säger hur långt vi kommit förut.

  • O(2^31 – n) tidskomplexitet. Större tal får snabbare svar.
  • isEven4(1200000000) svarade true på endast 23 sekunder.
int offset;
 
public boolean increment(int n) {
    if (n == Integer.MAX_VALUE) {
        return false;
    }
    try {
        n = Math.addExact(n, 2);
        offset += 2;
        return increment(n);
    } catch (ArithmeticException e) {
        return true;
    }
}
 
public boolean isEven4(int n) {
    offset = 0;
    while (true) {
        try {
            return increment(n + offset);
        } catch (StackOverflowError e) {
            //inget fel här, moving on...
        }
    }
}
Metod 5: Goldbach

En välkänd hypotes inom talteorin är den s.k. Goldbach Conjecture, som säger att varje jämnt tal större än 2 kan uttryckas som summan av två primtal. Resultatet har inte bevisats för godtyckligt stora jämna tal, men det har verifierats med dator för tillräckligt stora tal för våra ändamål.
Det enda jämna primtalet är 2, dvs det största jämna talet som kan uttryckas som summan av två jämna primtal är 4. Alltså om vårt tal är större än eller lika med 6 söker vi udda primtal vars summa är vårt givna tal. Annars undersöker vi talet med Metod 4.

Hur kan vi då visa att ett givet tal är ett primtal? Vi använder så klart Wilson’s Theorem. Enligt denna sats är n ett primtal om och endast om talets (n-1)! divisionsrest med n är n-1, dvs.
(n-1)!\ \equiv\ -1 \pmod n
Till detta ändamål har vi hjälpfunktionerna modFactorial och isPrime.

  • Antagligen O(n^3) tidskomplexitet. Funktionen modFactorial är O(n) och isEven5 har en dubbel loop.
  • Körtiden varierar kraftigt mellan udda och jämna tal av ungefär samma storlek:
    isEven5(4000) gav true på 2 sekunder och isEven5(4001) gav false på cirka 15 sekunder.
    isEven5(10000) gav true efter 30 sekunder. Hur länge tog det för isEven5(10001)?
  • Använd alltså den här metoden om du redan anar att ditt tal är jämnt!
public int modFactorial(int p, int mod) {
    if (p < 1) {
        return -1;
    }
    long n = 1;
    for (int i = 1; i <= p; i++) {
        n = n*i % mod;
    }
    return (int) n;
}
 
public boolean isPrime(int n) {
    if (n < 2) {
        return false;
    } else {
        return modFactorial(n - 1, n) == n - 1;
    }
}
 
public boolean isEven5(int n) {
    n = n < 0 ? -n : n; //gör n positivt
    if (n < 6) {
        return isEven4(n);
    }
 
    for (int i = 3; i < n; i++) {
        if (!isPrime(i)) {
            continue;
        }
        for (int j = 3; j <= i; j++) {
            if (!isPrime(j)) {
                continue;
            }
            if (i + j == n) {
                return true;
            }
        }
    }
    return false;
}

Här tog kreativiteten och/eller tålamodet slut, för om vi vill kan vi göra godtyckligt ”effektiva” algoritmer, men de är inte nödvändigtvis så intressanta. Men nu har vi ju jobbat under premissen att vår metod ska ge ett svar för just det talet vi stoppar in, och att svaret ska vara rätt. Vad om vi ändrar på spelreglerna lite? En bonusmetod, isEven6, hittas under länken längst ner.

Det här inlägget kunde tolkas både som en uppmuntran och en varning. Avsiktligt dålig kod kan vara väldigt underhållande och lära en tänka på problem på nya sätt (om det här är en bra eller dålig sak är upp till läsarens tolkning). Å andra sidan är dessa metoder det oundvikliga resultatet av att spendera helt för mycket tid på Tira.

TL;DR

https://i.imgur.com/TUYX6Tq.jpg

 

Algoritmisk Sudokulösning

Sudoku, eller “Number Place” som det ursprungligen hette är i dagens läge ett mycket välkänt logiskt pussel:

rank3Example rank3ExampleSolved

Givet ett 9 \times 9 rutfält delvis ifyllt av siffrorna 1-9 skall du fylla i resten av rutorna med siffrorna 1-9 så att varje siffra uppkommer endast en gång på varje rad/kolumn/liten ruta, vilka i exemplet omringas i bilden av de lite tjockare linjerna.

Sudoku pussel kan hittas överallt; många tidningar (t.ex. Hbl) publicerar sudokun dagligen, dessutom kryllar bokaffärerna av ”traditionella” och internet av elektroniska sudokun i varierande kvalitet. För de allra ivrigaste lösarna ordnas det årligen VM, med tusentals euron som pris. För den intresserade läsaren finns det i källorna ett par länkar om sudokuns historia, jag måste medge att jag hade trott att sudoku skulle härstamma från Japan, men den moderna varianten av sudoku skapades (högst troligen) av en 74-årig arkitekt från USA.

Det skulle kunna finnas ett antal olika aspekter att diskutera då det kommer till sudokun. Jag kommer att (igen) ta en datavetar-syn på det hela och undersöka till vilken grad datorer kan användas för sudokulösning. Det vill säga: hur svårt är lösning av sudokun för en dator och har människan någon chans klara sig mot dem? Mer specifikt så kommer jag att presentera tre olika algoritmer för sudokulösning samt jämföra dem med varandra.

Sudokulösning med datorhjälp

Näst går vi alltså igenom tre alternativa algoritmer för att lösa sudokun. För läsbarhetens skull kommer jag inte att gå in på detalj då det kommer till implementeringen av de mer komplicerade algoritmerna. Detaljerad förståelse för algoritmerna krävs inte i resten av texten och för de intresserade läsarna finns det en bilaga med (lite) mer detalj.

Algoritm 1:  SimpleSolver

Den första algoritmen vi undersöker är också den enklaste. Ifall jag skulle be 100 människor beskriva det simplaste sättet de kommer på för att lösa sudokun, skulle de flesta högst troligen beskriva SimpleSolver. Det handlar nämligen om att pröva alla de (ändligt många) sätten att fylla i de tomma rutorna. Algoritmen fungerar genom att gå igenom alla tomma rutor en åt gången och pröva alla möjliga siffror att sätta i dem. Efter att ha fyllt rutan granskar algoritmen att alla sudokuregler fortfarande uppfylls. Om allt är ok går algoritmen vidare till nästa tomma ruta, annars prövar algoritmen nästa siffra. Om algoritmen tvingas pröva alla siffror utan att kunna hitta en lösning går den tillbaka till föregående tomma ruta och prövar nästa siffra.

Med denna taktik kommer algoritmen i något skede att ha prövat alla möjligheter och därmed också hittat lösningen. SimpleSolver är väldigt simpel, implementation av den brukar vara en av räkneövningarna under grundprogrammeringskurserna i Gumtäkt.

Algoritm 2: DLXSudoku

Till skillnad från första algoritmen är de två andra algoritmerna för sudokulösning ursprungligen inte skapade för sudokun. Istället baserar de sig på idén att omvandla sudoku problemet till något annat (välkänt) problem och sedan lösa det andra problemet istället. Orsaken till att vilja göra såhär är att det ofta är lättare att omvandla problem än att lösa dem. Så om vi kan hitta andra problem som någon annan (lite fiffigare) människa har utvecklat effektiva lösningsalgoritmer för, kan vi dra nytta av dessa algoritmer genom att omvandla vårt problem. Detta är ofta tidseffektivare än att tillbringa en massa tid på att utveckla specialiserade algoritmer för just sudokun. Inom datavetenskap kallar man ofta denna process för en reduktion av ett problem till ett annat. Vår andra algoritm är baserad på en reduktion av sudokun till exact cover problemet och lösning av exact cover med hjälp av Algoritm X implementerad med dancing links: DLXSudoku.

Exact cover är ett ganska abstrakt problem: Givet en matris bestående av endast ettor och nollor är uppgiften att välja ut en delmängd av raderna i matrisen så att det bland de rader vi väljer ut finns exakt en etta i varje kolumn (Obs! Detta är inte den mest allmänna formuleringen av exact cover, men tillräcklig för vårt behov). Ett sudoku problem kan relativt enkelt omvandlas till en exact cover matris :

  • Varje tom ruta i sudokubrädet motsvaras av 9 rader i matrisen. Vi kallar dessa rader för Rr\#Cc\#1, \ldots, Rr\#Cc\#9 där den tomma rutan i fråga finns på rad r kolumn c.
  • Kolumnerna i matrisen representerar de olika sudoku reglerna:
    1. Varje ruta i sudokubrädet skall få exakt 1 siffra
    2. Varje kolumn på sudokubrädet skall bli ifylld av exakt en av varje siffra
    3. Varje rad i sudokubrädet skall skall bli ifylld av exakt en av varje siffra.
    4. Varje liten ruta skall bli ifylld av exakt en av varje siffra.

Alla av dessa regler representeras av kolumnerna så att kolumnen innehåller en etta på alla rader som uppfyller regeln (se exempel nedan).

Efter denna konstruktion kan vi lösa exakt cover problemet och omvandla lösningen till en lösning av sudokut helt enkelt genom att fylla i sudokut enligt de rader Rr#Cc#x som vi valt ut till exact cover lösningen. Notera specifikt att kolumnerna i exact cover matrisen som representerar kravet ”varje ruta på sudokubrädet får exakt ett värde” försäkrar oss om att exact cover lösningen innehåller för varje rad r och kolumn c på sudoku brädet, exakt en rad Rr#Cc#i från exact cover matrisen. För den intresserade läsaren finns det som bilaga till denna text en beskrivning på hur DLX fungerar. Här nöjer vi oss med att nämna att algoritmen har populariserats av Donald Knuth, som även har utvecklat det (inom naturvetenskaper) mycket använda LateX typsättningssystemet.

rank2Exampel

Exempel: Vi reducerar 4 \times 4  sudokut ovanför till exact cover. För detta sudoku får vi en exact cover matris med 8 (antalet tomma rutor) \times 4 rader. Bilden nedan visar en del av den:

ExactCover I bilden representerar första kolumnen kravet: ”Rutan på rad 2 kolumn 1 måste få exakt 1 värde”. Vi ser att kolumnen innehåller en etta på varje rad vars val fyller i rutan och 0 annars. Andra kolumnen representerar kravet ”Någon ruta på rad två måste innehålla en etta”, tredje kolumnen representerar: ”Första kolumnen måste innehålla en fyra” och fjärde ”lilla rutan uppe till höger måste innehålla en etta”, vi märker specifikt att fjärde kolumnen innehåller en etta endast på första raden. Detta betyder att vi måste välja första raden till exact cover lösningen vilket i sin tur betyder att rutan i kolumn 1 rad 2 kommer att innehålla en etta.

Algoritm 3: SATSudoku

Den sista av våra algoritmer reducerar sudoku till det kanske mest kända ”svåra” problemet inom datavetenskap, nämligen satisfiability (SAT). För att kunna beskriva SAT måste vi påminna oss om logik kursen i gymnasiet och specifikt de delarna som handlade om propositionslogik.

Propositionslogik är ett väldigt enkelt logiskt ”språk” där man formar formler genom att binda ihop sanningsvariabler (dvs. variabler som antingen kan vara sanna eller falska) med hjälp av \land (OCH), \lor  (ELLER) och \neg (INTE). (Obs. det finns ett antal olika sätt att definiera propositionslogik, vi använder det simplaste möjliga som räcker för vårt behov). Givet en propositionslogisk formel går SAT problemet ut på att hitta ett sätt att ge sanningsvärden (sant eller falskt) åt variablerna som gör att hela formeln blir sann. Sanningsvärdet för en formel definieras utgående från sanningsvärden för de delformler den innehåller:

  • Om formeln endast består av en enda variabel är dess sanningsvärde lika med sanningsvärdet för variabeln.
  • Sanningsvärdet för \lnot A är motsatsen till sanningsvärdet för formeln A
  • Formeln A \land B är sann ifall både formlerna A och B är sanna
  • Formeln A \lor B är sann ifall antingen A eller B (eller båda) är sanna.

Då vi i denna text pratar om att lösa SAT menar vi att hitta ett sätt att ge värden åt variablerna i en given formel så att formeln blir sann. Vi kallar detta sättet för en ”lösning” av SAT. (Notera att detta inte är en allmän definition av SAT problemet, men tillräcklig för oss.)

SAT är ett mycket välkänt problem inom datavetenskap. I dagens läge existerar det effektiva algoritmer för att lösa formler som består av hundratusentals variabler och miljontals delformler. För att kunna använda dessa algoritmer för att lösa sudokun måste vi från ett givet sudokubräde kunna forma en propositionsformel som tillåter oss omvandla en lösning på SAT problemet till en lösning på sudoku problemet.

För varje ruta, säg på rad r kolumn c, introducerar vi 9 sanningsvariabler: v^{rc}_1, \ldots, v^{rc}_9. Meningen med dessa variabler är: ”v^{rc}_k är sann om och endast om rutan på rad r kolumn c får värdet k i sudokulösningen”. Vår formel kommer att bestå av 5 olika delformler, fyra olika beskrivningar på de olika sudokureglerna och en som beskriver de siffror som är färdigt ifyllda:

1) Varje ruta skall få exakt ett värde. För en fixerad ruta på rad r kolumn c beskrivs detta krav av en logisk representation av: \sum_{j=1}^9 v^{rc}_j = 1. Det finns olika sätt att representera detta som propositionslogik. Ett av de simplaste är att använda formeln: v^{rc}_1 \lor v^{rc}_2 \lor ldots \lor v^{rc}_9 för att se till att rutan får minst ett värde och 27 formler av formen: \lnot (v^{rc}_i \land v^{rc}_j) \quad \forall i < j för att se till att den får högst ett värde. I vår implementation använder vi oss av ett lite annorlunda sätt att representera samma sak (kallas för sequential counter). För den intresserade läsaren finns det referenser.

2) Varje rad skall få en av varje värde. För en fixerad rad R beskrivs detta av (del)formeln:

\bigwedge_{k=1}^9 \left(\sum_{c=1}^9 v^{Rc}_k = 1\right)

som omvandlas till propositionslogik precis som i punkt 1.

3) Varje kolumn skall få en av varje värde. För en fixerad column C beskrivs detta av formeln:

\bigwedge_{k=1}^9 \left( \sum_{r=1}^9 v^{rC}_k = 1 \right)

4) Varje liten ruta skall få en av varje värde. För t.ex. lilla rutan längst upp till vänster beskrivs detta av formeln:

\bigwedge_{k=1}^9 (v^{11}_k + v^{12}_k + v^{13}_k + v^{21}_k + v^{22}_k+v^{23}_k+v^{31}_k+v^{32}_k+v^{33}_k = 1)

5) Varje redan färdigt ifylld ruta motsvaras av en formel som tvingar motsvarande variabel att sättas till sant. Så ifall rutan på rad r kolumn c har färdigt ifyllt värdet k lägger vi med delformeln v^{rc}_k till hela formeln.

Vår sista algoritm för sudokulösning bygger upp ett SAT problem såhär och ger den åt en SAT algoritm. Så länge ursprungliga sudokut har en lösning kommer SAT algoritmen att hitta en lösning på SAT problemet. Sedan omvandlas  SAT lösningen till en sudoku lösning: rutan på rad r kolum c i sudokubrädet fylls i med det värde k för vilket variabeln v^{rc}_k är sann i SAT lösningen. Delformeln vi satt med i punkt 1 här ovan försäkrar oss om att det finns exakt en sådan för varje tom ruta.

rank2Exampel

Exempel: Vi fortsätter med samma exempel som tidigare. Fullständiga propositionsformeln som beskriver detta exempel är för lång för att skrivas ner för hand. Men här följer en del illustrerande exempel   

  1. Rutan på rad 2 kolumn 1 skall få exakt ett värde: (v^{21}_1 \lor v^{21}_2 \lor v^{21}_3 \lor v^{21}_4) \land \lnot (v^{21}_1 \land v^{21}_2) \land \lnot (v^{21}_1 \land v^{21}_3) \land \lnot (v^{21}_1 \land v^{21}_4) \land \lnot (v^{21}_2 \land v^{21}_3) \land \lnot (v^{21}_2 \land v^{21}_4) \land \lnot (v^{21}_3 \land v^{21}_4).
  2.  Kolumn 1 måste innehålla en etta: (v^{11}_1 \lor v^{21}_1 \lor v^{31}_1 \lor v^{41}_1) \land \lnot (v^{11}_1 \land v^{21}_1) \land \lnot (v^{11}_1 \land v^{31}_1) \land \lnot (v^{11}_1 \land v^{41}_1) \land \lnot (v^{21}_1 \land v^{31}_1) \land \lnot (v^{21}_1 \land v^{41}_1) \land \lnot (v^{31}_1 \land v^{41}_1).
  3. Rad 1 måste innehålla en två: (v^{11}_2 \lor v^{12}_2 \lor v^{13}_2 \lor v^{14}_2) \land \lnot (v^{11}_2 \land v^{12}_2) \land \lnot (v^{11}_2 \land v^{13}_2) \land \lnot (v^{11}_2 \land v^{14}_2) \land \lnot (v^{12}_2 \land v^{13}_2) \land \lnot (v^{12}_2 \land v^{14}_2) \land \lnot (v^{13}_2 \land v^{14}_2).
  4. Vissa rutor är färdigt ifyllda: v^{11}_3 \land v^{12}_4 \land v^{13}_1 \land v^{22}_2 \land v^{33}_2 \land v^{42}_1 \land v^{43}_4 \land v^{44}_3.

Bilagan till denna artikel går in på (lite mer) detalj om hur en SAT algoritm oftast fungerar.

Vilken är bäst?

Nu är det dags för den mest intressanta frågan; vilken är bäst? För att kunna testa detta fick jag hjälp av Toffe som implementera SimpleSolvern och Lasse som implementera DLXSudoku. Själv implementerade jag SATSudoku. Tack till både Toffe och Lasse!

Innan vi går till resultaten vill jag påpeka att skillnaderna vi kommer att se i dessa algoritmer inte beror på implementationerna, resultaten kan inte och skall inte användas för att jämföra våra kodningskunskaper.

Jag valde på måfå ut 3 sudokun av storlek 9 \times 9 och tog tid på hur länge var och en av våra algoritmer tog på sig för att lösa dem. Resultaten finns nedan:

SudokuEasy

Det var ju lite tråkigt inte sant? Till och med den simplaste algoritmen löser alla 3 på under 1.5s, de mer avancerade lösarna tar under en tiondels sekund på sig. Detta illustrerar orsaken till varför jag bara hade tre sudokun; faktum är att de allra flesta normala sudokun är så gott som triviala för en dator. Det går att designa problem som vår SimpleSudoku inte skulle kunna lösa, men redan genom att ha SimpleSudoku  pröva siffror i slumpmässig ordning istället för storleksordning så klarar även den av så gott som alla 9 \times 9 sudokun snabbare än vad det skulle ta för människan att skriva ner en färdig lösning. Så det ser inte så hemskt lovande ut för oss människor.

Det verkar alltså klart att om man behöver få många sudokun löst snabbt är det mer tidseffektivt att koda en lösare än att lösa dem själv. Dock kan man efter dessa resultat  fråga sig varför man över huvudtaget borde sätta ner tid på att implementera något som helst mer avancerat än SimpleSudoku?

Ifall man bara är intresserad av 9 \times 9 sudokun är svaret: man borde inte. Men, om vi tillåter större sudokun blir saker och ting intressantare. Forskningsresultat inom sudokulösning (ja, det finns sådana) pratar ofta om ordningen (rank) av ett sudoku. En normal sudoku är av ordning 3 och allmänt så skall en sudoku av ordning n lösas på ett n^2 \times n^2 bräde. Så en 4 \times 4 sudoku är av ordning 2 och en 16 \times 16 sudoku är av ordning 4. Alla av våra algoritmer kan användas för att lösa sudokun av vilken ordning som helst. Dessutom borde större sudokun vara bättre för att jämföra algoritmer, intuitivt känns det ju ganska klart att ett större sudoku borde vara svårare än ett mindre.

SudokuHard

Resultaten finns ovan och nu börjar vi på riktigt märka skillnader i algoritmerna. SimpleSolvern klarade inte av en enda av dessa problem på under en timme (gränsen på lösningstiden). Däremot klarar sig både SATSudoku och DLXSudoku ganska väl, speciellt på ”enkla” sudokun. Av dessa två klarar sig SATSudoku lite bättre än DLX: den klarar av en ordning större ”lätt” problem och en ordning större ”svårt” problem.

Vad lär vi oss av detta? Jo, om du bara vill lösa ett enda normal stort sudoku är det fiffigare att ta papper och penna än börja koda. Skall du lösa 1000 normala sudokun kan du be datorn göra det på det enklaste möjliga sättet. Skall du lösa ett enkelt 15^2 = 225 \times 225 sudoku, så går det också att fixas, dock med lite mer möda. Men om du vill lösa ett svårt 49 \times 49 sudoku? Då är det dags att ta fram pennan igen, skriva ett stort ”LÖS SJÄLV” på hela brädet, och ta en öl istället.

Slutligen vill jag lämna er med det största sudokut som våra algoritmer klarade av och det minsta som de inte klarade. Om någon av er får någondera löst kan ni lämna en kommentar så sätter jag med er i resultaten.

Jeremias

BILAGA:

Algorithm X, Conflict Driven Clause Learning and Dancing Links for Sudokusolving.

Källor:

Problemlösning – sagan om att overkilla

Mycket av det som görs i Gumtäkt och speciellt i Exactum handlar om någon form av problemlösning. Redan under grundkursen i Analys presenteras man varje vecka med åtminstone sex problem man förväntas kunna lösa. Problemen förföljer studerandena genom hela kandidat-,  magisterexamen och för vissa även in i forskningsvärlden. Ofta kritiseras dessa problem; jag är nästan säker på att så gott som alla som studerat matematik eller data har i något skede av studierna tyckt att problemen som skall lösas är helt för artificiella, eller abstrakta för att vara intressanta: vem bryr sig om varför man inte får dela med 0? För att hålla kvar de få matematikstuderanden vi har tänkte jag i denna text dela med mig ett exempel av applicering av abstrakta problemlösningstekniker för att åstadkomma saker som på riktigt spelar någon roll. Som huvudpersoner i historien fungerar tre namnlösa spektrumiter som vi kallar för Lasse, Peter och Jeremias, alla med en matematisk/datavetenskaplig utbildning.

very-hard-riddles

Varje problemlösning börjar med ett problem. I vårt fall började vi från följande scenario:

Tänk dig att du och två av dina vänner vid en given tidpunkt har fått en lapp med gåtor vars lösningar är sex olika barer i Helsingfors. Er uppgift är, att snabbare än 200 andra grupper på 3 människor, ta er till alla av dessa sex barer, inmundiga 1.5l öl på varje ställe, sedan ta er till Otnäs och inmundiga 1.5l öl till. Som färdmedel får endast allmäntransport användas.” För enkelhetens skull kommer jag från och med nu kalla detta scenario för ”Problem Y”.

Problemlösning i sig är ett forskningsområde inom kognitiv psykologin. Inte oväntat så verkar det inte finnas ett absolut svar på frågan ”hur skall man göra för att lösa problem?”. Det finns dock vissa standardtekniker för problemlösning som dyker upp i olika undersökningar. Den man ofta börjar med inom matematik och datavetenskap kallas abstraktion. Abstraktion går ut på att exakt definiera vad man försöker åstadkomma, samt identifiera vilka delar av den information man har som behövs för att utveckla en lösning. Dessutom brukar man under abstraktion ofta identifiera begränsningar som sätts på de metoder man kan använda i sin lösning. Ett sätt att beskriva problemet efter abstraktion är genom att använda orden ”INPUT” för att beskriva den (viktiga) informationen man har, ”OBJECTIVE” för att beskriva det man försöker åstadkomma och ”CONSTRAINTS” för att beskriva de begränsningar ens lösning måste följa. Då det kommer till problem Y lyckades vi inte komma på ett sätt att använda (lagliga) datavetenskapliga/matematiska metoder för att hjälpa oss med inmundigandet av 7 \times 1.5 liter vätska eller påverka de 200 andra lagen. Därför bestämde vi oss för att ignorera dessa delar av Y och fokusera på lösningen av gåtorna samt bestämmandet av rutten att ta. Som begränsningar för problemet identifierade vi faktumet att rutten måste endast bestå av allmäntransport. Efter abstraktion såg Y alltså ut såhär:

INPUT: startställe, gåtor till 6 barer

OBJECTIVE: Kortast möjligast tid för att lösa gåtorna, ta sig runt till barerna och sedan ta sig till Otnäs.

CONSTRAINTS: Endast allmänna färdmedel tillåtna.

abstracttionIntressant nog betyder abstraktion inom konst oftast inte ”göra saker klarare”.

Efter abstraktion är det sedan dags att börja söka en lösning. En inom psykologin identifierad och inom Exactum utlärd teknik för problemlösning kallas divide and conquer. Idén är att spjälka upp ett komplext problem i mindre delar i hopp om att delarna skall vara lättare att lösa. Ofta strävar man till att delproblemen är oberoende av varandra, då kan nämligen alla delproblem lösas samtidigt.  I bästa fall kan optimala lösningarna av delproblemen sen kombineras för att åstadkomma en optimal lösning på ursprungliga problemet. Det finns ett ganska naturligt sätt att dela in Y: lösningen av gåtorna samt bestämmande av rutten. Visserligen är dessa två problem inte riktigt oberoende, man kan inte bestämma rutten innan man har löst alla barer. Vi bestämde oss ändå för att dela in Y såhär i hopp om att gåtlösaren skulle bli tillräckligt effektiv för oss att ha någon nytta av rutlösaren.  Olyckligt nog visade det sig att gåtlösning högst troligen är för svårt för oss att automatisera. Det finns en dator vid namnet Watson som har  lyckats slå  de bästa människorna på Jeopardy, men att åstadkomma detta tog 7 år för IBM:s topp ingenjörer. För att vara effektiv måste Watson dessutom köras parallellt på 70 datorer samtidigt. Eftersom vi inte kände för att börja bära omkring på 70 datorer samt inte hade 7 år att sätta på projektet, var det bästa vi kunde hoppas på ett hjälpmedel för gåtlösning, inte en automatisering. Det vill säga, vi skulle inte kunna kombinera lösningarna av delproblemen för att få en optimal lösare av Y. Liknande fenomen sker ofta inom datavetenskap/matematik. Ifall ursprungliga problemet man löser är ”tillräkligt svårt” kan man inte kombinera dellösningarna för att åstadkomma en optimal lösning. Men ofta visar det sig att den (lite sämre) lösningen man åstadkommer ändå är ”tillräkligt bra”, vilket också kommer att vara fallet med Y. Resten av denna text kommer att koncentrera sig på rutt-lösnings problemet: ”givet 6 barer samt en startposition hitta snabbaste sättet att ta sig till alla 6 barer och Otnäs med hjälp av allmäntransport”. Detaljerna av gåtlösaren kommer eventuellt att publiceras i ett senare skede (läs: ifall jag inte får en bättre idé för en höstartikel).

Då man söker efter en lösning till ett ovanligare problem är det alltid inte klart att det man försöker göra är svårt. Detta kan vara bra att ta reda på;  det är rätt så onödigt att utveckla hemskt komplicerade lösningar till problem som egentligen (bevisligen) är simpla. ”Hur svårt kan det vara?” var alltså nästa fråga vi ställde oss. En systematisk analys av olika problems svårighet är ett delområde inom komplexitetsteori och är ett forskningsområde för sig. Tekniska detaljer åsido så går analyserna av problemsvårigheter ofta ut på att man förliknar sitt problem med andra kända problem som man vet är svåra/lätta. Ofta är dessa kända problem relativt abstrakta, mest p.g.a. att det skall vara enklare att se likheterna mellan dem och det egna problemet. Då det kommer till vårt problem: ”givet en start position, 6 barer samt ett mål, hitta snabbaste rutten till alla” finns det ett relativt känt problem som man enkelt kan jämföra med, nämligen traveling salesman problem (TSP). I ursprungliga formuleringen av TSP ingår en försäljare som skall besöka alla städer i Tyskland och/eller Schweiz (ursprunget är oklart) i hopp om att sälja sina varor i var och en. Uppgiften är att försöka hitta den kortaste möjliga rutten att göra detta. I en mer abstrakt formulering av TSP  har man en matematisk graf bestående av något antal noder och kanter där varje kant har en given längd. Målet är att hitta den kortaste möjliga rutten genom grafen som besöker varje nod åtminstone en gång. Ruttlösningen för problem Y kan ses som travelling salesman där noderna i grafen är de 8:a olika platserna som skall besökas och längden på en kant mellan två noder är tiden som det tar att ta sig mellan dem med allmäntransport. Denna jämförelse mellan problemen är tillräcklig för vårt behov, men inte helt fullständig, vilket vi kommer att märka lite senare.

TSP, non abstract TSP, abstrakt

 

Efter att man ”känt igen” sitt problem kan man sen dra slutsatser på huruvida man kan förvänta sig att det går att komma fram till en lösning som fungerar inom en rimlig tid. I vårt fall skulle ju en rutt-lösare inte hjälpa hemskt mycket ifall det skulle ta 5 timmar att använda den. Olyckligt nog är traveling salesman ett NP-svårt problem. Igen tekniska detaljer åsido, betyder detta att det i allmänna fallet knappast finns ett effektivt sätt att lösa TSP. Tur i oturen kommer dessa teoretiska begränsningar emot endast då man ökar mängden noder i grafen. Med andra ord så går det troligtvis inte att koda en effektiv ruttlösare för att komma till 100 barer. Men detta var ju inte vad vi var ute efter; våra levrar skulle ändå  inte stå ut med så mycket öl. Att lösa rutten till 6 barer borde däremot inte vara en utmaning, ens åt Lasses miniläppäre. Vi kunde alltså fortsätta på projektet trots vissa teoretiska begränsningar.

Efter all förberedning visade sig själva kodandet av ruttlösaren var relativt lätt. Efter lite undersökning märkte vi nämligen att HSL bjuder på ett gratis gränssnitt till sin reittiopas, vilket i princip betyder att programmerandet av en normal reittiopas skulle (nästan) kunna vara en uppgift under ohjelmoinnin jatkokurssi. Inspirerade av detta samt de tidigare teoretiska funderingarna döpte vi vår ruttlösare till Drunken Salesman Opas (DSOPAS). Under kodandet av DSOPAS stötte vi egentligen endast på ett till problem som förhindrade oss från att lösa rutten optimalt. Problemet har att göra med jämförelsen av vårt problem och TSP. Då det kommer till allmän transportation kan det ju nämligen hända att tiden det tar att komma från bar X till Y är olika beroende på vilken tid på dagen man reser. Mera matematiskt formulerat så är längden av varje kant i grafen inte konstant. Detta betyder att för en optimal lösning av vårt problem borde reittiopas ”frågas” skilt för vikten av alla kanter i varje rutt möjlighet som undersöks. I en rutt ingår 7 kanter, allt som allt finns det 6! = 720 olika ruttmöjligheter. Totalt skulle algoritmen vid varje körning vara tvungen att fråga reittiopas efter längden av 5040 kanter. Detta skulle annars inte vara ett problem, men HSL tillåter endast 5000 frågor i timmen. Så fast det skulle vara helt möjligt att koda DSOPAS såhär, skulle det ta minst en timme att köra den. För att komma över detta problem bestämde vi oss för att än en gång approximera optimala lösningen genom att helt enkelt skita i att tiderna eventuellt ändrar. Den slutgiltiga DSOPAS börjar alltså med att fråga reittiopas efter tiden det tar att röra sig mellan alla 8 platser (6 barer, start och mål) vid en fixerad tidpunkt (\frac{6 \times 5}{2} kanter mellan barerna, 6 från startpunkten till de olika barerna och 6 från de olika barerna till målet, allt som allt 27). Efter det löser DSOPAS den kortaste rutten i denna ”approximeringsgraf” med hjälp av en sofistikerad algoritm känd som ”prova alla möjligheter”. Under lösningen behöver DSOPAS inte fråga reittiopas alls. Slutligen väljer DSOPAS ut de 5 snabbaste rutterna, vilka sen körs på nytt genom reittiopas för att få egentliga tiderna det tar att använda var och en. Dessa fem rutter visas sen åt användaren. Att fråga reittiopas om tiderna för en fixerad rutt kräver ju alltså 7 frågor. Allt som allt 27 + 5 \times 7 = 62 frågor,  betydligt bättre än ursprungliga 5040.

dsopas2 dsopas3

Näst borde vi kanske anlita en grafisk designer…

Efter att man löst sitt problem så återstår ett sista steg: verifikation av lösningen. Fastän vi kunde testa DSOPAS på påhittade rutter, var vi tvungna att vänta på årets Ylonz (som de flesta av er säkert har fattat är det Ylonz detta handlar om) innan vi kunde veta hur bra det skulle fungera på riktigt. (För att vara helt ärlig blev väntandet inte hemskt långt, sista buggarna i DSOPAS fixades onsdagen innan Ylonz lördagen). Jag kommer inte att prata så hemskt mycket om hur det gick, många av er vet det redan och för resten kan ju nämnas att vårt lag hette ”<script>alert (‘TechSupported’);</script>” samt att resultaten finns här. Jag påstår inte att DSOPAS var ända orsaken till att resultaten ser ut som de gör, men jag kan med största säkerhet säga att den tillsammans med vårt gåtverktyg nog hjälpte betydligt.

Det fanns en bar i årets Ylonz rutt som fungerar väl som exempel för nyttan vi hade av båda verktygen:  Park hotell. Då vi, baserat på bilden av ett monopolhotell, slog in ”hotell” i gåtlösaren var ”Park hotell” det enda alternativet vi fick ut. Dumma som vi var trodde vi inte på vårt eget program, men fortsatte istället fundera.  Fem minuter senare hade vi löst resten av tipset och kom fram till att gåtlösaren hade rätt från början. Senare, då vi kom fram till baren, visade sig att den långa kön skulle förhindra oss från att hinna på den bussen som DSOPAS hade bestämt åt oss tidigare. Då, detta under tidigare år skulle ha lett till en massa spekulationer på vad vi borde göra näst, kunde vi nu helt enkelt mata in de återstående barerna i DSOPAS på nytt. Den nya rutten vi fick av vårt program visade sig sist och slutligen vara lika snabb som den första vi hade fått.

Den här texten har egentligen två syften. Den ena är ett exempel på hur ”viktiga problem”  kan modeleras och lösas genom abstrakta vetenskapliga metoder. Den andra kan sammanfattas i form av en utmaning. Åtminstone 1/3 av laget TechSupported kommer inom snarast framtid att försvinna utomlands och det verkar som vi inte kommer att ha möjlighet att tävla i Ylonz med samma laguppsättning igen. Men det är inget i användningen av DSOPAS samt gåtlösaren som specifikt kräver att man kan programmera. Dvs. om det är något annat Spektrum lag som känner sig intresserade av att pröva hur långt man kommer i Ylonz med lite teknikhjälp är det bara att ta kontakt. Som sagt påstår vi inte att programmen automatiskt leder till framgång, men får man tipsen löst snabbt och är färdig att springa, har man alla möjligheter att klara sig mycket väl. Spektrum har en fin vana att klara sig väl i Ylonz, en vana som började länge före oss. Vad tycker ni, nog skall vi väl hålla segern inom Spektrum några år till?

Jeremias

KÄLLOR:

http://en.wikipedia.org/wiki/Problem_solving

http://en.wikipedia.org/wiki/Watson_%28computer%29

http://mathworld.wolfram.com/TravelingSalesmanProblem.html

http://mathworld.wolfram.com/NP-HardProblem.html

http://staff.science.uva.nl/~ulle/teaching/comsoc/2012/slides/comsoc-complexity-tutorial.pdf