Knapzak-achtig probleem (collapsing knapsack?)

[Verwijderd]

Hoi.

Ik ben van plan een programma te schrijven dat knapzakproblemen kan oplossen. In mijn geval is het uiteindelijke doel van het probleem: het maximaliseren van de opbrengst van een aantal handelingen tegen bepaalde kosten. Deze kosten mogen een voorafgestelde waarde niet overschrijden. De handelingen variëren in efficientie en opbrengst. Over het algemeen kunnen we stellen, hoe hoger de opbrengst, des te inefficienter de handeling is.

Tot zo ver is het niet al te ingewikkeld, en als het dit was kon ik het wel implementeren met behulp van lineair programmeren of wat dan ook.

Echter in mijn specifiek geval doen zich extra randvoorwaarden voor. De drie belangrijkste waar ik mee worstel, zijn

1. De handelingen waar ik invloed over kan uitoefenen zijn maken deel uit van een groter geheel aan handelingen. Dit houdt in dat mijn maximaal mogelijke bijdrage minder wordt naar mate de tijd vordert! Ik wil natuurlijk mijn handelingen zo kiezen dat ze mijn bijdrage maximaliseren. (Hoewel het mogelijk is dat de tijd zo kort is dat ik zelfs met de meest inefficiente handelingen het budget niet op kan maken moet ik daar niet vanuit gaan. Het spel is natuurlijk om een gulden middenweg te vinden tussen efficientie en opbrengsten.)
2. sommige opeenvolgende handelingen kunnen invloed op elkaars opbrengsten of kosten (al dan niet positief) hebben.
3. sommige handelingen (hoge opbrengst tegen relatief lage kosten) kunnen niet constant achter elkaar worden verricht.

Mijn vraag is of hier nu ook bepaalde algoritmen voor bestaan. Of ben ik nu gedwongen om mijn programma als een soort simulatie te maken zodat het alleen dit specifieke probleem kan oplossen? Het liefst had ik natuurlijk een methode die het hele type van dit soort problemen aankan.

Ik vermoed dat het knapzakprobleem samen met randvoorwaarde 1 in het engels als het ‘collapsing knapsack’ probleem te boek staat. Google vindt alleen links naar artikelen die achter slot en grendel van bepaalde sites staan die de publicaties willen verkopen. Wikipedia heeft ook geen teksten over dit probleem—alleen maar over het gewone knapsack probleem, plus een paar variaties daarop. Bovendien heb ik nergens iets kunnen vinden over handelingen die elkaar kunnen beïnvloeden. Of moet ik een samengestelde handelingen als één handeling zien? Dat zou vervelend zijn omdat er dan heel veel combinaties mogelijk zijn.

[Verwijderd]

Ik heb besloten de knapsack methode over boord te zetten en een non-deterministische aanpak te volgen. Ik laat mijn programma een willekeurige keuze maken van de beschikbare handelingen en laat het programma dan berekenen of deze keuze de beoogde efficientie en opbrengst van de handelingen haalt. Zo nee dan gaan we een stapje terug en kiezen een andere handeling daarvoor in de plaats. Zo ja, dan was dat kennelijk de juiste keuze en gaan we verder met de volgende handeling. Enzovoorts totdat de gewenste eindopbrengst is behaald.

Deze aanpak heeft als voordeel dat ik het in een boomstructuur kan onderbrengen (al dan niet virtueel) en zo kan bijhouden of er handelingen in het verleden hebben plaatsgevonden die invloed zouden kunnen hebben op de efficientie van nieuw te verrichten handelingen.

Klinkt bon, non? (Of zie ik nou iets over het hoofd?)

[EfBe]

Verwijderd schreef op zondag 18 november 2007 @ 15:11:
Ik heb besloten de knapsack methode over boord te zetten en een non-deterministische aanpak te volgen. Ik laat mijn programma een willekeurige keuze maken van de beschikbare handelingen en laat het programma dan berekenen of deze keuze de beoogde efficientie en opbrengst van de handelingen haalt. Zo nee dan gaan we een stapje terug en kiezen een andere handeling daarvoor in de plaats. Zo ja, dan was dat kennelijk de juiste keuze en gaan we verder met de volgende handeling. Enzovoorts totdat de gewenste eindopbrengst is behaald.

Lijkt me nog steeds een knapsack solution. Knapsack is NP hard, althans voor grote waarden van M waarbij M de grootte van de knapsack is. Er zijn wel wat slimme algo's voor kleine M, maar dan is brute force ook niet zo inefficient meer vergeleken bij een slim algo.

Koop Sedgewick, algorithms in C, is al oud boek maar nog steeds actueel.

[netvor]

Inderdaad, je bent dan nog steeds een knapsack problem aan het oplossen, al is het met een ander algoritme.

Je zal als eerste de keuze moeten maken: ga ik volledig of onvolledig zoeken? Met NP-C problemen als knapsack heb ik de ervaring dat een volledige zoekmethode ondoenlijk is voor N>50 op een standaard-PC. Maar als je probleem kleiner dan dat is en het gerust een uurtje mag duren dan is zo'n algoritme wel zo simpel. Het voordeel is dat je er niet veel aan hoeft te tweaken en dat je zeker weet dat je oplossing ook echt het globale optimum is. Voor knapsack heb ik zelf Branch&Bound gebruikt, met goede resultaten.

Als je onvolledig gaat zoeken, dan heb je een enorme berg aan algoritmes die je kan gebruiken. Je kan een greedy algorithm bouwen dat een voor een items in de knapsack stopt ADHV een cost/benefit-ratio; dat doe je in een kwartiertje. Of je kan een enorm sophisticated genetisch algoritme bouwen met meerdere bevolkingsgroepen en migraties en alle toeters en bellen. Het is aan jou.

Verder heb je ook nog trucjes als dynamic programming, waarmee je over het algemeen globale optima kan vinden in semi-polynomial time. Voor knapsack bestaan er een aantal.

Mijn advies: als je voor jouw probleem een dynamic programming algoritme kan vinden, neem dat dan. Als je er geen kan vinden, dan hangt het af van de grootte van je probleem.

[dingstje]

Verwijderd schreef op zaterdag 17 november 2007 @ 23:46:
Ik vermoed dat het knapzakprobleem samen met randvoorwaarde 1 in het engels als het ‘collapsing knapsack’ probleem te boek staat. Google vindt alleen links naar artikelen die achter slot en grendel van bepaalde sites staan die de publicaties willen verkopen. Wikipedia heeft ook geen teksten over dit probleem—alleen maar over het gewone knapsack probleem, plus een paar variaties daarop. Bovendien heb ik nergens iets kunnen vinden over handelingen die elkaar kunnen beïnvloeden. Of moet ik een samengestelde handelingen als één handeling zien? Dat zou vervelend zijn omdat er dan heel veel combinaties mogelijk zijn.

Stap eens een universiteitsbibliotheek binnen, daar hebben ze meestal wel toegang tot die databases. Op de Universiteit Gent hebben ze alleszins toegang tot ScienceDirect waar "An efficient algorithm for the collapsing knapsack problem" op staat...

[BCC]

scholar.google.com