Hallo zusammen,
ich suche eine Idee, wie ich mich folgendem Problem der Flächenoptimierung nähern könnte:
Wir haben ein Diagramm A mit mehreren Balken unterschiedlicher Höhe; letztendlich eigentlich nur eine Liste mit ganzzahligen Werten. Das ist die zu füllende Fläche.
Dann gib es das ganze noch mehrfach (hier 3 x) in klein (B, C und D).
Ich möchte jetzt die kleinen Flächen in die Fläche A integrieren (ggf. die Balken stapeln) und zwar so, dass möglichst wenig drüberraussteht - ein Optimierungsproblem also.
Das könnte dann ungefähr so aussehen (die beiden roten Balken oben stehen jetzt etwas drüber raus):
Statt Flächen kann man A-D auch als Tupel beschreiben, z.B. A = (10,12,11,12,15,10...), B = (4,5,3,4) usw. - das hilft vielleicht, einen nichtgraphischen Ansatz zu finden.
Ich habe schon beim Rucksackproblem geschaut, das geht ja in die Richtung, hier kommt als Besonderheit dazu, dass die farbigen Blöcke nicht aufgetrennt werden dürfen und man sehr wohl in einzelnen (oder auch allen, wenn A zu klein für B+C+D ist) Balken über das Ziel hinausschießen darf - das ziel ist einfach, in Summe möglichst wenig über die Balkenhöhen von A hinausgegangen zu sein.
Integrale sind mir auch schon eingefallen, das wäre dann wohl eher die numerische Annäherung an integrale, aber da wüsste ich mathematisch/algorithmisch nicht weiter, wie ich quasi mehrere Integrale in ein großes Integral reinbringen soll.
Was natürlich immer geht, ist brute-force - einfach sämtliche möglichen Kombinationen durchrechnen. Der Aufwand steigt aber exponenziell (erst recht, wenn die zu verteilenden Tupel zahlreich oder A lang werden) und daher ist das eigentlich keine Lösung.
Vielleicht hat ja jemand ein Buzzword, das mich in die richtige Richtung lenken könnte - auch dieses Rad wurde sicher schon mehrfach vorher erfunden...
Vielen Dank im Voraus
Micha
ich suche eine Idee, wie ich mich folgendem Problem der Flächenoptimierung nähern könnte:
Wir haben ein Diagramm A mit mehreren Balken unterschiedlicher Höhe; letztendlich eigentlich nur eine Liste mit ganzzahligen Werten. Das ist die zu füllende Fläche.
Dann gib es das ganze noch mehrfach (hier 3 x) in klein (B, C und D).
Ich möchte jetzt die kleinen Flächen in die Fläche A integrieren (ggf. die Balken stapeln) und zwar so, dass möglichst wenig drüberraussteht - ein Optimierungsproblem also.
Das könnte dann ungefähr so aussehen (die beiden roten Balken oben stehen jetzt etwas drüber raus):
Statt Flächen kann man A-D auch als Tupel beschreiben, z.B. A = (10,12,11,12,15,10...), B = (4,5,3,4) usw. - das hilft vielleicht, einen nichtgraphischen Ansatz zu finden.
Ich habe schon beim Rucksackproblem geschaut, das geht ja in die Richtung, hier kommt als Besonderheit dazu, dass die farbigen Blöcke nicht aufgetrennt werden dürfen und man sehr wohl in einzelnen (oder auch allen, wenn A zu klein für B+C+D ist) Balken über das Ziel hinausschießen darf - das ziel ist einfach, in Summe möglichst wenig über die Balkenhöhen von A hinausgegangen zu sein.
Integrale sind mir auch schon eingefallen, das wäre dann wohl eher die numerische Annäherung an integrale, aber da wüsste ich mathematisch/algorithmisch nicht weiter, wie ich quasi mehrere Integrale in ein großes Integral reinbringen soll.
Was natürlich immer geht, ist brute-force - einfach sämtliche möglichen Kombinationen durchrechnen. Der Aufwand steigt aber exponenziell (erst recht, wenn die zu verteilenden Tupel zahlreich oder A lang werden) und daher ist das eigentlich keine Lösung.
Vielleicht hat ja jemand ein Buzzword, das mich in die richtige Richtung lenken könnte - auch dieses Rad wurde sicher schon mehrfach vorher erfunden...
Vielen Dank im Voraus
Micha
