Berechnung effizienter Anordnung von rechteckigen Objekten

5 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Gibt es hierfür einen mathematischen oder algorithmischen Ansatz ?

Klar, alles Durchprobieren. Das kann alles dauern. Ich unterstelle mal, das deine Grundfälche am Ende auch wieder ein Rechteck seinen soll, d.h. das du die Größe des umfassenden Rechtecks minimieren willst.

Was das Finden des exakten Optimums betrifft, sieht das nach einen NP vollständigen Problem aus. Ich denke, man kann das auf das Multiprozessorschedulingproblem zurückführen.

Dazu nehme man ein ganz großes Rechteck, das die Zahl der Prozessoren definiert, und die Jobs bildet man auf kleine Rechtecke ab. Diese macht man sehr lang (wobei alle kleinen Rechtecke die gleiche Länge l haben) und definiert über die kleine Dicke die Job Dauer. Sie müssen halt lang genug sein, das man sie nicht quer stellen kann, d.h. die Länger ist größer als die Summe aller Breiten. Das Große Rechteck muß Prozessorzahl mal l lang sein und hinreichend Breit (Summe aller übrigen Längen und Breiten).

Was bedeutet das aber nun ?

Es ist zwar nicht bewiesen, das man NP-vollständige Problem nicht in polynomialer, d.h. vernünftiger Zeit lösen kann, aber wenn du dein Problem gelöst hast, kann man damit auch eine Reihe andere Probleme sehr elegant lösen. z.B. kann man dann damit praktisch sämtlichen modernen Verschlüssungesverfahren knacken, (Transkationssysteme der Banken, e-pass signatur uws.)

Folglich mußt du approximativen Algorithmen verwenden. D.h. der Algorithmus wird das Optimum nicht immer finden. Eine Möglichkeit wäre ein Greedy algorithmus, d.h. du beginnst mit dem Größten Rechteck und versuchts immer das nächstkleinere so zu platzieren, das es das aktuelle Optimum ist.

Besten Dank für deine ausführliche Antwort. Ich denke von hier aus werde ich so weit als möglich eigenständig weiter kommen :)

Beste Grüße,

Dominik

0

Ich habe zwar keine Lösung für dich, aber einen Denkanstoß:
Dies scheint mir eine Variante des Rucksackproblems zu sein. Da dieses NP-vollständig ist, und außerdem P <> NP-vollständig vermutet wird, gibt es wohl keinen polynomialen Algorithmus zur Lösung des Problems. Jede Lösung hat demnach exponentielle oder zumindest subexponentielle Laufzeit.
p.s. Die Bruteforcemethode ist natürlich das Durchprobieren aller Permutationen, dies erfordert aber selbstverständlich auch eine exponentielle Laufzeit, es gibt mit Sicherheit bessere Algorithmen.

Hallo lks,

ich danke dir für deine Antwort. Um genau zu sein hatte ich soetwas befürchtet wobei eine Abbildung auf 3d-Raum noch komplexer und noch mehr varianten aufwerfen würde als nur in der zweiten Dimension. Doch bei 100 Objekten mit je unterschiedlicher Seitenlänge ist dann so gesehen auch zappenduster.

Das "Rucksackproblem" sagt mir grob was - ich werde mal schauen in wie weit ich mit dem Begriff weiter komme. Auf jeden Fall danke ich dir schon einmal für deine Antwort ;)

Grüße,

Dominik

0

was für eine form soll deine grundfläche denn haben? auch rechteckig nehm ich an? weil sonst, wenn die grundfläche beliebige form hätte, wäre sie bei jeder anordnung gleich groß...

Die Grundform soll ebenfalls rechteckig sein, das ist korrekt. Die Frage ist halt wie ich berechnen kann, welches Objekt an welche Stelle kommt sodass eine möglichst geringe Grundfläche benötigt wird. Überlagerungen der Objekte sind nicht möglich allerdings können alle Objekte unterschiedliche Maße haben.

Danke auf jeden Fall schon mal für deine Reaktion.

Beste Grüße,

Dominik

0
@Andersgeartet

hm also auf anhieb fällt mir nix konkretes ein, is gar nicht so leicht das problem...

aber am besten geh ich immer an sowas ran, dass ich es mir erst mit wenigen sachen überlege, also in deinem fall mit 3 objekten oder so... wenn das geht, gehts iwie auch mit mehreren, aber mir fällt nichts ein wie es geht, wenn sich was ändert sag ich bescheid;-)

0
@thomas1908

Danke für deine Rückmeldung Thomas.

Bin selber auch die ganze Zeit am kreuz und quer überlegen gewesen doch außer einer Multidimensionalen funktion nach dem Try'n'error Prinzip fällt mir nichts ein - zumal die Anzahl der Durchläufe um die Anzahl der Objekte potenziert wird.

0

So eine ähnliche Aufgabe gab es in VHS Programmierungskurs.

Man kann mit der Programmierung ein bestehendes Chaos vorausberechnen zumindest beim Spielprogrammierung.

Spielt man im Internet als Team ein Strategiespiel berechnet ein PC immer die Positionen von Figuren, was den Hauptspieler rechtzeitig mitgeteilt wird, teilweise schon vor erscheinen der Gegner.

Einen Code finde ich leider nicht mehr in den Unterlagen.

Was möchtest Du wissen?