Dynamisch Programmeren (een uitdaging)

Zo, nu deze verwarrende titel je aandacht heeft getrokken, zal ik eerst proberen die verwarring weg te nemen. Het dynamisch programmeren wat hier bedoeld wordt, heeft niets te maken met dynamische talen en ook niets met extra veel bewegen achter je toetsenbord en/of beeldscherm. Net zoals extreme programming niets te maken heeft met op bergtoppen of onder water programmeren.

Dynamisch Programmeren is een algoritme voor het optimaal nemen van een rij van afhankelijke beslissingen. De formele omschrijving zal ik je hier niet mee vermoeien. Het is heel waarschijnlijk dat je het tijdens je opleiding bent tegengekomen als je een opleiding in programmeren of gerelateerde vakgebieden hebt gevolgd. Tijdens mijn studie Elektrotechniek ben ik het enkele malen tegenkomen. Het stuk van André getiteld “Algoritmiek” triggerde mij om het weer eens op te zoeken.

Een tot de verbeelding sprekend voorbeeldprobleem om dynamisch programmeren voor te gebruiken is het welbekende knapzak-probleem. Er zijn natuurlijk veel varianten van, ik heb gekozen voor de variant met kunstwerken en een museum. Eventueel kun je The Thomas Crown Affair bekijken voor een levendige illustratie, maar simpel gezegd komt het op het volgende neer..

Het knapzak-probleem
Situatieschets: je bevindt je in een museum met allemaal kunstwerken aan de muur en je hebt een (grote) knapzak om een aantal kunstwerken mee te nemen. Je kunt maar een maximaal gewicht meenemen in je knapzak, anders scheurt dat ding (mental note: als het allemaal lukt, koop je een nieuwe). De beveiliging is reeds uitgeschakeld. Het doel is om een zo waardevol mogelijke buit mee te nemen uit het museum. Gelukkig ben je een echte kunstliefhebber en ken je de waardes van de verschillende kunstwerken. En uiteraard heb je een weegschaal mee.

Je zou het in al je hebzucht misschien snel proberen op te lossen door de kunstwerken met de meeste waarde per kg eerst te pakken en in je knapzak te stoppen, maar deze aanpak is niet optimaal. Een goed voorbeeld hiervan is de situatie dat je maximaal 50 kg mee kunt nemen en de museum collectie bestaat uit één schilderij van 30 kg en 400 Euro en twee schilderijen van 25 kg en 250 Euro per stuk. Het schilderij van 30 kg biedt duidelijk meer euro’s voor zijn kilo’s, maar het is natuurlijk evident dat de twee kleinere schilderijen samen meer opbrengen dan de ene grote. Je snapt hem al: er is net iets meer vernuft nodig.

Dynamisch programmeren lost dit probleem op door het op te delen in kleine stukjes en de uitkomst daarvan afhankelijk te maken van weer kleinere sub-problemen. Je kunt het algoritme op verschillende manieren gebruiken, maar een recursieve aanpak is het makkelijkst te begrijpen, daar ga ik dan ook van uit. Hieronder zie je een voorbeeld van een simpele recursieve aanpak. Om het overzichtelijk te houden staat hier alleen de methode (beter gezegd functie in dit geval) waarin het algoritme zich bevindt.

 1 public static int Solve(List weights,
 2       List values, int curr, int capacity) {
 3
 4  if (lastIndex == -1 || capacity == 0) return 0;
 5    if (weights[curr] > capacity)
 6    {
 7      return Solve(weights, values,
 8                    curr- 1, capacity);
 9    } else {
10      return Math.Max(
11        Solve(weights, values,
12               curr- 1, capacity),
13        (values[curr]
14          +
15          Solve(weights, values,
16                (curr- 1),
17                (capacity - weights[curr])))
18      );
19    }
20  }
21 }

Je ziet in het bovenstaande stukje code dat de keuze tussen het wel of niet meenemen van het huidige (curr) item gemaakt wordt in het return statement dat regels 10 t/m 18 beslaat. Regels 11 en 12 gaan over de uitkomst als het kunstwerk niet meegenomen wordt. Regels 13 t/m 17 gaan over de uikomst als het kunstwerk wel meegenomen wordt: de waarde wordt erbij opgeteld en het gewicht van de capaciteit afgetrokken.

Implementaties in C#
Ik besloot om twee implementaties van het algoritme te maken: functioneel (recursief) en object georiënteerd. Uiteindelijk kwam dit erop neer dat ik een simpele recursieve implementatie heb gemaakt zoals hierboven en een verbeterde variant en vervolgens ben gaan refactoren. In de simpele recursieve implementatie wordt alleen de optimale waarde berekend, maar is achteraf niet meer bekend welke kunstwerken je dan moet meenemen. Bij de verbeterde versie wordt gewerkt met structs die de kunstwerken representeren. De oplossing is een lijst van deze kunstwerken.

In het domeinmodel komen nu de volgende klasses van objecten voor:

  • WorkOfArt – representeert een kunstwerk en heeft een waarde en gewicht
  • ArtCollection – representeert een verzameling kunstwerken en heeft tevens een waarde en gewicht
  • SelectionOfArt – representeert een optimale (sub-)oplossing
  • Knapsack – representeert de knapzak en bevat de kunstwerken na de ‘transactie’
  • Museum – representeert het museum, dat een collectie kunstwerken bevat en bestolen wordt.

Hieronder zie je de belangrijkste aanroep in het domeinmodel: het moment dat de boel gejat wordt. Of beter gezegd: dat het museum een optimale selectie samenstelt en overhandigd aan de knapzak (van de dief). Dit is uiteraard geheel in lijn met het Actief-Passief patroon zoals Rob Vens dat beschrijft.

.. in de class Museum:

void SurrenderBestSelectionTo(Knapsack knapsack)
{
  SelectionOfArt selection =
    SelectionOfArt.MakeSelection(collection.Copy());

  foreach (WorkOfArt work in
   selection.GetBestSelectionFor(knapsack.Capacity))
  {
    knapsack.Take(Surrender(work));
  }
}

In de zip-file Dynamic Programming staat de source code van de verschilllende implementaties in één solution. Het zou allemaal goed moeten compileren. Eventueel kun je wat problemen hebben met de unittests als je nUnit niet geinstalleerd hebt. Verwijder de tests dan gewoon, of beter nog, installeer een unit testing framework zoals nUnit. Overigens gebruik ik voor het testen tussendoor testdriven.net, wat het heel snel en makkelijk maakt om een aantal tests te runnen vanuit Visual Studio.

Conclusie en uitdaging
Als ik dan mijn uiteindelijke domeinmodel vergelijk met de simpelere functionele varianten, vallen mij een aantal zaken op.

  1. De code in de OO variant komt op mij veel leesbaarder over. Toegegeven, er is ook wel meer tijd in gaan zitten.
  2. De hooflijnen van het algoritme zijn in de OO variant nog steeds herkenbaar. Zie hiervoor de SelectionOfArt. Ik ben benieuwd of die uberhaupt kan verdwijnen.
  3. De klasse SelectionOfArt doorloopt twee fasen: 1 het opsplitsen van de collectie (opzetten van de boom) en 2 het berekenen van een optimale samenstelling voor een capaciteit. Het elegante is dat de eerste fase maar éénmaal doorlopen hoeft te worden en onafhankelijk is van de tweede fase.
  4. In de OO code zie ik vrij veel klasses met weinig functionaliteit. Dit heeft er denk ik mee te maken dat er geen volledige applicatie geschreven is. Zou dit wel gebeuren, dan blijkt waarschijnlijk dat sommige domein objecten in andere situatie intensiever gebruikt te worden, terwijl het nu slechts figuranten zijn.
  5. Er is ook meer code in het domein model gaan zitten. Dit is een direct gevolg van het feit dat ik er in dit geval niet op bespaard heb. Het ging mij om een duidelijke representatie van het domein met zoveel mogelijk scheiding van verantwoordelijkheden.

Ik wil dit stuk afsluiten met een uitdaging. Ik zet een flesje wijn op de beste structurele verbetering van het domein model. De beoordeling ervan laat ik aan mijzelf, maar ik beloof niet krenterig te zullen zijn. Als deadline voor de inzendingen geldt 31 oktober, 12:00 en het is de bedoeling dat de inzending compileert. Als je mijn e-mailadres niet hebt, laat dan even een berichtje achter. Tenslotte, mocht het een spannende strijd worden, dan kunnen er ook nog wel twee flesjes wijn vanaf. Wel wil ik zelf graag ook een glaasje meedrinken..

Source code in Rick Dynamic Programming (een gezipt VS2008 project).