Wetenschapsforum

Ik zit met volgend probleem:

Stel je hebt n rechthoeken. De grootte van de rechthoeken verschilt per rechthoek. Hoe kan ik deze rechthoeken op zo'n manier laten schikken in een 2D vlak, om een minimale totale oppervlakte te bekomen.

Heeft iemand hiervoor een behoorlijk algoritme, en eventueel ook de uitleg van het algoritme

Ik denk dat je even zal moeten verduidelijken. Als je n rechthoeken hebt met oppervlakte S_i, dan kan je deze toch niet minimaliseren?

Hij wil waarschijnlijk een soort van legpuzzel maken waarbij je de rechthoeken zo ordent dat de omhullende rechthoek van het geheel zo'n klein mogelijke oppervlakte heeft.

Maar ik kan helaas niet helpen

Ahzo. Echt helpen kan ik dan ook niet. Mogelijk vind je hier iets: http://en.wikipedia.org/wiki/List_of_algorithms

Ik bedoel inderdaad wat cycloon zegt. K'zie ook niet echt een manier om eraan te beginnen, dus als iemand een principe weet zou dat al een stap in de goede richting zijn.

Tjah voor wanneer het rechthoeken nog niet in de 10.000 gaat dan kun je gewoon bruteforcen anders moet je toch wel al richting een AI aan gaan zitten denken...

Ik weet wel dat een aantal studenten van de TU delft of eindhoven (weet niet meer) bezig waren met een studie over hoe het bagage systeem te optimaliseren zodat er zoveel mogelijk bagage past in zo'n klein mogelijke ruimte... Hetzelfde probleem als jij dus hebt maar dan 3D. Heb geprobeerd info te vinden maar kan helaas niets vinden op dit moment...

Bruteforce vindt ik geen goede oplossing, stel dat je zo'n honderd vierkanten als invoer krijgt lost zelfs een serieuze computer dat niet op in een tiental minuutjes.

Dat probleem was een van de opdrachten van het vak combinatieve algoritmen dat ik ooit eens gevolgd heb. Ik heb mijn oplossing niet in mijn oude papieren terug kunnen vinden. Het was in ieder geval een "uitdagende" opgave.

Ik denk dat het ging met backtracking.

http://en.wikipedia.org/wiki/Backtracking

Je moet er wel bij zeggen dat de rechthoeken binnen een gegeven grote rechthoek moeten liggen.

Mogen de rechthoeken roteren of zelfs draaien met 1 graad etc?

Als het om fotos gaat op een beeldscherm dan kan men deze niet roteren...

Moet je het ook mooi vullen?

Dus zoveel mogelijk een vierkant of mooie rechthoek creeeren.

Wat gebeurd er met diegene die niet gaan passen?

Volgens mij kun je het beste eerst vijf indexen maken van alle vierkanten.

De index voor breedte en hoogte sorteren op maat.

De derde index verwijst naar een geheugen die een x,y positie bijhoudt.

De vierde index verwijst naar een scorelijst van een aantal elementen

De vijfde index is een werklijst die men nodig heeft.

De vijfde omvat toegepast of nog niet toegepast.

men gaat dan de routine laten puzzelen met een beetje logica en random...

Na een tig tal puzzelingen gaat men de score bekijken.

De beste score kan dan de beste oplossing zijn.

Men kan een timer test inbouwen om te zorgen dat de routine niet te lang bezig is.

Men kan een puzzelingen getal laten berekenen bij het begin naarmate de aangeleverde data.

Men kan ook nog een hulparray construeren voor het invullen.

De computer rekent dan sneller.

Men kan eerst van grof naar fijn werken.

Men kan ook wat XOR technieken toepassen met random.

Men gebruikt geheugen voor de XOR.

En niet alleen in vlakken denken, ook in lijnen.

De rechthoek steeds kleiner maken.

Kleine rechthoeken combineren tot een grote,men gebruikt dan weer geheugen voor die virtuele rechthoeken.

Niet 1 2 3 programmeren maar een beetje van dit en beetje van dat.

ZO komt men er wel...

Dit soort problemen maar dan in 3D wordt gewoonlijk aangeduid met: binpacking of knapsack problem

De oplossing is dan via het zogenaamde branch and bound algoritme.

Voor dit 2D problem zal dit algoritme ook wel gebruikt kunnen worden.

Mooi. Daar ken ik het dus van. Het is eenvoudig aan te passen voor 2D.

Het kan natuurlijk ook altijd met exhaustive search.

Het kan natuurlijk ook altijd met exhaustive search.

Gaat dit, zoals Vladimir Lenin ook al aangaf, voor een groot aantal rechthoeken niet te lang duren?

Vast wel.

Het is sowieso nuttig kennis te nemen van de branch and bound methode, omdat je het op veel meer problemen kunt toepassen (b.v. op het handelsreizigersprobleem).

Bedankt voor de reacties, ik ga het eens rustig bekijken, maar het ziet er op het eerste zicht krachtig genoeg uit.