Backtracking

En vanlig problemtyp är sådana som kräver backtracking (förkortat till BT hädanefter). Dessa problem är normalt sett NP kompletta, dvs de saknar lösning inom polynomisk tid. Personligen tycker jag inte om dessa uppgifter eftersom det kan vara svårt att veta i förväg om programmet kommer att vara tillräckligt snabbt eftersom BT är en exponentiell algoritm (O(x^n) eller O(n!) eller dyl)

För att få upp effektiviteten med BT gäller det att avbryta de rekursiva anropen så fort man inser att man hamnat i en återvändsgränd och att en lösning (eller att ingen bättre lösning än den hittills bäst funna) omöjligen kan finnas längs det nuvarande spåret. Hur man avgör om man kommit till en återvändsgränd är inget man kan lära ut - det skiljer sig förstås mycket från uppgift till uppgift.

Däremot finns det en teknik som kan användas på flertalet BT-uppgifter så att man når återvändsgränderna tidigare än om man mer eller mindre slumpmässigt backtrackar. Många BT uppgifter är av typen "placera ut ett antal objekt i ett område så att de passar ihop". Ett exempel kan vara ett vanlig träpussel (eng. jigsaw puzzle); givet bitarna i pusslet och formen på kanterna för varje bit, lös pusslet. Jag kommer att använda detta exempel i
beskrivningen nedan, men ha i åtanke att detta kan generaliseras till andra objekt.

Den enkla (och naiva) BT metoden är att välja en godtycklig bit, pröva att placera ut den på alla ställen där den passar, och anropa rekursivt för att pröva nästa bit. Så fort man inte hittar en bit som inte passar in på något ställe avbryter man.

Denna metod funkar nog bara på väldigt små pussel, och är inte att rekommendera. En mycket bättre metod är att inte välja en godtycklig bit, utan den bit som minskar sökträdet så mycket som möjligt. Antag att vi har bitarna A,B,C,D kvar. Om det finns 4 ställen att placera ut A på, 4 ställen för B, 2 ställen för C och 3 ställen för D, ska vi givetvis placera ut bit C på något av de två möjliga ställena. Efter att ha gjort den utplaceringen kommer antalet ställen för de övriga bitarna att minska, vilket gör att hela sökträdet minskar i storlek. Dessutom är denna extra loop som krävs vid varje steg i rekursion
naturlig - då ser vi ju samtidigt om det finns någon bit som inte går att placera ut någonstans alls (och kan då backtracka).

Det finns en "spegelvänd" variant också, och det är att bestämma sig för en ruta i pusslet där ingen bit ännu placerats, och testa alla bitar som passar där. Som ovan vill vi välja den ruta i pusslet där så få bitar som möjligt passar in. T ex i ett pussel så är de fyra hörnbitarna speciella (vi antar att bitarna kan roteras, annars är ju hörnbitarna givna direkt). Med den senare metoden skulle man då först välja att placera ut en bit i det övre vänstra hörnet, och därefter testa de fyra hörnbitarna. Notera att det skiljer sig från att först välja en hörnbit och sedan testa den i de fyra olika hörnen! (vilket den förra metoden skulle ha gjort)

Vilken av dessa två snarlika metoder är bäst då? De är troligen likvärdiga, så vilken man använder beror på uppgiften. I vissa fall kan speciellt den senare metoden vara svårare att tillgripa (uppgift två nedan är ett exempel). Det kan givetvis också gå att kombinera dessa metoder på olika sätt, men det är ofta onödigt - men det kan vara bra att tänka på om inget annat verkar vara tillräckligt snabbt.

Uppgifter

Problem Tävlingens hemsida Hjälp och kommentarer
Korsord SM 1999
Chess x Tetris
 ACM NWERC 1999
Graph Coloring
 ACM SWERC 1995









Tillbaka