Blöcke gleichmäßig auf Spalten aufteilen

[melwyn]

Ich hab ein kleines Problem. Ich schilder es erstmal:

Ich habe x Blöcke derselben Breite. Jeder Block hat aber eine beliebige Höhe. Diese Blöcke will ich nun in der gegebenen Reihenfolge auf y Spalten auteilen, und zwar so, das der Platz optimal genutzt wird. Sprich, alle Spalten sollten am Ende so befüllt sein, das die gesamte Höhe der Spalten möglichst niedrig ausfällt.

Beispiel im Bild, damit das besser klar wird:

http://www.inward.de/block.gif

Wie gesagt, es können x Blöcke und y Spalten sein. Wichtig ist, das die Blöcke in der richtigen Reihenfolge bleiben! Der einzigste Algorithmus der mir einfällt, ist jede mögliche Kombination einmal auszuprobieren, und sich bei jeder Möglichkeit die maximale Höhe zu merken. Am Ende gewinnt dann die Möglichkeit, wo das Maximum am niedrigsten ist. Aber selbst das ist garnicht mal so einfach.

Ich hab zwar nen Algorithmus der mir das schon zu ca. 85% relativ geschickt aufteilt, aber ich hätte gern immer die optimale Aufteilung. Vielleicht hat ja jemand eine Idee, wie mans machen könnte.

mfg melwyn

[flashpixx]

Dieses Problem ist das "Rucksackproblem" Rucksackproblem ? Wikipedia und da es NP vollständig ist, lässt es nicht effizient lösen. Ein Lösungsalgorithmus aus der dynamischen Programmierung ist auf Wiki angegeben.

Eine weiterer Lösungsansatz wäre ein Greedy-Algorithmus: Greedy-Algorithmus ? Wikipedia

Aber eine generelle und optimale Lösung wirst Du in endlicher Zeit & mit endlichem Speicherplatz nicht finden können

HTH Phil

[melwyn]

Naja, ganz so wie das Rucksackproblem ist es ja nicht (Glaub ich zumindest). Bei meiner Problematik will ich ja alle Blöcke reinbekommen. Egal ob die dann überstehen oder nicht. Sie sollten halt nicht zu weit überstehen, das in der ersten Spalte eine Höhe von 50 ist, in der zweiten eine Höhe von 3 und in der dritten eine Höhe von 40. Es sollte halt so aufgeteilt werden, das die Höhe optimal genutzt wird. Achja, und in jeder Spalte muss at least ein Block sein!

Um etwas konkreter zu werden. Es handelt sich später natürlich nicht um Blöcke sondern um andere dinge, die der Benutzer möglichst übersichtlich am Bildschirm sehen will, ohne das er 80 mal den Scrollbalken bewegen muss.

Das dumme ist, das mein überlegter (und zugegebenermaßen ziemlich billiger) Algorithmus das ja schon ganz gut hin bekommt. Aber bei manchen Konstellationen sieht man halt sofort, das er den einen Block doch besser in die nächste Spalte hätte schieben können. Vielleicht fällt das beim kunden ja später auf, vlt nicht, vlt ist es ihnen egal, vlt können sie damit auch einfach leben! Wie auch immer... es wurmt mich halt einfach nen bissle, das mir nichts perfektes einfällt und ich auch leider nicht die zeit habe, mich damit stundenlang zu beschäftigen, obwohl es mir große freude bereitet (verrückt).

Ich werde es später irgendwann mal mit einer Art Greedy Algo ausprobieren, der einfach immer im Vorfeld testet, ob der Block für die spätere Bewertung besser in der angegebenen Spalte bleibt, oder in die nächste kommt. Kann nicht die Welt sein, auch vom Rechenaufwand nicht. Denke mal es werden maximal 3-4 Spalten, da der Benutzer sonst nichts gewonnen hätte. Es würde ab 5 Spalten so breit werden, das er anstatt Vertikal dann Horizontal scrollen müsste.

Danke trotzdem für die Hilfe!

Bearbeitet 5. Dezember 2008 von melwyn

[flashpixx]

Naja, ganz so wie das Rucksackproblem ist es ja nicht (Glaub ich zumindest). Bei meiner Problematik will ich ja alle Blöcke reinbekommen. Egal ob die dann überstehen oder nicht. Sie sollten halt nicht zu weit überstehen, das in der ersten Spalte eine Höhe von 50 ist, in der zweiten eine Höhe von 3 und in der dritten eine Höhe von 40. Es sollte halt so aufgeteilt werden, das die Höhe optimal genutzt wird. Achja, und in jeder Spalte muss at least ein Block sein!

Das spielt formal keine Rolle, denn das sind weitere Bedingungen, die das Problem weiter einschränken, bzw Konstanten, die man ignorieren kann.

Es bleibt eine Optimierung und dies ist auf das Rucksackproblem zurückzuführen und damit NP vollständig, ob das nun noch mit einem Faktor multipliziert wird oder nicht, ist irrelevant.

Du wirst, wie Du schon beschrieben hast, nur mit der Möglichkeit alle Lösungsmöglichkeiten durch zu probieren, die beste Lösung finden, Du kannst Dir dann selbst ausrechnen, wenn Du nun eben nicht mehr n Elemente hast, sondern n+1 wie viele Möglichkeiten mehr es nun werden, die Du prüfen musst.

Du wirst keine optimale Lösung finden, sondern allerhöchstens eine gute Näherung. Je nach Problematik kannst Du auch ein Clusterverfahren (VQ Verfahren) einsetzen. Ggf kannst Du auch wenn Du eine Lösung gefunden hast, diese bewerten und verwendest diese dann bei einer ähnlichen Konstellation. Es gibt da verschiedene Möglichkeiten wie man das optimieren kann, aber eine optimale Lösung wirst Du nicht "schnell" finden können. Außer wenn Deine Datenmenge konstant und bekannt ist.

HTH Phil

[SoL_Psycho]

Hmm...

Bin ein kleiner unstudierter Bengel

Ich würde an die Sache folgendermaßen rangehen:

x Blöcke

y Spalten

Ich würde die Blöcke nach der Höhe sortieren und dann mit dem größten Block anfangen und ihn setzen.

Dann setze ich den zweithöchsten daneben und schaue, ob ich noch einen kleineren Block habe, der zusammen mit dem zweithöchsten nicht höher als der höchste Block ist...

Dann gehe ich auf den dritthöchsten, etc. etc.

Wenn man das durchzieht und dann, wenn Spalte Y gefüllt ist, von hinten anfängt und das gleiche Spiel durchzieht (nur von Spalte Y zu Spalte 1), dann würde sich meiner Meinung nach ein gutes Bild ergeben...

Aber wie gesagt: Unstudiert und nicht getestet, war nur nen Bauchgefühl

[flashpixx]

Aber wie gesagt: Unstudiert und nicht getestet, war nur nen Bauchgefühl

ist nicht schlimm: Das Problem besteht ja, aber es gibt eben keine optimale Lösung, sondern nur gute Näherungen. Bei bestimmten Konstellationen der Daten ist eben die approximierte Lösung sehr schlecht.

Man muss eben ein sinnvolles Mittel zwischen Approximation vs. Performance hinbekommen. Im Grunde kann ich nur raten, sich die Daten anzuschauen und ggf. verschiedene Lösungsverfahren wie z.B. Greedy Strategie oder auch Neuronale Netze (wenn man eine Regression oder Klassifikation hat) auszuprobieren und das passende zu verwenden.

Phil

[AndiE]

Hallo,

ich gehe das ganze mal anders an.

gegeben seien 9 Zahlen, die die Höhe der Blöcke darstellen

2, 9, 3, 4, 7, 5, 9, 1, 6

Diese seien auf 6 Spalten aufzuteilen:

1. Frage: Wie groß sind die Blöcke insgesamt

2+9+3+4+7+5+9+1+6=46

2. Wie hoch ist jede Spalte durchschnittlich:

46/6=7,66

Wieviel Blöcke entfallen auf eine Spalte:

9/6=1,5

3. 1. Lösung

a) 2+9=9

3+4=7

c) 7

d) 5

e) 9

f) 1+6=7

Ich meine die Kriterien, ob ein Stein hinzukommt, oder nicht liegen bei halber und anderthalfacher Füllhöhe.

Ist die Füllhöhe mit dem neuen Stein kleiner als 12, dann noch ein Stein. Sonst nächste Spalte.

MfG

Andre'

[LadyPreis]

3. 1. Lösung

a) 2+9=9

3+4=7

c) 7

d) 5

e) 9

f) 1+6=7

Kommt aber auch nicht ganz hin! erstmal kommt bei "a" nicht 9 sondern 11 raus.

Damit hast du eine Blockverteilung von 11,7,7,5,9,7

Das der erste Block hier raus sticht, muss ich wahrscheinlich nicht sagen. Besser wäre es, wenn die 2 aus dem a-Teil in d landen würden. Dann sähre das ganz gut aus.

Aber generell ein guter Ansatz. Darauf könnte man aufbauen

Gruß

Die Lady

[SoL_Psycho]

gegeben seien 9 Zahlen, die die Höhe der Blöcke darstellen

2, 9, 3, 4, 7, 5, 9, 1, 6

Diese seien auf 6 Spalten aufzuteilen:

Meine Lösung wäre dann:

Sortieren: 9 9 7 6 5 4 3 2 1

Spalte 1: 9

Spalte 2: 9 ---> Spalte 2 >= Spalte 1 ---> Weiter in Spalte 3

Spalte 3: 7 ---> Spalte 2 < Spalte 1 ---> Über die restlichen Blöcke von groß nach klein iterieren: 7 + 6 > Spalte 1 ---> weiter iterieren ---> 7 + 5 > Spalte 1 ---> ... ---> 7 + 2 <= Spalte 1 ---> Weiter in Spalte 4

Spalte 4: 6 ---> Spalte 3 < Spalte 1 ---> Über die restlichen Blöcke von groß nach klein iterieren: 6 + 5 > Spalte 1 ---> weiter iterieren ---> 6 + 4 > Spalte 1 ---> 6 + 3 <= Spalte 1 ---> Weiter in Spalte 5

Spalte 5: 5 ---> Spalte 5 < Spalte 1 ---> Über die restlichen Blöcke von groß nach klein iterieren: 5 + 4 <= Spalte 1 ---> Weiter in Spalte 6

Spalte 6: 1

Also:

1: 9

2: 9

3: 7+2 = 9

4: 6+3 = 9

5: 5+4 = 9

6: 1

[AndiE]

Danke für die Korrektur.

Aber es gibt noch diese "doofe" Nebenbedingung:

Wichtig ist, das die Blöcke in der richtigen Reihenfolge bleiben!

Das macht das so problematisch

Viele Grüße

Andre'

[SoL_Psycho]

Tatsache! Mea culpa