[Alg] Procedure om alle mogelijkheden te enumereren

[Oscar Mopperkont]

Ik heb een integer lineair programmeringsprobleem (ILP), omdat probleem op te lossen gebruik ik een heuristiek. Om nu te testen of die heuristiek goed werkt wil ik het gaan toepassen op een klein probleem waarvoor ik gewoon alle mogelijke oplossingen kan nagaan. Mijn probleem is nu hoe ik nu alle mogelijkheden kan afgaan.

Het probleem is als volgt:

-Ik heb X verschillende knikkers
-Ik heb Y zakken
-In elke zak kunnen Z knikkers (voor elke zak kan het anders zijn)
-Het aantal knikkers dat ik heb is gelijk aan het aantal dat in alle zakken past

Ik kan nu op ongelofelijk veel manieren de knikkers verdelen over de zakken. Ik wil al die mogelijkheden nagaan. Voor een klein probleem is dat misschien nog te doen.

Voorbeeldje:
-Ik heb 14 knikkers
-Ik heb 3 zakken
-In zak 1 passen 4 knikkers
-In zak 2 passen 4 knikkers
-In zak 3 passen 6 knikkers

Nu is het aantal mogelijkheden volgens mij een heleboel (misschien kan iemand ff neerzetten hoeveel+berekening, heb nooit WisA gehad, en dat kun je dan wel merken!)

Maar hoe ga ik alle mogelijkheden af? Hoe programmeer ik dat (gewoon in pseudo-taal).


_{Ik heb de knikkers in een array staan.
De knikker-zakken staan in een array van array's. Dimensie1=aantal zakken, dimensie2=aantal knikkers dat in zak Z past.}

[ Voor 10% gewijzigd door Oscar Mopperkont op 10-07-2003 14:15 ]

[ACM]

Zijn de knikkers onderling verschillend en/of maakt de volgorde van de knikkers uit?
Als ze niet verschillen is er nl maar 1 manier (althans, alle andere zijn exact hetzelfde)

Als de volgorde wel uitmaakt en ze verschillen boeit het niet in welke zak ze komen, je neemt gewoon alle mogelijke volgordes en houdt in gedachten dat de eerste 4 in zak 1 komen, het aantal mogelijkheden is dan 14!

Als het alleen uitmaakt in welke zak ze komen dan wordt het weer wat lastiger, hoewel je er gewoon 4 willekeurig uit de verzameling van 14 moet trekken voor de eerste zak. Die bereking is me nu even ontschoten Maar heel moeilijk is ie niet.

[GambitRS]

lamaar, knikkers verschillen dus gaat niet op dan.

[ Voor 94% gewijzigd door GambitRS op 10-07-2003 14:13 ]

[Oscar Mopperkont]

ACM schreef op 10 July 2003 @ 14:08:
Zijn de knikkers onderling verschillend en/of maakt de volgorde van de knikkers uit?
Als ze niet verschillen is er nl maar 1 manier (althans, alle andere zijn exact hetzelfde)

De knikkers zijn allemaal verschillend, anders zou het idd niet uitmaken.

Als de volgorde wel uitmaakt en ze verschillen boeit het niet in welke zak ze komen, je neemt gewoon alle mogelijke volgordes en houdt in gedachten dat de eerste 4 in zak 1 komen, het aantal mogelijkheden is dan 14!

De knikkers verschillen dus, en de volgorde hoe ze in de zak komen maakt niet uit. Dus het aantal mogelijkheden is dan alweer een stuk kleiner dan 14!.
Als ik alle 14! volgordes probeer ben ik er ook, maar dan tel ik dus veel dubbel, het maakt immers niet uit in welke volgorde de eerste 4 knikkers staan.
Bestaat er trouwens een makkelijke manier om alle 14! volgordes te creeeren? Mocht er geen silmmere optie dan die komen.

Als het alleen uitmaakt in welke zak ze komen dan wordt het weer wat lastiger, hoewel je er gewoon 4 willekeurig uit de verzameling van 14 moet trekken voor de eerste zak. Die bereking is me nu even ontschoten Maar heel moeilijk is ie niet.

Dat is hem idd.

[ACM]

Waarschijnlijk krijg je dan zoiets:
Aantal combinaties van 4 waarbij de volgorde niet uit maakt, uit 14
Dan het zelfde voor 10
en de rest komt in de laatste zak (of als je automatiseert gewoon 6 uit 6 halen, dat levert toch 1 op).

Die combinaties kan je met de nCr knop op je rekenmachine uitrekeken

Of zelf: x boven y: x! / (y! * (x-y)! )

In jouw geval zijn er dan:
1001 * 210 * 1 combinaties

Althans, als mijn berekening klopt

[ Voor 13% gewijzigd door ACM op 10-07-2003 14:22 ]

[Oscar Mopperkont]

ACM schreef op 10 July 2003 @ 14:21:
Waarschijnlijk krijg je dan zoiets:
Aantal combinaties van 4 waarbij de volgorde niet uit maakt, uit 14
Dan het zelfde voor 10
en de rest komt in de laatste zak (of als je automatiseert gewoon 6 uit 6 halen, dat levert toch 1 op).

Die combinaties kan je met de nCr knop op je rekenmachine uitrekeken

Of zelf: x boven y: x! / (y! * (x-y)! )

In jouw geval zijn er dan:
1001 * 210 * 1 combinaties

Althans, als mijn berekening klopt

Aannemende dat dat klopt dan is dat al een stuk gunstiger dan 14! (=87178291200) mogelijkheden af te gaan! Daarom wil ik alleen die 1001x210x1=210210 combi's afgaan.

Scheelt factor 87178291200/210210=414720

[ Voor 6% gewijzigd door Oscar Mopperkont op 10-07-2003 14:35 ]

[Oscar Mopperkont]

Misschien is hier iets mee te doen, alle 5 boven 3 mogelijkheden kan ik op de volgende manier "snel" opschrijven:

Delphi:

10011
10101
10110
11001
11010
11100
01011
01101
01110
00111

Hierbij begin ik dus altijd met een toewijzing op positie 1, en de overige 1-en aan het einde toegewezen. Vervolgens probeer ik achterste 1 naar voren te schuiven, lukt dat niet dan schuif ik eennalaatste 1 naar voren, en valt achterste 1 weer helemaal terug naar achteren. Dit doe je totdat je niet meer kunt.
Vervolgens schuif je je de eerste positie 1 naar achter op. En begin je weer opnieuw.


_{Ik vind het knap als je het kan volgen ....}

[ Voor 4% gewijzigd door Oscar Mopperkont op 10-07-2003 15:04 ]

[Oscar Mopperkont]

Zijn hier echt geen "standaard" procedures/functies voor? Want ik kan mij voorstellen dat dit een heel bekend probleem is bij het oplossen van ILP's, gewoon brute-force.

[hammerhead]

Oscar Mopperkont schreef op 11 July 2003 @ 08:44:
Zijn hier echt geen "standaard" procedures/functies voor? Want ik kan mij voorstellen dat dit een heel bekend probleem is bij het oplossen van ILP's, gewoon brute-force.

Brute force is voor de meeste ILP problemen echt niet meer mogelijk hoor....

Ik ben op dit moment ook bezig met een ILP probleem en volledige enumeratie is echt niet meer mogelijk. En dat werd het al heel snel niet meer. Op het moment dat de problemen groter worden ga je kijken naar dingen als het LP Relaxeren, dus de geheeltalligheids eis weghalen om een ondergrens op je probleem te bepalen in geval van een minimalisatieprobleem. Als je geluk hebt is de oplossing die je uit dit LP probleem krijgt al geheeltallig en dan ben je zeer snel klaar en heb je al gelijk de bewezen optimale oplossing voor je ILP.

[Oscar Mopperkont]

hammerhead schreef op 11 July 2003 @ 09:17:
[...]

Brute force is voor de meeste ILP problemen echt niet meer mogelijk hoor....

Ik ben op dit moment ook bezig met een ILP probleem en volledige enumeratie is echt niet meer mogelijk. En dat werd het al heel snel niet meer. Op het moment dat de problemen groter worden ga je kijken naar dingen als het LP Relaxeren, dus de geheeltalligheids eis weghalen om een ondergrens op je probleem te bepalen in geval van een minimalisatieprobleem. Als je geluk hebt is de oplossing die je uit dit LP probleem krijgt al geheeltallig en dan ben je zeer snel klaar en heb je al gelijk de bewezen optimale oplossing voor je ILP.

Brute force is voor ongelofelijk veel problemen net mogelijk nee. Zo ook niet voor het mijne. Maar om te testen of mijn manier van oplossen "goed" is kun je een klein probleem nemen dat wel met brute force op te lossen is, vergelijken met jouw gevonden oplossing.

Maar dan moet ik wel alle manieren af kunnen gaan.

[hammerhead]

Oscar Mopperkont schreef op 11 July 2003 @ 09:40:
[...]


Brute force is voor ongelofelijk veel problemen net mogelijk nee. Zo ook niet voor het mijne. Maar om te testen of mijn manier van oplossen "goed" is kun je een klein probleem nemen dat wel met brute force op te lossen is, vergelijken met jouw gevonden oplossing.

Maar dan moet ik wel alle manieren af kunnen gaan.

Inderdaad... Zo heb ik het ook met mijn probleem gedaan. Alhoewel ik het voordeel had dat er een persoon voor mij aan hetzelfde probleem bezig is geweest. Ik maak echter gebruik van een andere methode om het ILP probleem op te lossen, echter ik kon dus wel gelijk mijn methoden testen door te kijken of ze dezelfde oplossingen gaven als de resultaten van het eerste onderzoek.

Maar ik heb in het allereerste begin inderdaad ook een klein programma geschreven wat alle mogelijkheden voor mijn programma enumereerde. Was op zich niet zo heel moeilijk hoor, gelukkig waren er bij die kleine versie maar 1024 mogelijkheden waarvan er maar 157 waren toegestaan.

Bij mijn probleem was het gewoon een kweste van iets van 10 for lusjes in elkaar en in de allerbinnenste for-lus gewoon een aantal checks doen om te kijken of de gevonden mogelijkheid inderdaad wel toegstaan was. Het was niet de meest efficiente manier, dat weet ik, maar om een totaal van 1024 mogelijkheden afgaan lukt nog wel heel erg snel

Als ik het even heel snel bekijk moet het bij jou probleem mogelijk zijn om alle mogelijkheden te enumereren door gewoon alle mogelijke permutaties (14!) te enumereren. Dit levert elke keer een regel op met een aantal getallen achter elkaar. Van elke regel pak je dan de eerste 6 getallen en die stop je in zak 1, de volgende 4 stop je zak 2 en de laatste 4 getallen stop je in zak 3.
Dit is een manier om alle mogelijkheden te enumereren. Twee problemen van deze methode:
* Hij is waarschijnlijk wat traag 14! is iets van 87 miljard... Best wel veel mogelijkheden dus
* Er zitten heel veel dubbele mogelijkheden in aangezien de volgorde binnen een zak dus niet uitmaakte.

Echter kun je kijken of je een nieuw gevonden oplossing toe moet voegen aan de totale enumeratie, wanneer deze in een bepaalde permutatie al bestond voeg je hem niet toe, anders wel. Dan nog moet je waarschijnlijk wel even wachten voor het programma afgelopen is, maar daarna kun je alle mogelijke oplossingen gewoon oplevren in een verzameling.

[Oscar Mopperkont]

hammerhead schreef op 11 July 2003 @ 09:58:
...

Als ik het even heel snel bekijk moet het bij jou probleem mogelijk zijn om alle mogelijkheden te enumereren door gewoon alle mogelijke permutaties (14!) te enumereren. Dit levert elke keer een regel op met een aantal getallen achter elkaar. Van elke regel pak je dan de eerste 6 getallen en die stop je in zak 1, de volgende 4 stop je zak 2 en de laatste 4 getallen stop je in zak 3.
Dit is een manier om alle mogelijkheden te enumereren. Twee problemen van deze methode:
* Hij is waarschijnlijk wat traag 14! is iets van 87 miljard... Best wel veel mogelijkheden dus
* Er zitten heel veel dubbele mogelijkheden in aangezien de volgorde binnen een zak dus niet uitmaakte.

Echter kun je kijken of je een nieuw gevonden oplossing toe moet voegen aan de totale enumeratie, wanneer deze in een bepaalde permutatie al bestond voeg je hem niet toe, anders wel. Dan nog moet je waarschijnlijk wel even wachten voor het programma afgelopen is, maar daarna kun je alle mogelijke oplossingen gewoon oplevren in een verzameling.

Dat laatste is inderdaad misschien wel een idee, dus ik ga alle 14! af, sla die op in een array, als ze toegestaan zijn, en nog al voorkomen... Hmm, ik ga dat eens proberen uit te werken. Is dat wel te doen 87miljard dingen?

Ik sta trouwens nog steeds open voor efficientere manieren! Want 14 knikkers in 3 zakken, is nog een relatief heel klein probleem, vergeleken met mijn echte probleem, van 1428 knikkers in 7 zakken.

[hammerhead]

Ik vermoed niet dat het je zal gaan lukken om 1428 knikker in 7 zakken te enumereren.....

Verder weet ik ook niet welke programmeertaal je gebruikt... 87 Miljard elementen in een Array opslaan zal zeker weten niet gaan lukken Maar je kunt in Java gaan kijken naar dingen als Vectors of Hashmaps... Je moet namelijk wel kunnen controleren of een bepaalde set knikkers niet al bekend is, maar dan onder een andere volgorde. Dus uiteindelijk hoef je niet alle 87 miljard elementen op te slaan, maar slechts een gedeelte.

Efficientere manieren zijn dingen waar ik ook mee bezig ben op dit moment. Ik weet niet hoe je precies je model hebt opgesteld, maar ik heb voor het oplossen van mijn probleem de integer eis laten vallen en los het hieruit ontstane LP probleem op met behulp van kolomgeneratie (dit aangezien er nog steeds wel heel veel mogelijkheden zijn....) Op het moment dat ik het LP probleem optimaal heb opgelost kijk ik of de oplossing die ik eruit krijg toevallig integer is. Zo ja, dan ben ik klaar en heb ik dus het ILP probleem bewezen optimaal opgelost en als de oplossing niet integer is (dus in jouw geval dat een knikker bijvoorbeeld voor 30% in zak 1 zit en 70% in zak 2) moet ik vanuit de LP oplossing een ILP oplossing gaan genereren. Hier is een algemene techniek voor die het optimaal doet (Branch-and-Bound) en verder kun je indien je zelf meer informatie over je domein weet een eigen heuristiek gaan implementeren om van de gebroken oplossing snel een geheeltallige oplossing te genereren die een zeer goede, maar niet per se optimale oplossingswaarde heeft). Het probleem van Branch-and-Bound is dat het soms best veel tijd kan kosten als hij veel verschillende mogelijkheden af moet gaan.

edit:
Even klein zinnetje toegevoegd....

[ Voor 5% gewijzigd door hammerhead op 11-07-2003 10:27 ]

[Oscar Mopperkont]

hammerhead schreef op 11 July 2003 @ 10:21:
Ik vermoed niet dat het je zal gaan lukken om 1428 knikker in 7 zakken te enumereren.....

Dat gaat zeker niet lukken nee! Dat had ik ook nog wel door. Zelfs met een superslimme branch-and-bound gaat je dat niet lukken (gok ik).

Verder weet ik ook niet welke programmeertaal je gebruikt... 87 Miljard elementen in een Array opslaan zal zeker weten niet gaan lukken

Delphi, maar het is ook niet nodig om er 87 miljard op te slaan. Er zijn "slechts" 210210 toegestaan. Meer hoef je niet op te slaan

Maar je kunt in Java gaan kijken naar dingen als Vectors of Hashmaps... Je moet namelijk wel kunnen controleren of een bepaalde set knikkers niet al bekend is, maar dan onder een andere volgorde. Dus uiteindelijk hoef je niet alle 87 miljard elementen op te slaan, maar slechts een gedeelte.

Daar heb ik geen kaas van gegeten...

Efficientere manieren zijn dingen waar ik ook mee bezig ben op dit moment. Ik weet niet hoe je precies je model hebt opgesteld, maar ik heb voor het oplossen van mijn probleem de integer eis laten vallen en los het hieruit ontstane LP probleem op met behulp van kolomgeneratie (dit aangezien er nog steeds wel heel veel mogelijkheden zijn....) Op het moment dat ik het LP probleem optimaal heb opgelost kijk ik of de oplossing die ik eruit krijg toevallig integer is. Zo ja, dan ben ik klaar en heb ik dus het ILP probleem bewezen optimaal opgelost en als de oplossing niet integer is (dus in jouw geval dat een knikker bijvoorbeeld voor 30% in zak 1 zit en 70% in zak 2)

Lagrange relaxatie

moet ik vanuit de LP oplossing een ILP oplossing gaan genereren. Hier is een algemene techniek voor die het optimaal doet (Branch-and-Bound) en verder kun je indien je zelf meer informatie over je domein weet een eigen heuristiek gaan implementeren om van de gebroken oplossing snel een geheeltallige oplossing te genereren die een zeer goede, maar niet per se optimale oplossingswaarde heeft). Het probleem van Branch-and-Bound is dat het soms best veel tijd kan kosten als hij veel verschillende mogelijkheden af moet gaan.

Ik gebruik simulated annealing voor het oplossen van het probleem. Volgens mij werkt het wel goed, maar dat wil ik dus ff onderbouwen. Vandaar mijn aftelproject.

[hammerhead]

Simulated annealing werkt op zich wel ok idd... Maar het probleem hiervan is dat je vrij makkelijk in een lokaal optimum terecht kan komen. Nu is SA wel bedoeld om hier uit te kunnen komen, maar nog hou je altijd het probleem dat je niet zeker weet of je nu het echte optimum of een lokaal optimum hebt gevonden.

Voor mijn probleem is het ILP probleem slechts de eerste fase van het probleem. Hierna moet ik met die oplossing weer andere dingen gaan doen en andere voorkeuren in de oplossing gaan verwerken die ik niet kan verwken op het moment dat ik met kolomgeneratie werk. Voor die fase ga ik waarschijnlijk ook werken met iets van SA of Tabu Search.

Ik weet overigens niet of de grootte van jouw probleem niet opgelost kan worden met een superslimme branch-and-bound. Ik mag voor mijn programma gebruik maken van het programma CPLEX en ik moet zeggen dat het wel verdomd snel en efficient is hoor... Ik vermoed dat het nog best wel een eind kan komen. Het enige wat wel een zeer groot probleem is als je jouw probleem zou willen oplossen met een ILP probleem en Brand-and-Bound is dat er heel veel dezelfde oplossingen zijn, er is veel symmetrie vanwege het feit dat de volgorde niet belangrijk is binnen een zak. Als je dat op een slimme manier eruit zou kunnen halen dan moet het misschien nog wel te doen zijn met Branch-and-Bound.

[kvdveer]

Uitgaand van Y zakken met aantallen Z₁, Z₂, ... Z_y-1, Z_y geldt volgens mij de volgende vergelijking:


Dat aantal loopt erg snel op met het aantal knikkers, maar dat was al duidelijk.
Code-matig zal het probleem niet al te lastig zijn, maar je zult serieus moeten denken over opslag. Bij zakken met kleine capaciteit loopt het aantal erg snel op...

code:

Function verdeel_over_zak(zakken[][], knikkers[]) {
   indien zak[1] niet vol - (
      voor iedere knikker i - (
         kopieer knikkers en zakken.
         Voeg knikker i toe aan kopie_van_zak[1]. 
         haal knikker uit kopie_van_knikkers[].
         verdeel_over_zak( kopie_van_zak[][], kopie_van_knikkers[]).
      )
   ) indien zak[1] vol - (
      verplaats zak[1] naar achterkant van zakken[].
      indien zak[1] vol - (
         voeg zakken toe als optie
      )
      indien zak[1] niet vol - (
         verdeel_over_zak( zakken[][], knikkers[] ).
      )
   )
)

edit:

grote toevoeging - afbeelding leesbaar gemaakt voor !slechtzienden

[ Voor 79% gewijzigd door kvdveer op 11-07-2003 11:20 ]

[Oscar Mopperkont]

hammerhead schreef op 11 July 2003 @ 10:58:
Simulated annealing werkt op zich wel ok idd... Maar het probleem hiervan is dat je vrij makkelijk in een lokaal optimum terecht kan komen. Nu is SA wel bedoeld om hier uit te kunnen komen, maar nog hou je altijd het probleem dat je niet zeker weet of je nu het echte optimum of een lokaal optimum hebt gevonden.

Tja, mijn afstudeerbegeleiders zijn helemaal "SA"-minded, dus het zal denk ik wel meevallen hoe groot dat risico is, dat je ver weg van een globaal optium zit.

Voor mijn probleem is het ILP probleem slechts de eerste fase van het probleem. Hierna moet ik met die oplossing weer andere dingen gaan doen en andere voorkeuren in de oplossing gaan verwerken die ik niet kan verwken op het moment dat ik met kolomgeneratie werk. Voor die fase ga ik waarschijnlijk ook werken met iets van SA of Tabu Search.

Tabu Search heb ik eigenlijk nooit echt van begrepen waarom dat echt goed zou werken. Snap de methode wel.

Ik weet overigens niet of de grootte van jouw probleem niet opgelost kan worden met een superslimme branch-and-bound. Ik mag voor mijn programma gebruik maken van het programma CPLEX en ik moet zeggen dat het wel verdomd snel en efficient is hoor... Ik vermoed dat het nog best wel een eind kan komen. Het enige wat wel een zeer groot probleem is als je jouw probleem zou willen oplossen met een ILP probleem en Brand-and-Bound is dat er heel veel dezelfde oplossingen zijn, er is veel symmetrie vanwege het feit dat de volgorde niet belangrijk is binnen een zak. Als je dat op een slimme manier eruit zou kunnen halen dan moet het misschien nog wel te doen zijn met Branch-and-Bound.

Het aantal unieke oplossingen bij mijn probleem is:
1428 boven 168 x 1260 boven 168 x 1092 boven 168 x 924 boven 168 x 756 boven 252 x 504 boven 252 x 252 boven 252 = heleboel

In dit topic staat mijn probleem overigens als ILP, mocht je het willen weten.
Hoe bewijs ik dat mijn probleem NP-lastig is?

_{Staat wel klein foutje in ipv X12 staat er egens de X boven 12, maar dat boeit niet zoveel.}

[Oscar Mopperkont]

kvdveer schreef op 11 juli 2003 @ 11:06:
Uitgaand van Y zakken met aantallen Z₁, Z₂, ... Z_y-1, Z_y geldt volgens mij de volgende vergelijking:
[afbeelding]

Het is iig goed te lezen voor slechtzienden!

[hammerhead]

Hmmm... Zat nog even na te denken over je oorspronkelijke vraag over het enumereren. Je zat dus met het probleem dat je unieke oplossingen wilt hebben en ook niet nog eens alle mogelijke permutaties daarvan. Is eigenlijk een vrij simpele oplossing:

Stappenplan:
* Genereer alle 14! mogelijke manieren om de 14 knikkers achter elkaar te leggen
* Stop de eerste zes knikkers in zak 1, de volgende 4 in zak 2, en de laatste 4 in zak3
* Voeg deze mogelijke oplossing alleen maar toe aan de uiteindelijke serie indien de knikkers van klein naar groot gesorteerd zijn:

Een tussenoplossing die je wel toevoegt:
Voor zak 1: 1 3 6 9 10 11
Voor zak 2: 2 4 5 12
Voor zak 3: 7 8 13 14
Dit omdat voor alle drie de zakken geldt dat de knikkers precies op volgorde liggen.

Een tussenoplossing die je niet meeneemt naar de uiteindelijke oplossing:
Voor zak 1: 11 10 9 6 3 1
Voor zak 2: 12 5 4 2
Voor zak 3: 7 8 13 14
Deze neem je niet mee omdat twee van de zakken niet precies geordend zijn. Deze oplossing is eigenlijk namelijk precies hetzelfde als de eerste oplossing, alleen op een andere volgorde.

Op deze manier zorg je er dus voor dat je alleen unieke oplossingen meeneemt in je verhaal.

[Oscar Mopperkont]

hammerhead schreef op 11 juli 2003 @ 11:33:
Hmmm... Zat nog even na te denken over je oorspronkelijke vraag over het enumereren. Je zat dus met het probleem dat je unieke oplossingen wilt hebben en ook niet nog eens alle mogelijke permutaties daarvan. Is eigenlijk een vrij simpele oplossing:

Stappenplan:
* Genereer alle 14! mogelijke manieren om de 14 knikkers achter elkaar te leggen
* Stop de eerste zes knikkers in zak 1, de volgende 4 in zak 2, en de laatste 4 in zak3
* Voeg deze mogelijke oplossing alleen maar toe aan de uiteindelijke serie indien de knikkers van klein naar groot gesorteerd zijn:

Een tussenoplossing die je wel toevoegt:
Voor zak 1: 1 3 6 9 10 11
Voor zak 2: 2 4 5 12
Voor zak 3: 7 8 13 14
Dit omdat voor alle drie de zakken geldt dat de knikkers precies op volgorde liggen.

Een tussenoplossing die je niet meeneemt naar de uiteindelijke oplossing:
Voor zak 1: 11 10 9 6 3 1
Voor zak 2: 12 5 4 2
Voor zak 3: 7 8 13 14
Deze neem je niet mee omdat twee van de zakken niet precies geordend zijn. Deze oplossing is eigenlijk namelijk precies hetzelfde als de eerste oplossing, alleen op een andere volgorde.

Op deze manier zorg je er dus voor dat je alleen unieke oplossingen meeneemt in je verhaal.

Dat is idd een slimme manier

Maar je zei zelf al dat je voor alle 1024 mogelijkheden 10 loopjes schreef,dus je moest hem herscrijven zodra je het voor 2048 mogelijkheden ding doen?
Bestaat er een algemene loop om een array met lengte x in alle mogelijke volgordes te zetten?

[hammerhead]

Ja.... Is recursieve manier voor.... Mijn manier was niet zo heel erg netjes, zeer inefficient Zeker in jouw geval. Mijn methode zal voor 10 knikkers 10 geneste forlussen van 1..10 doen. Voor 14 knikkers wordt het dus 14^14 wat opzich best wel een groot getal wordt Maar bij mijn probleem zat het net iets anders in elkaar waardoor het gewoon eigenlijk 10 bits waren en ik dus maar 1024 mogelijkheden had (had 10 geneste forlusjes van 0..1).

Echter even zoeken op internet leverde het volgende artikel op Generating permutations Op die manier kun je echt permutaties gegeneren van een bepaalde array (mijn methode zou nog veel meer combinaties uitrekenen waarin bijvoorbeeld knikker 3 meerdere keren voorkomt, en dat wil je niet....) Elke gegenereerde permutatie van de array zou je dus per direct kunnen controleren of het de gesorteerde is, zo ja schrijf je hem weg naar een bestand, of je doet er wat anders mee (berekent kosten en kijkt of die kleiner zijn dan de minimale kosten tot dan toe.. etc...). Als het niet een gesorteerde is, dan ga je gewoon gelijk door naar de volgende permutatie aangezien de huidige alleen maar een dubbele is van een andere oplossing.

Verder heb ik dat enumeratie programma alleen in het begin van mijn onderzoek geschreven puur om het probleem wat ik moest oplossen inzichtelijker te maken voor mezelf. Wordt dus op dit moment niet meer gebruikt in mijn programma.

[Oscar Mopperkont]

hammerhead schreef op 11 July 2003 @ 13:03:
Ja.... Is recursieve manier voor.... Mijn manier was niet zo heel erg netjes, zeer inefficient Zeker in jouw geval. Mijn methode zal voor 10 knikkers 10 geneste forlussen van 1..10 doen. Voor 14 knikkers wordt het dus 14^14 wat opzich best wel een groot getal wordt Maar bij mijn probleem zat het net iets anders in elkaar waardoor het gewoon eigenlijk 10 bits waren en ik dus maar 1024 mogelijkheden had (had 10 geneste forlusjes van 0..1).

Voor die 1024 mogelijkheden had je ook "gewoon" 0 t/m 1023 binair kunnen vertalen Is minder werk dan 10 lusjes. Heb het namelijk al eens moeten doen.

Echter even zoeken op internet leverde het volgende artikel op Generating permutations Op die manier kun je echt permutaties gegeneren van een bepaalde array (mijn methode zou nog veel meer combinaties uitrekenen waarin bijvoorbeeld knikker 3 meerdere keren voorkomt, en dat wil je niet....) Elke gegenereerde permutatie van de array zou je dus per direct kunnen controleren of het de gesorteerde is, zo ja schrijf je hem weg naar een bestand, of je doet er wat anders mee (berekent kosten en kijkt of die kleiner zijn dan de minimale kosten tot dan toe.. etc...). Als het niet een gesorteerde is, dan ga je gewoon gelijk door naar de volgende permutatie aangezien de huidige alleen maar een dubbele is van een andere oplossing.

Verder heb ik dat enumeratie programma alleen in het begin van mijn onderzoek geschreven puur om het probleem wat ik moest oplossen inzichtelijker te maken voor mezelf. Wordt dus op dit moment niet meer gebruikt in mijn programma.

Thnx voor artikel, ik gaat het bekijken

[hammerhead]

Oscar Mopperkont schreef op 11 juli 2003 @ 13:43:
[...]

Voor die 1024 mogelijkheden had je ook "gewoon" 0 t/m 1023 binair kunnen

Hmmmm.. Zal dat even onthouden voor de volgende keer. Echter die 10 lusjes schrijven kostte me eigenlijk geen moeite. Ik schrijf al mijn code in ViM en ik moet zeggen dat ik steeds meer leuke functies ontdek die ervoor zorgen dat ik steeds minder hoef in te tikken

[Soultaker]

Het berekenen van het aantal mogelijkheden is makkelijk, maar dat is hier geloof ik niet de bedoeling. Je wil alle verschillende mogelijkheden hebben. Wil je ze ook allemaal tegelijk in je geheugen hebben? Met andere woorden: wil je een functie die gegeven je invoer een lijst van oplossingen retourneert? Zo ja, dan moet je er aan denken dat er al snel ontzettend veel mogelijke oplossingen zijn en dat de benodigde hoeveelheid geheugen dus al snel gigantisch uit de klauwen gaat lopen.

Ik kan me echter ook voorstellen dat je per oplossing wat code wilt toepassen en dan hoef je de oplossingen slechts eenmalig te genereren (en kun je ze direct weer weggooien). Dit kost nog steeds veel CPU tijd (aangezien het aantal mogelijkheden groot blijft) maar het scheelt weer gigantisch in geheugen.

Van de oplossing met gebruikmaking van permutaties van de gehele rij ben ik niet echt gecharmeerd, omdat het gigantische overhead oplevert in sommige gevallen. Beschouw bijvoorbeeld de invoer: 20 knikkers, 2 zakken; één met een capaciteit van 2 knikkers en één met een capaciteit van 18 knikkers. Er zijn dan 20! (=2432902008176640000; ook wel achterlijk veel genoemd) permutaties die je allemaal na zou moeten gaan, terwijl er slechts 20*19 (=380) oplossingen zijn.

Je kunt waarschijnlijk dus beter een backtracking algoritme gebruiken (zeker aangezien je probleem toch al onoplosbaar wordt met veel knikkers en veel zakken met veel knikkers) waarbij je elke knikker recursief aan verschillende zakken toekent. Uiteraard hou je dan bij welke zakken vol zijn en op die manier kap je gelijke permutaties al tijdens het zoeken af. De recursie eindigt precies bij de oplossingen en de recursiediepte is gelijk aan het aantal beschikbare knikkers. Dat lijkt me een stuk prettiger.

Ik vind kvdveer's algoritme niet zo helder (heb er niet heel gedetailleerd naar gekeken) maar volgens mij probeert hij ook zoiets. Desgewenst kan ik wel een wat nauwkeurigere samenvatting van een geschikt algoritme geven. Merk op dat dit algoritme natuurlijk ook gebruikt kan worden om alle gevonden antwoorden in een grote verzameling te stoppen.

Overigens lijkt dit probleem me niets met lineair programmeren te maken hebben; je zoekt immers geen oplossing van een lineair stelsel, maar mogelijke combinaties met beperkingen van je invoer. Het lijkt me dus een combinatorisch probleem.

[ Voor 5% gewijzigd door Soultaker op 11-07-2003 14:43 ]

[Oscar Mopperkont]

Soultaker schreef op 11 July 2003 @ 14:41:
Het berekenen van het aantal mogelijkheden is makkelijk, maar dat is hier geloof ik niet de bedoeling.

Idd, de berekening is inmiddels al voorbij gekomen.

Je wil alle verschillende mogelijkheden hebben. Wil je ze ook allemaal tegelijk in je geheugen hebben?

Nee is niet nodig. Als ik alle (toegelaten) oplossingen maar langs kan gaan en de beste onthoud.

Met andere woorden: wil je een functie die gegeven je invoer een lijst van oplossingen retourneert? Zo ja, dan moet je er aan denken dat er al snel ontzettend veel mogelijke oplossingen zijn en dat de benodigde hoeveelheid geheugen dus al snel gigantisch uit de klauwen gaat lopen.

Precies, en het is ook overbodig, ben alleen geinteresseerd in het optimum

Ik kan me echter ook voorstellen dat je per oplossing wat code wilt toepassen en dan hoef je de oplossingen slechts eenmalig te genereren (en kun je ze direct weer weggooien).

Juist

Dit kost nog steeds veel CPU tijd (aangezien het aantal mogelijkheden groot blijft) maar het scheelt weer gigantisch in geheugen.

Kost idd gigantisch veel tijd, zeker omdat doelfunctie een lange berekening vergt

Van de oplossing met gebruikmaking van permutaties van de gehele rij ben ik niet echt gecharmeerd, omdat het gigantische overhead oplevert in sommige gevallen.

Het genereren van alle verschillende niet dubbele oplossingen zal toch niet zo superlang duren?

Beschouw bijvoorbeeld de invoer: 20 knikkers, 2 zakken; één met een capaciteit van 2 knikkers en één met een capaciteit van 18 knikkers. Er zijn dan 20! (=2432902008176640000; ook wel achterlijk veel genoemd) permutaties die je allemaal na zou moeten gaan, terwijl er slechts 20*19 (=380) oplossingen zijn.

Idd

Je kunt waarschijnlijk dus beter een backtracking algoritme gebruiken (zeker aangezien je probleem toch al onoplosbaar wordt met veel knikkers en veel zakken met veel knikkers) waarbij je elke knikker recursief aan verschillende zakken toekent. Uiteraard hou je dan bij welke zakken vol zijn en op die manier kap je gelijke permutaties al tijdens het zoeken af. De recursie eindigt precies bij de oplossingen en de recursiediepte is gelijk aan het aantal beschikbare knikkers. Dat lijkt me een stuk prettiger.

Als jij me dan vertelt hoe een procedure daarvoor er in pseudoprogrammeertaal uitziet.

Ik vind kvdveer's algoritme niet zo helder (heb er niet heel gedetailleerd naar gekeken) maar volgens mij probeert hij ook zoiets. Desgewenst kan ik wel een wat nauwkeurigere samenvatting van een geschikt algoritme geven.

Dat zou rieleks zijn

Merk op dat dit algoritme natuurlijk ook gebruikt kan worden om alle gevonden antwoorden in een grote verzameling te stoppen.

Ok

Overigens lijkt dit probleem me niets met lineair programmeren te maken hebben; je zoekt immers geen oplossing van een lineair stelsel, maar mogelijke combinaties met beperkingen van je invoer. Het lijkt me dus een combinatorisch probleem.

Het is idd een combinatorisch optimaliseringsprobleem, maar dat sluit niet uit dat het ook als een ILP geformuleerd kan worden, zoals ik dus ook gedaan heb.

[Soultaker]

Oscar Mopperkont schreef op 11 juli 2003 @ 14:58:
Het genereren van alle verschillende niet dubbele oplossingen zal toch niet zo superlang duren?

Dat hangt er dus maar vanaf hoeveel oplossingen er zijn. Als je 20 zakken van 1 knikker hebt, zit je al weer op die rottige 20! en hoewel het genereren op zich redelijk efficient is, zit je dan weer vreselijk veel oplossingen te produceren.

Uiteraard zou je met een goede heuristiek of andere eigenschappen van je probleem de mogelijkheden verder kunnen beperken, bijvoorbeeld door veelbelovende combinaties eerst te genereren en latere combinaties af te kappen zodra je vast kunt stellen dat ze slechter zijn dan het huidige optimum. Daarvoor is het echter wel vereist dat je de (minimale) waarde van een gedeeltelijke oplossing (waarin bijvoorbeeld maar voor de helft van de knikkers bekend is in welke zak ze komen) kunt inschatten. Voorlopig lijkt me dat erg ingewikkeld; ik zou dat eerder als een uitbreiding zien. Gelukkig is een backtrackingalgoritme eenvoudig uit te breiden met van dit soort extra constraints.

Als jij me dan vertelt hoe een procedure daarvoor er in pseudoprogrammeertaal uitziet. [...] Dat zou rieleks zijn

Dat gaat me iets meer tijd kosten dan ik vandaag bereid ben te investeren; mischien dat ik er van het weekend zin in heb om dat uit te werken, maar het is eigenlijk niet zo ingewikkeld. Misschien kun je ook eens naar kvdveer's oplossing kijken, want volgens mij doet die het ook goed (disclaimer: nog niet echt in detail naar gekeken).

Het is idd een combinatorisch optimaliseringsprobleem, maar dat sluit niet uit dat het ook als een ILP geformuleerd kan worden, zoals ik dus ook gedaan heb.

Ah accoord. Helaas ben ik niet zo thuis in lineaire oplossingsalgoritmen (zeker daar ik in dit topic allerlei termen voorbij zie komen die ik niet ken). Er zijn trouwens ook veel goede standaardlibraries beschikbaar voor het oplossen van lineaire problemen, maar je moet dan wel je probleem correct weten te formuleren (en het probleem is dat je daarvoor weer redelijk goed thuis moet zijn in het lineaire programmeren).

[Oscar Mopperkont]

Soultaker schreef op 11 July 2003 @ 15:08:
Dat hangt er dus maar vanaf hoeveel oplossingen er zijn. Als je 20 zakken van 1 knikker hebt, zit je al weer op die rottige 20! en hoewel het genereren op zich redelijk efficient is, zit je dan weer vreselijk veel oplossingen te produceren.

Uiteraard zou je met een goede heuristiek of andere eigenschappen van je probleem de mogelijkheden verder kunnen beperken, bijvoorbeeld door veelbelovende combinaties eerst te genereren en latere combinaties af te kappen zodra je vast kunt stellen dat ze slechter zijn dan het huidige optimum. Daarvoor is het echter wel vereist dat je de (minimale) waarde van een gedeeltelijke oplossing (waarin bijvoorbeeld maar voor de helft van de knikkers bekend is in welke zak ze komen) kunt inschatten. Voorlopig lijkt me dat erg ingewikkeld; ik zou dat eerder als een uitbreiding zien.

Dat is eigenlijk branch en bound, waarbij eerst naar de meest veelbelovende "takken" wordt gekeken.

Dat gaat me iets meer tijd kosten dan ik vandaag bereid ben te investeren; mischien dat ik er van het weekend zin in heb om dat uit te werken, maar het is eigenlijk niet zo ingewikkeld. Misschien kun je ook eens naar kvdveer's oplossing kijken, want volgens mij doet die het ook goed (disclaimer: nog niet echt in detail naar gekeken).

Dat zou wel rieleks zijn

Ah accoord. Helaas ben ik niet zo thuis in lineaire oplossingsalgoritmen (zeker daar ik in dit topic allerlei termen voorbij zie komen die ik niet ken). Er zijn trouwens ook veel goede standaardlibraries beschikbaar voor het oplossen van lineaire problemen, maar je moet dan wel je probleem correct weten te formuleren (en het probleem is dat je daarvoor weer redelijk goed thuis moet zijn in het lineaire programmeren).

Maar eens aan mijn aftsudeerdocent vragen zodra hij terug is van vakantie. Helaas duurt dat nog een maand

[mocean]

hammerhead schreef op 11 juli 2003 @ 11:33:
Hmmm... Zat nog even na te denken over je oorspronkelijke vraag over het enumereren. Je zat dus met het probleem dat je unieke oplossingen wilt hebben en ook niet nog eens alle mogelijke permutaties daarvan. Is eigenlijk een vrij simpele oplossing:

Stappenplan:
* Genereer alle 14! mogelijke manieren om de 14 knikkers achter elkaar te leggen
* Stop de eerste zes knikkers in zak 1, de volgende 4 in zak 2, en de laatste 4 in zak3
* Voeg deze mogelijke oplossing alleen maar toe aan de uiteindelijke serie indien de knikkers van klein naar groot gesorteerd zijn:

Een tussenoplossing die je wel toevoegt:
Voor zak 1: 1 3 6 9 10 11
Voor zak 2: 2 4 5 12
Voor zak 3: 7 8 13 14
Dit omdat voor alle drie de zakken geldt dat de knikkers precies op volgorde liggen.

Een tussenoplossing die je niet meeneemt naar de uiteindelijke oplossing:
Voor zak 1: 11 10 9 6 3 1
Voor zak 2: 12 5 4 2
Voor zak 3: 7 8 13 14
Deze neem je niet mee omdat twee van de zakken niet precies geordend zijn. Deze oplossing is eigenlijk namelijk precies hetzelfde als de eerste oplossing, alleen op een andere volgorde.

Op deze manier zorg je er dus voor dat je alleen unieke oplossingen meeneemt in je verhaal.

Deze optie klinkt wel handig ja.

Maar je hoeft toch niet gelijk alle 14! mogelijkheden te berekenen?
Ik zou per zak de mogelijkheden voor die zak berekenen/bepalen.

En dan is het berekenen van het totaal aantal mogelijkheden niet moeilijk meer.

[hammerhead]

Kan idd ook. Je hoeft overigens niet alle 14! mogelijkheden te berekenen, je hoeft er slechts () 14!/2 te berekenen aangezien je namelijk mag ophouden zodra het eerste getal groter wordt dan dan de helft van het totaal aantal knikkers. Dit kan omdat ik had gesteld dat ik alleen unieke oplossing wilde gaan bekijken en ik kon makkelijk ervoor zorgen alleen maar unieke oplossing te gebruiken door alleen oplossingen te gebruiken waarvan alle nummertjes opeenvolgend gesorteerd waren. Dit kan sowieso al niet meer op het moment dat het eerste getal groter dan de helft wordt.

Echter, BIG DISCLAIMER: Deze code is niet snel. De TS vroeg zich af of er een methode was die alle mogelijkheden kon enumereren. Hij had hierbij opgegeven dat de grootte 14 knikkers was en drie zakken. Aangezien 14! iets van 85 miljard was en je met deze methode slechts iets van 42 miljard oplossingen hoeft te bekijken is het waarschijnlijk nog wel te doen. Ga je echter idd met 20 knikkers werken dan zal deze methode ook zeker niet meer gaan werken en zul je slimmere methoden moeten gaan verzinnen.

[Buffy]

Zoals ACM al aan gaf is het probleem te reduceren tot het kiezen van Z knikkers uit X knikkers en voor de volgende zak het zelfde te doen met de overgebleven knikkers.
Het probleem komt er dus op neer om alle unieke selecties van Z knikkers uit X knikkers te kiezen.

Als je kijkt naar een simple voorbeeldje van 3 knikkers uit 5 knikkers genummerd 1 t/m 5 dan krijg je de volgende combinaties:

code:

123    134    145
124    135
125
-------------------------
234     245
235
--------------------------
345

oftewel in pseudo code met Z[z] de knikkers in de zak en X[x] de te verdelen knikkers:

code:

for i = 1 to x-z+1 do
     Z[1] = X[i]
     for j = i+1 to x-z+2 do
          Z[2] = X[j]
           for k = j+1 to x-z+3 do
                Z[3] = X[k]
                /* recursieve aanroep voor de volgende zak met overgebleven knikkers */
          od
     od
od

Natuurlijk moeten de for-lussen niet hard geprogrameerd worden omdat drie geneste lussen z == 3 implicieerd. Tevens moet je op een efficiente manier de overgebleven knikkers bij houden maar dat moet te doen zijn.


PS: zijn de zakken eigenlijk wel uniek of zijn de zakken met de zelfde grootte onderling uitwisselbaar?