Laborationer

Laboration 3: Optimering av radbyten i en text

Målsättning

I denna laboration ska du lära dig hur dynamisk programmering kan användas för att effektivt lösa vissa optimeringsproblem. Du ska också få viss insikt i hur man kan använda optimering för att lösa uppgifter som man inte självklart betraktar som optimeringproblem.

Uppgift

Du ska skriva ett program som bestämmer var man ska göra radbyten i en text. Programmet ska läsa in texten från en fil och producera ett formatterat stycke där radernas längd är så nära ett givet värde som möjligt. Man vill alltså ha en "ganska rak högermarginal".

Vi gör några förenklingar som egentligen inte har med själva lösningstekniken att göra men som gör det enklare att programmera det hela. För det första antar vi att alla tecken är lika breda. Detta är sant för vissa typsnitt på skärmen. Denna förenkling gör att vi inte behöver bry oss om olika typsnitt. Den andra förenklingen är att vi antar att vi bara får göra radbyten mellan orden och att alla ordmellanrum består av mellanslag eller radbyten i infilen. Egentligen borde man ta hänsyn till att man kan avstava ord men detta bryr vi oss inte om nu.

Bakgrund

Det är mycket vanligt att man behöver formattera om text så att den får en bredd som passar i sammanhanget. Ofta har man en given spaltbredd eller en ruta med givna dimensioner där texten måste rymmas. Samtidigt vill man att det ska se "snyggt ut" vilket vi här kan tolka som att man vill undvika att vissa rader blir märkbart längre eller kortare än de övriga.

Låt oss utgå från följande text (plockad från Stockholms kommuns webbsidor):

Kommunfullmäktiges övergripande inriktningsmål skall genomsyra
stadens alla verksamheter och förtydligas i
verksamhetsspecifika inriktningsmål och generella åtaganden
i nämndernas verksamhetsplaner.
De övergripande målen är likvärdiga och utan prioritering.
De verksamhetsspecifika inriktningsmålen och åtagandena skall
formuleras så att de ryms inom fastlagda ekonomiska ramar och inte
kommer i konflikt med budgethållningen.

Ett sätt att välja var man skall placera radbytena är att använda en girig algoritm, vilket här helt enkelt innebär att man fyller på raderna succesivt så långt det går. Man byter alltså rad före det ord som skulle ha tagit oss över högermarginalen. Om vi gör detta med vår exempeltext med högermarginalen satt till 70 tecken så får vi detta resultat.

Kommunfullmäktiges övergripande inriktningsmål skall genomsyra stadens
alla verksamheter och förtydligas i verksamhetsspecifika
inriktningsmål och generella åtaganden i nämndernas verksamhetsplaner.
De övergripande målen är likvärdiga och utan prioritering. De
verksamhetsspecifika inriktningsmålen och åtagandena skall formuleras
så att de ryms inom fastlagda ekonomiska ramar och inte kommer i
konflikt med budgethållningen.

Denna metod används i många enklare ordbehandlare.

Vi ser här att det inte ser så vidare snyggt ut när den andra raden är markant mycket kortare än de omgivande. Att det har blivit så beror på att ordet "inriktningsmål" är så långt att det inte får plats på den andra raden. Man borde dock kunna lösa det hela lite bättre genom att flytta ned ordet "stadens" från första raden så att de två första raderna blir mer jämnlånga. Detta klarar dock inte den giriga algoritmen av eftersom den bara tittar på den aktuella raden utan att ta hänsyn till konsekvenserna längre ned.

I denna laboration ska vi använda oss av en teknik där man betraktar det hela som ett optimeringsproblem. Vi formulerar då en kostnadsfunktion som har egenskapen att ge lägre värden ju bättre texten ser ut. Det blir därigenom väldefinierat vad vi menar med att texten ska se så bra ut som möjligt. Det är naturligtvis inte självklart vilken kostnadsfunktion man ska använda och det kan behövas en del pyssel innan man hittar en som fungerar bra.

En rimligt kostnadsfunktion kan vara summan av kvadraten på skillnaden mellan radlängderna och något önskevärde, g, där vi vill att marginalen ska hamna. Om vi låter xi beteckna längden på rad i så blir kostnaden alltså

Man brukar inte betrakta det som störande att den sista raden i ett stycke är för kort. Därför specialbehandlar man den sista raden så att kostnaden för den sätts till noll om dess längd är mindre än g.

Om vi sätter g till 70 så blir det optimala utseendet på texten detta:

Kommunfullmäktiges övergripande inriktningsmål skall genomsyra stadens
alla verksamheter och förtydligas i verksamhetsspecifika inriktningsmål
och generella åtaganden i nämndernas verksamhetsplaner. De övergripande
målen är likvärdiga och utan prioritering. De verksamhetsspecifika
inriktningsmålen och åtagandena skall formuleras så att de ryms inom
fastlagda ekonomiska ramar och inte kommer i konflikt med budgethållningen.

Vi ser här att algoritmen har lyckats väldigt bra, men vi inser snart att det inte är en jämfördelse på lika villkor. Optimeringsalgoritmen försöker ju få raderna att bli ca 70 tecken långa medan den giriga algoritmen gjorde raderna till max 70 tecken långa. En mer rättvis jämförelse får vi om vi minskar g något så att raderna blir ungefär lika långa i båda fallen. Om vi exempelvis sätter g till 65 så blir den optimala lösningen istället:

Kommunfullmäktiges övergripande inriktningsmål skall genomsyra
stadens alla verksamheter och förtydligas i verksamhetsspecifika
inriktningsmål och generella åtaganden i nämndernas verksamhetsplaner.
De övergripande målen är likvärdiga och utan prioritering. De
verksamhetsspecifika inriktningsmålen och åtagandena skall formuleras
så att de ryms inom fastlagda ekonomiska ramar och inte kommer i
konflikt med budgethållningen.
Detta är ganska likt vad den giriga algoritmen producerade med skillanden att den andra raden gjorts något längre på bekostnad av den första.

Dynamisk programmering

Dynamisk programmering är en teknik för att lösa vissa typer av optimeringsproblem effektivt. Många optimeringsproblem är av typen att man skall hitta den bästa kombinationan av ett stort antal val. Om man försöker lösa sådana problem med ren råräkning (brute force) leder det normalt till att komplexiteten växer exponentiellt med problemstorleken. Detta är alltså en oanvändbar strategi i de flesta lite större sammanhang. Under vissa förhållanden kan man dock organisera problemet så att man kan utnyttja en teknik som kallas dynamisk programmering. Ordet programmering syftar här inte alls på något datorprogram utan skall väl främst betraktas som planering.

Idén bakom dynamisk programmering liknar det resonemang man gör vid rekursion. I vårt fall kan vi konstatera att kostnaden när vi väljer att placera första radbytet på ett visst ställe kan uttryckas som summan av det lokala bidraget från den första radens längd plus den totala kostnaden för att optimalt lösa problemet med resten av texten. Den optimala lösningen får vi helt enkelt genom att prova igenom alla möjliga placeringar av första radbytet och välja den som ger den minsta summan.

Om vi gör denna rekursion på ett naivt sätt så kommer vi dock att få en algoritm som har exponentiell komplexitet. Tricket vid dynamisk programmering är att man utnyttjar att det optimala sättet att lösa delproblemet är oberoende av hur man kommit till den situationen. I vårt fall betyder det alltså att det bästa sättet att bryta texten efter ett radbyte vid position p är oberoende av hur man eventuellt har brutit raderna före p. Det innebär att när man en gång har räknat ut den optimala radbrytningen från p och framåt så kan man lagra denna information, t.ex. i en vektor med p som index, så att man kan utnyttja denna dellösning flera gånger.

Tips för genomförandet

Börja med att läsa in alla orden till en vektor med ett ord per element i vektorn. Se till att alla mellanslag och radbyten plockas bort så att de inte stör beräkningarna i fortsättningen. Du kan nu använda index i denna vektor även för att beteckna ordmellanrummen. Detta innebär att alla möjliga platser för radbyten också kan identifieras med sådana index.

För att genomföra den dynamiska programmeringsalgoritmen behöver du även en vektor för att lagra kostnaden för delproblemen. Denna kostnad skall beräknas vid varje möjlig plats för ett radbyte, d.v.s. vid varje ordmellanrum. Skapa därför en till vektor för detta ändamål som är lika lång som ordvektorn (möjligen ett längre, beroende på hur du väljer att implementera looparna senare).

Det går att implementera den dynamiska programmeringen rekursivt men i praktiken gör man det oftast med hjälp av vanliga loopar. Man måste då se till att man löser problemet "från slutet" (i rekursiva termer betyder det att man startar från basfallet). Fyll alltså succesivt i kostnadsvektorn från slutet. När man väl har kommit till vektorns början har man löst problemet eftersom index noll motsvarar det bästa sättet att bryta raderna fr.o.m. första ordet.

När man ska räkna ut ett element i kostnadsvektorn, säg p, så har man redan tillgång till alla kostnader för positionerna med högre index än p. Finessen men dynamisk programmering är nu att man utnyttjar dessa värden för att förenkla beräkningen av värdet vid p. Värdet som ska lagras vid p får man fram genom att prova igenom alla möjliga platser q för nästa radbyte och behålla den bästa. Kostnad för varje sådant fall får man genom att lägga ihop kostnaden för första raden (från p till q) och det värde man redan räknat ut för q. Man måste också ta med fallet att q ligger sist, vilket innebär att raden som börjar vid p är den sista raden. Tänk då på att kostnaden för den sista raden räknas ut annorlunda (om den är kortare än g är kostnaden noll).

Detta förfarande upprepas nu tills man har kommit fram till början av vektorn. Man har då fått fram den optimala totala kostnaden för hela stycket som nu ligger i vektorns position noll.

För att man ska kunna skriva ut texten med rätt radbyten räcker det dock inte med att veta den optimala kostnaden. Man måste också veta vilka positioner för radbytena som ledde fram till detta optimala värde. Denna information har vi använt oss av när vi räknade ut kostnaderna tidigare. Vi måste nu komplettera algoritmen ovan så att informationen sparas på något lättillgängligt format. Man kan t.ex. använda ytterligare en vektor där man vid varje position sparar index till nästa optimala radbyte. Denna vektor fyller man då i samtidigt som man fyller i kostnadsvektorn enligt algoritmen ovan. När man slutligen ska skriva ut resultatet plockar man succesivt index från denna vektor. Vid position noll finns nu index till positionen där första radbytet ska vara. På denna position hittar man index till andra radbytet, o.s.v. Man använder alltså dessa index som ett slags länkar liknande vad man normalt gör med referensvariabler i länkade datastrukturer.

Lycka till!
Örjan