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
Laatste berichten
-
06:56
Casus uit de praktijk: positief test THC 3
-
22:01
vB 7
-
21:45
Vreemde stank in huis 9
-
08:39
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 1
-
08:34
Python: sockets sluiten 4
-
14 apr
Een eenvoudige logische redenering waarom tijd niet kan bestaan 'daarbuiten' 6
-
14 apr
Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k 3
-
13 apr
Rotatie van het heelal 22
-
13 apr
Documentenverdwijnen uit onedrive 1
-
12 apr
Behoud van impulsmoment en energie 5
-
12 apr
INLOG STORING / TIPS 4
-
09 apr
[natuurkunde] systeemgrafen 1
-
05 apr
afbuiging licht rond zware objecten via grondbeginselen relativiteitstheorie 490
-
05 apr
Ongepaste reclame 179
-
04 apr
Gegevens wissen mobiel 6
-
04 apr
Geiger Muller telbuis 2
-
03 apr
Schroefdraad berekening 3
-
03 apr
Relatieve luchtvochtigheid 26
-
03 apr
tank 4
-
02 apr
gereduceerde massa 12
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Optimalisatieprobleem
-
- Berichten: 829
Optimalisatieprobleem
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)
--Vladimir Lenin-- (Владимир Ильич Ульянов)
-
- Berichten: 6.905
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.
-
- Berichten: 4.810
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
-
- Berichten: 6.905
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.
-
- Berichten: 829
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-- (Владимир Ильич Ульянов)
-
- Berichten: 157
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...
-
- Berichten: 829
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-- (Владимир Ильич Ульянов)
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.
-
- Berichten: 691
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.
-
- Pluimdrager
- Berichten: 4.168
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.
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.
-
- Berichten: 6.905
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.
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).
-
- Berichten: 829
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-- (Владимир Ильич Ульянов)
