Dynamisch Programmeren (een uitdaging)

 
14 september 2008

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).


Werken met ?
Kijk dan bij onze mogelijkheden voor starters en/of ervaren IT'ers.


Categorieën: Architectuur, Development, .Net

Tags: , , , ,


Reacties (8)

  • Hoi Joris,

    Voor het bepalen van het rendement zou je dynamisch programmeren niet gebruiken, dat lijkt me niet zo moeilijk te berekenen met een directe percentageberekening ((totale grootte rechthoeken / totale grootte gebruikt materiaal) * 100%). Bedoel je misschien iets anders?

    Groet,
    Rick

    Geplaatst op 26 maart 2011 om 22:26 Permalink

  • Joris schreef:

    Ik wil graag voor een serie rechthoeken die uit standaard afmetingen worden gehaald bepalen wat het rendement is. Kan dat met het knapzak algoritme?
    Let wel ik heb geen ervaring met programmeren…

    Geplaatst op 26 maart 2011 om 14:39 Permalink

  • Hi Ruud,

    Geen probleem! Het is alleen maar leuk om te horen dat je ermee bezig bent. Help je er graag verder mee.

    Groet, Rick

    Geplaatst op 15 oktober 2008 om 10:49 Permalink

  • Ruud Albert schreef:

    Hi Rick,
    Heb dat over het hoofd gezien :-(. Maar nu werkt het en mijn dank voor het instructieve programma voorbeeld in C#.

    Geplaatst op 15 oktober 2008 om 9:52 Permalink

  • Rick schreef:

    @Ruud

    In de Unittests staat ook een aanroep van de RecursiveSolutionImproved, in het bestand testRecursiveSolutionImproved.cs – ik denk dat het daarmee zou moeten lukken. Zo niet, laat het nog even weten.

    Geplaatst op 14 oktober 2008 om 16:41 Permalink

  • Ruud Albert schreef:

    Kun je ook nog aangeven hoe de code in Program.cs is voor het aanroepen van RecursiveSolutionImproved(…)?

    Geplaatst op 14 oktober 2008 om 13:00 Permalink

  • @Pieter: ten eerste, goede vraag.

    Het is zoals je wel hebt kunnen zien een vrij generiek algoritme, waarschijnlijk is het daarom dat je je er niet direct iets concreets bij voor kunt stellen. Het wordt bijvoorbeeld al veel gebruikt in allerlei stringbewerkingen. Ook word wrap kun je op deze manier mooi oplossen, mooier bijvoorbeeld dan met een greedy methode (in het artikel beschreven als de hebzuchtige variant). Veel van dit soort string functionaliteit is al geschreven voor je, dus daar zul je ze niet van kennen.

    Verder zijn plekken waar je het tegen kunt komen in de logistiek, voor bijvoorbeeld optimaal voorraadbeheer en in de financiële wereld. In die domeinen zijn namelijk vele voorbeelden te vinden van problemen met dezelfde karakteristieken. Ik kan mij zelf een concreet voorbeeld herinneren van task scheduling dat hiermee goed op te lossen was, maar dat is al wel weer een tijdje geleden. :-)

    Als je er meer voorbeelden van wilt zien en ook een uitgebreide uitleg van het algoritme zelf, dan verwijs ik je door naar het artikel op de engelstalige Wikipedia, http://en.wikipedia.org/wiki/Dynamic_programming

    Geplaatst op 19 september 2008 om 8:54 Permalink

  • Pieter J. de Vries schreef:

    Ik vroeg me af wanneer je dit “dynamische programmeren” zou kunnen toepassen in een realtime-situatie. Zijn hier eventueel voorbeelden voor te noemen?

    Geplaatst op 18 september 2008 om 9:16 Permalink