Springen naar inhoud

Optimalisatieprobleem


  • Log in om te kunnen reageren

#1

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 11 maart 2009 - 23:55

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
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 12 maart 2009 - 19:04

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.

#3

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 12 maart 2009 - 19:16

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 ;)

#4

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 12 maart 2009 - 19:27

Ahzo. Echt helpen kan ik dan ook niet. Mogelijk vind je hier iets: http://en.wikipedia....t_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.

#5

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 13 maart 2009 - 00:33

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-- (Владимир Ильич Ульянов)

#6

Chip

    Chip


  • >100 berichten
  • 157 berichten
  • Ervaren gebruiker

Geplaatst op 13 maart 2009 - 00:49

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...

Veranderd door Wouser, 13 maart 2009 - 00:50


#7

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 13 maart 2009 - 01:05

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-- (Владимир Ильич Ульянов)

#8

*_gast_PeterPan_*

  • Gast

Geplaatst op 13 maart 2009 - 12:56

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....ki/Backtracking

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

#9

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 13 maart 2009 - 13:47

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...
Een computertaal is voor mensen, niet voor de computer.

#10

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 13 maart 2009 - 17:56

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.
Hydrogen economy is a Hype.

#11

*_gast_PeterPan_*

  • Gast

Geplaatst op 13 maart 2009 - 18:31

Mooi. Daar ken ik het dus van. Het is eenvoudig aan te passen voor 2D.
Het kan natuurlijk ook altijd met exhaustive search.

#12

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 13 maart 2009 - 18:35

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?
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.

#13

*_gast_PeterPan_*

  • Gast

Geplaatst op 15 maart 2009 - 10:58

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).

#14

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 15 maart 2009 - 23:59

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-- (Владимир Ильич Ульянов)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures