Soort packing algoritme nodig

[Verwijderd]

Hallo,

Ik ben op zoek naar een soort packingalgoritme waarvan ik, na tevergeefs zoeken, maar niet op de naam kan komen. Ik vermoed dat het qua complexiteit een nogal moeilijk probleem is (NP?), dus als iemand een geoptimaliseerd benaderingsalgoritme weet, heel graag!

Het probleem is beste uit te leggen aan de hand van een afbeelding:



De bovenste 3 rijen bevatten gekleurde blokjes met een hoop witruimte. De hoeveelheid witruimte moet geminimaliseerd woorden door de rijen als het waren in elkaar te persen, waarbij de blokjes van rij mogen verwisselen. Een mogelijke eindsituatie is onderaan de afbeelding te zien: het aantal rijen is verminderd: minder rijen is in dit geval zelfs onmogeljk. Kent iemand een algoritme wat zoiets voor elkaar krijgt? Wellicht kan het ook onder de noemer 'matching' algoritmes vallen.

[gorgi_19]

Bedoel je dit? Wikipedia: Knapsack problem

[MTWZZ]

Bij onze grote vriend Google lever het volgende op als je zoekt naar packing algorithm:
- Wikipedia: Bin packing problem (goeie kandidaat)
- http://www.csc.liv.ac.uk/~epa/surveyhtml.html (maar dan met vierkantjes)

@Gorgi_19: grr!

[ Voor 3% gewijzigd door MTWZZ op 22-05-2008 21:04 ]

[Verwijderd]

De genoemde webpagina's had ik in m'n zoektocht ook al gevonden, maar volgens mij is mijn probleem anders doordat de verticale locatie van de blokjes niet mag veranderen. Het lijkt dus wel erg op het knapsack probleem, en ook wel het bin probleem, echter zit er een extra contraint op (dat die positie dus niet mag veranderen).

[Onbekend]

Wat is er mis met zelf een (benaderings)algoritme te schrijven?

Je sorteert de blokjes eerst op volgorde van links naar rechts.
Vervolgens begin je met het meest linker blokje. Die streep je weg en ga je kijken welk volgende blokje het als eerste in past. Die streep je ook weg en dit doe je net zo lang totdat je balk vol is.
Daarna begin je weer met een lege balk en ga je weer het eerst volgend blokje zoeken die er in past.

[Fish]

Onbekend schreef op donderdag 22 mei 2008 @ 21:12:
Wat is er mis met zelf een (benaderings)algoritme te schrijven?

Je sorteert de blokjes eerst op volgorde van links naar rechts.
Vervolgens begin je met het meest linker blokje. Die streep je weg en ga je kijken welk volgende blokje het als eerste in past. Die streep je ook weg en dit doe je net zo lang totdat je balk vol is.
Daarna begin je weer met een lege balk en ga je weer het eerst volgend blokje zoeken die er in past.

iets met wiel opnieuw uitvinden . en optimalisatie ? iets met bubblesort vs quicksort etc

[Jaap-Jan]

fish schreef op donderdag 22 mei 2008 @ 21:23:
[...]


iets met wiel opnieuw uitvinden . en optimalisatie ? iets met bubblesort vs quicksort etc

Welk wiel? Er is nog geen standaardoplossing voor het knapzakprobleem.

[roy-t]

Verwijderd schreef op donderdag 22 mei 2008 @ 21:09:
De genoemde webpagina's had ik in m'n zoektocht ook al gevonden, maar volgens mij is mijn probleem anders doordat de verticale locatie van de blokjes niet mag veranderen. Het lijkt dus wel erg op het knapsack probleem, en ook wel het bin probleem, echter zit er een extra contraint op (dat die positie dus niet mag veranderen).

Opzich zou je het algoritme prima kunnen omschrijven als "een doos met hoogte 1 en breedte 10" waar bij de code exact het zelfde blijft (of iig dat vermoed ik, niet naar de website gekeken) Anders is er aan de hand van een 2 dimensioneel voorbeeld toch ook wel een 1 dimensioneel programma uit te kloppen? Niet alles is zomaar kant en klaar natuurlijk

[pedorus]

Onbekend schreef op donderdag 22 mei 2008 @ 21:12:
Wat is er mis met zelf een (benaderings)algoritme te schrijven?

Je sorteert de blokjes eerst op volgorde van links naar rechts.
Vervolgens begin je met het meest linker blokje. Die streep je weg en ga je kijken welk volgende blokje het als eerste in past. Die streep je ook weg en dit doe je net zo lang totdat je balk vol is.
Daarna begin je weer met een lege balk en ga je weer het eerst volgend blokje zoeken die er in past.

Als ik het goed zie is dit probleem niet NP-compleet. Volgens mij is het algoritme hierboven niet een benaderingsalgoritme, maar geeft het een optimale oplossing. (net zo lang totdat je balk vol is-->zo lang totdat er geen blokje meer geplaatst kan worden)

[curry684]

fish schreef op donderdag 22 mei 2008 @ 21:23:
[...]


iets met wiel opnieuw uitvinden . en optimalisatie ? iets met bubblesort vs quicksort etc

Toch is voor dit specifieke geval zijn gegeven optie ook voor zover ik kan zien de meest optimale oplossing in de minimale tijd (logaritmisch door de sort, lager gaat ie niet). Tis namelijk niet knapsack, en die is zoals gesteld nog niet optimaal opgelost

[Zoijar]

pedorus schreef op donderdag 22 mei 2008 @ 21:33:
Als ik het goed zie is dit probleem niet NP-compleet. Volgens mij is het algoritme hierboven niet een benaderingsalgoritme, maar geeft het een optimale oplossing. (net zo lang totdat je balk vol is-->zo lang totdat er geen blokje meer geplaatst kan worden)

Jawel, dit is een NPC probleem. Je ziet ook al met lengtes 4,4,3,3,3 bv en een balk van 9, sorteer algoritme vult het tot 8 met twee keer een 4 en dan past er niks meer. Optimaal algoritme pakt drie keer een 3. (dat is dan met 1 bin, maar je krijgt soortgelijke dingen met een variabel aantal bins)

[ Voor 7% gewijzigd door Zoijar op 22-05-2008 21:45 ]

[MPEG]

Wat je zoekt is het bestfit algorithme. Dit bestaat in twee vormen offline en online. Het grote verschil tussen deze twee is dat het offline compactere bins kan maken in tegenstelling tot het online type.
Het online type wordt bijvoorbeeld gebruikt voor het on-the-fly vullen van bins waarbij het totale aantal bins dat tegelijk open kan blijven beperkt is.

Voorbeelden:
http://www.developerfusion.co.uk/show/5540/5/
http://www2003.org/cdrom/papers/refereed/p445/node9.html
http://www.google.com/sea...q=best+fit+algorithm&aq=f

[MPEG]

Toevoeging op mijn vorige post: je hebt de online versie nodig, die plaats blokken in de bins waar het past, zodra een bin niet genoeg ruimte heeft wordt een nieuwe bin gestart.

(Offline type zal altijd proberen zo min mogelijk bins te gebruiken)

[pedorus]

Verwijderd schreef op donderdag 22 mei 2008 @ 21:09:
maar volgens mij is mijn probleem anders doordat de verticale locatie van de blokjes niet mag veranderen.

Zoijar schreef op donderdag 22 mei 2008 @ 21:41:
[...]
Jawel, dit is een NPC probleem. Je ziet ook al met lengtes 4,4,3,3,3 bv en een balk van 9, sorteer algoritme vult het tot 8 met twee keer een 4 en dan past er niks meer. Optimaal algoritme pakt drie keer een 3. (dat is dan met 1 bin, maar je krijgt soortgelijke dingen met een variabel aantal bins)

Lengtes op welke positie? Het gaat hier niet om het knapsack probleem, maar om een probleem vergelijkbaar met het probleem dat je hebt met zalen en huurperiodes. (En dan ook nog eens het vereenvoudigde probleem waarbij elke zaal dezelfde capaciteit en kwaliteiten heeft. Huurauto's ipv zalen is misschien beter.)

[NMe]

Waar hoort mijn topic?

Hier wordt niets geprogrammeerd, dit is vooralsnog allemaal pure theorie, dus: PRG>>SEA

[Onbekend]

Zoijar schreef op donderdag 22 mei 2008 @ 21:41:
[...]

Jawel, dit is een NPC probleem. Je ziet ook al met lengtes 4,4,3,3,3 bv en een balk van 9, sorteer algoritme vult het tot 8 met twee keer een 4 en dan past er niks meer. Optimaal algoritme pakt drie keer een 3. (dat is dan met 1 bin, maar je krijgt soortgelijke dingen met een variabel aantal bins)

Je mag de blokken niet horizontaal verschuiven, maar wel vertikaal. Dit betekent dat je soms verplicht grote witruimtes kan hebben terwijl andere blokken gemakkelijk in zouden passen als ze op een andere horizontale positie stonden.

[Wolfboy]

Als ik het zo zie is het gewoon een standaard "interval scheduling" probleem, iets waar wel een algoritme voor te vinden is.

[Verwijderd]

pedorus schreef op donderdag 22 mei 2008 @ 21:51:
Lengtes op welke positie? Het gaat hier niet om het knapsack probleem, maar om een probleem vergelijkbaar met het probleem dat je hebt met zalen en huurperiodes. (En dan ook nog eens het vereenvoudigde probleem waarbij elke zaal dezelfde capaciteit en kwaliteiten heeft. Huurauto's ipv zalen is misschien beter.)

Zalen is wel degelijk een goed voorbeeld, daar kun je ook niet horizontaal (tijd) schuiven, maar vaak wel verticaal (zaal). Maar idd, zalen met verschillende capaciteit en features maken 't nog een stuk lastiger, en met schuifwanden wordt 't helemaal vervelend. Stel je hebt zaal 6A en 6B, en door de schuifwand weg te halen combineren die 2 tot zaal 6. Op 't moment dat zaal 6 verhuurd is, zijn 6A en 6B niet meer verhuurbaar, en andersom.

[curry684]

Ja, dan maak je het probleem ineens wel complex, maar dat was de vraag niet

Onbekend's algoritme is heel simpel per definitie de optimale oplossing voor het probleem als gepresenteerd in de topicstart, en in een paar regels code te implementeren.

[Verwijderd]

Ik gebruik Onbekend's algoritme ook (iets aangepast) bij 't automatisch toewijzen van hotelkamers of vergaderkamers. Die zijn vaak voor 80 of 90% uitwisselbaar.
De aanpassingen hebben vooral te maken met de voorkeuren van gasten/klanten (kamer dicht bij de lift, of niet hoger dan de 3e etage, of vergaderkamer met zicht op de tuin, dat soort dingen). Dan heb je toch al gauw iets meer dan een paar regels code nodig...

[AaroN]

kijk naar schedulers, distributed algorithms: Least Slack Time first scheduling algorithm is het algoritme dat je zoekt, meer info: Jane Liu, Real Time Systems, Prentice Hall, 2000.

[Verwijderd]

AaroN, bij LST mag je (tot op zekere hoogte) wel 'horizontaal schuiven'. Dat is hier dus geen echte oplossing denk ik...

[AaroN]

Verwijderd schreef op donderdag 22 mei 2008 @ 23:22:
AaroN, bij LST mag je (tot op zekere hoogte) wel 'horizontaal schuiven'. Dat is hier dus geen echte oplossing denk ik...

Daarop kun je de release times instellen he. Je kunt een taak niet eerder schedulen dan zijn release time. Release time = Deadline - Processortime.

Je zult uiteraard een beetje moeten tweaken, maar dat is niet het grootste probleem denk ik. Sowieso lijkt me dit helemaal niet zo'n groot probleem..

[ Voor 21% gewijzigd door AaroN op 22-05-2008 23:30 ]

[Boss]

Om hoeveel verschillende pakjes gaat dit? Aangezien de plaats van de pakjes vast is, valt het aantal mogelijkheden mee. Als je er niet te veel tijd in wilt stoppen kan je nog een heel end komen met brute-force

[Voutloos]

Boss schreef op vrijdag 23 mei 2008 @ 08:54:
Als je er niet te veel tijd in wilt stoppen kan je nog een heel end komen met brute-force

Als het implementeren van het algoritme van Onbekend je veel tijd kost, zal je wellicht ook niet met 5 minuutjes klaar zijn met een brute force versie.

En dat algoritme is gewoon al de optimale oplossing...

[ Voor 8% gewijzigd door Voutloos op 23-05-2008 09:09 ]

[pkuppens]

Wat een hoop klokken en klepels die allemaal tegen elkaar in gaan.
Op het risico af bij te dragen aan de kakafonie hier wat ik denk dat gevraagd wordt:

Probleem:
gegeven intervallen (x_i,y_i), vind minimaal aantal s van stroken S, waarbij het mogelijk is alle (x_i,y_i)'s toe te kennen aan S(j)'s waarbij geen twee intervallen overlappen binnen zo'n strook.

code:

sorteer de verzameling Z = {x_i} U {y_i} ( = {z_i} )

s = 0;

foreach z_i, // z_i == x_j wil dadelijk zeggen dat z_i de start van (x_j,y_j) is etc.
   z_i == x_j -> s++ ; als s > s_max, doe wat administratie op s_max en V, de set vrije stroken
                 S(V(s)) += (x_j,y_j);
   z_i == y_j -> s--; doe wat administratie om strook V(s) weer vrij te geven
end

[curry684]

Bluh geneuzel allemaal, heb maar even een proof of concept gemaakt.

Met de blocks parameter kun je het aantal blokken aanpassen (5 tot 1000), kunt zo vaak refreshen als je wilt.

[Voutloos]

Leuk gedaan. Met de droge theorie en bepaalde schedulers kom je er idd ook, maar het is, dankzij de beperking dat je de blokken niet horizontaal mag schuiven echt een stuk eenvoudiger.

En je kan op de bovenstaande link gewoon simpelweg zien dat het altijd optimaal is, aangezien je met de kleinere aantallen blokken eenvoudig op 1 scherm kan zien dat er een verticale lijn is waar in elke rij een deel van een blok zit. Mbv scheduling theorie kan je hoogstens de whitespace beter plaatsen (bv. zoveel mogelijk in de laatste rijen), maar dat was dus geen eis van de ts, dus KISS

[.oisyn]

Wolfboy schreef op donderdag 22 mei 2008 @ 22:32:
Als ik het zo zie is het gewoon een standaard "interval scheduling" probleem, iets waar wel een algoritme voor te vinden is.

Hierin mag je alsnog horizontaal schuiven, zolang een interval maar niet over een bepaalde grens heen gaat. Het probleem van de TS is feitelijk nog veel simpeler.

Het leuke van dit specifieke probleem is het vergelijkbaar is met een ander probleem dat een tijdje terug naar voren was gekomen: [SQL] Maximum aantal resultaten per seconde.
Het aantal balken dat je namelijk nodig gaat hebben is namelijk het maximum aantal blokken dat op een willekeurig punt overlappen.

[pkuppens]

.oisyn schreef op vrijdag 23 mei 2008 @ 11:41:
[...]

Hierin mag je alsnog horizontaal schuiven, zolang een interval maar niet over een bepaalde grens heen gaat. Het probleme van de TS is feitelijk nog veel simpeler.

Het leuke van dit specifieke probleem is het vergelijkbaar is met een ander probleem dat een tijdje terug naar voren was gekomen: [SQL] Maximum aantal resultaten per seconde.
Het aantal balken dat je namelijk nodig gaat hebben is namelijk het maximum aantal blokken dat op een willekeurig punt overlappen.

Pssst. niet te hard. Ik deed net met m'n pseudo-code m'n best om in 2 verschillende topics slim voor de dag te komen.

[curry684]

Pompom is topicstarter z'n topic kwijt na de move of zo? Of heb ik die l33te code gewoon voor niets geschreven?

[pkuppens]

curry684 schreef op zaterdag 24 mei 2008 @ 14:17:
Pompom is topicstarter z'n topic kwijt na de move of zo? Of heb ik die l33te code gewoon voor niets geschreven?

Bij deze heb je het (op z'n minst) gedaan voor mijn eeuwig respect van de dag...