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
-
Vladimir Lenin
- Artikelen: 0
- Berichten: 829
- Lid geworden op: do 25 sep 2008, 14:15
Optimalisatieprobleem
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)
--Vladimir Lenin-- (Владимир Ильич Ульянов)
-
jhnbk
- Artikelen: 0
- Berichten: 6.905
- Lid geworden op: za 16 dec 2006, 09:10
Re: Optimalisatieprobleem
Ik denk dat je even zal moeten verduidelijken. Als je n rechthoeken hebt met oppervlakte Si, dan kan je deze toch niet minimaliseren?
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
-
Cycloon
- Artikelen: 0
- Berichten: 4.810
- Lid geworden op: ma 24 jan 2005, 20:56
Re: Optimalisatieprobleem
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
Maar ik kan helaas niet helpen
-
jhnbk
- Artikelen: 0
- Berichten: 6.905
- Lid geworden op: za 16 dec 2006, 09:10
Re: Optimalisatieprobleem
Ahzo. Echt helpen kan ik dan ook niet. Mogelijk vind je hier iets: http://en.wikipedia.org/wiki/List_of_algorithms
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
-
Vladimir Lenin
- Artikelen: 0
- Berichten: 829
- Lid geworden op: do 25 sep 2008, 14:15
Re: Optimalisatieprobleem
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.
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)
--Vladimir Lenin-- (Владимир Ильич Ульянов)
-
Chip
- Artikelen: 0
- Berichten: 157
- Lid geworden op: vr 22 sep 2006, 20:14
Re: Optimalisatieprobleem
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...
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...
-
Vladimir Lenin
- Artikelen: 0
- Berichten: 829
- Lid geworden op: do 25 sep 2008, 14:15
Re: Optimalisatieprobleem
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.
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)
--Vladimir Lenin-- (Владимир Ильич Ульянов)
-
PeterPan
- Artikelen: 0
Re: Optimalisatieprobleem
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.
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.
-
Schwartz
- Artikelen: 0
- Berichten: 691
- Lid geworden op: di 14 mar 2006, 18:14
Re: Optimalisatieprobleem
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...
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...
Een computertaal is voor mensen, niet voor de computer.
-
Fred F.
- Pluimdrager
- Artikelen: 0
- Berichten: 4.167
- Lid geworden op: wo 15 nov 2006, 19:21
Re: Optimalisatieprobleem
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.
De oplossing is dan via het zogenaamde branch and bound algoritme.
Voor dit 2D problem zal dit algoritme ook wel gebruikt kunnen worden.
Hydrogen economy is a Hype.
-
PeterPan
- Artikelen: 0
Re: Optimalisatieprobleem
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.
-
jhnbk
- Artikelen: 0
- Berichten: 6.905
- Lid geworden op: za 16 dec 2006, 09:10
Re: Optimalisatieprobleem
Gaat dit, zoals Vladimir Lenin ook al aangaf, voor een groot aantal rechthoeken niet te lang duren?Het kan natuurlijk ook altijd met exhaustive search.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
-
PeterPan
- Artikelen: 0
Re: Optimalisatieprobleem
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).
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).
-
Vladimir Lenin
- Artikelen: 0
- Berichten: 829
- Lid geworden op: do 25 sep 2008, 14:15
Re: Optimalisatieprobleem
Bedankt voor de reacties, ik ga het eens rustig bekijken, maar het ziet er op het eerste zicht krachtig genoeg uit.
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)
--Vladimir Lenin-- (Владимир Ильич Ульянов)
