Rechtecke stapeln, um so wenig Platz wie möglich zu beanspruchen

Question

Ich habe ein Programm, das die minimale Fläche berechnet, die durch das Zusammenfügen von Rechtecken genommen wird.

Eingabe: Rechtecke unterschiedlicher Höhe und Breite.
Ausgabe: Ein Rechteck, das alle diese Rechtecke enthält.
Regeln: Man kann die Rechtecke nicht drehen oder rollen und sie können sich nicht überlappen.

Ich verstehe, dass dies verwandt ist oder möglicherweise als ein bin-Verpackungsproblem (NP-hart) definiert ist. Allerdings haben die Algorithmen, die ich für diese gefunden habe, oft eine Grenze für beispielsweise die Breite gesetzt. Ich habe keine solchen Grenzen, das einzige Ziel ist es, die resultierende Fläche so klein wie möglich zu machen.

Gibt es irgendwelche Hinweise darauf, welcher Algorithmus geeignet ist, um eine vernünftige Lösung zu erhalten?

Answer 1

http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf

Offenbar dieses Problem ist schwieriger, als es auf den ersten Blick aussieht. Es ist ein interessanter Algorithmus, da er zuerst eine Lösung rät und dann verbessert. Wenn Sie also nicht auf die optimale Lösung warten möchten, können Sie sie einfach für eine bestimmte Anzahl von Iterationen ausführen, um eine ungefähre Lösung zu erhalten (je länger Sie laufen es, je besser die Annäherung).

Answer 2

Ich würde anfangen durch http://mathworld.wolfram.com Skimmen - sie sind toll für solche Sachen. Zweitens könnte ich mir einen dopey Algorithmus vorstellen, der das längste Feld (in der X-Dimension) auf der Unterseite und dann das höchste (in der Y-Dimension) auf der einen oder der anderen Seite auf die Oberseite legt. Dann stapeln Sie sie weiter in dieser "treppenartigen" Art und Weise nach rechts und nach oben (zum Beispiel gehen Sie nach rechts, bis Sie nicht können, dann gehen Sie nach oben usw.).

Das ist wahrscheinlich nicht ideal, und kann Ihnen sehr schlechte Ergebnisse geben, aber es ist, was zuerst in den Sinn kam.

Answer 3

Ich würde empfehlen, mit einem einfachen gierigen Ansatz zu beginnen, und zu sehen, ob das gut genug für Ihre Bedürfnisse ist. Wenn Ihre Eingabe brav oder klein ist, ist das alles, was Sie brauchen - und die Komplexität steigt schnell an, wenn Sie versuchen, etwas anspruchsvolleres zu tun.

Zum Beispiel: Sortieren Sie die Rechtecke nach Größe, zuerst die größte. Fügen Sie die Rechtecke nacheinander hinzu und probieren Sie jede mögliche Position für das neue Rechteck aus. Wählen Sie die Position aus, die die kleinste Begrenzungsbox ergibt.

Ein anderer gieriger Ansatz wäre, ein Ausgangsrechteck auszuwählen und dann wiederholt das Rechteck hinzuzufügen, was zu der dichtesten Anordnung führt (wobei die Dichte als der Prozentsatz des Bereichs der Begrenzungsbox definiert ist, der gefüllt ist).