Rechteck mit Einschränkungen Verpackung

Question

Ich möchte eine Reihe von Rechtecken (Beispiel) packen:

Damit die Gesamthöhe mit der Einschränkung, so gering wie möglich ist, dass die Rechtecken in der am Ende müssen die gleiche Spalte, in der sie begonnen haben. Die Rechtecke dürfen sich gegenseitig "bewegen", um den Endzustand zu erreichen, solange sie sich am Ende nicht schneiden.

Unser aktueller Algorithmus besteht darin, die Rechtecke von der größten Höhe bis zur kleinsten Höhe zu verarbeiten und sie an der niedrigsten y-Position zu platzieren, die verfügbar ist. Gibt es einen optimalen Algorithmus?

EDIT: Ich brauche nicht unbedingt die optimale Lösung, jeder Algorithmus, der eine bessere Lösung als die aktuelle erzeugt, ist interessant. Die Anzahl der Rechtecke beträgt 50.

Answer 1

Angenommen, Sie haben N Rechtecke. Für jedes Rechteck i, lassen Sie [a_i, b_i] die horizontale Spannweite sein, und lassen Sie h_i die Höhe sein.

Ihr Lösungsbereich sieht wie y_i, i = 1, ..., N aus, wobei die vertikale Spannweite des Rechtecks ​​i ist.

Ohne Beschränkung der Allgemeinheit können wir y_i >= 0 beschränken. Wir wollen dann die Zielfunktion max{y_i + h_i | i} minimieren.

Die Einschränkungen, die Sie für nicht überlappende Rechtecken haben, sind:

y_i + h_i <= y_j 
    OR 
y_j + h_j <= y_i 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

aus Herauszufinden, die [a_i, b_i] sie schneiden ist einfach, so für die herauszufinden Paare von Rechtecken, diese Beschränkungen bilden einfach sein sollten.

Um von der oder in unserem Zwang loszuwerden, können wir binäre Dummy-Variablen z_k für jede Einschränkung k und ein „Big M“ M, die ausreichend groß ist und neu schreiben erstellen:

y_i + h_i <= y_j + (z_k)M 
y_j + h_j <= y_i + (1-z_k)M 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

Wir können eine Einführung Dummy-Variable H und fügen Sie die Einschränkungen y_i + h_i <= H hinzu, so dass wir die Zielfunktion als Minimierung H umschreiben können.

Das resultierende Optimierungsproblem ist:

minimize H 
with respect to: y_i, z_k, H 
subject to: 

(1) y_i + h_i <= y_j + (z_k)M for all i != j such that [a_i, b_i] 
    y_j + h_j <= y_i + (1-z_k)M and [a_j, b_j] intersect 

(2) y_i + h_i <= H    for all i 

(3) y_i >= 0      for all i 

(4) z_k in {0, 1}    for all constraints of type (1) k 

Dies ist ein mixed-integer linear optimization problem ist. Es gibt allgemeine Löser für diese Art von Problemen, die Sie direkt anwenden können.

Typischerweise werden sie Tricks wie eine Lockerung der binären Bedingung auf z_k der Einschränkung durchführen, die in [0,1] während des Algorithmus sein z_k, die diese in eine linear programming problem dreht, die sehr effizient gelöst werden können.

Ich würde nicht empfehlen, versuchen, diese Löser neu zu erfinden.

Answer 2

Da Rechtecke nur vertikal verschoben werden können, scheint es nur zwei Lösungen zu geben: Alle Rechtecke so weit wie möglich nach oben verschieben, bis eine Kollision auftritt, oder alle nach unten bewegen bis eine Kollision auftritt. Ich habe den schleichenden Verdacht, dass diese Lösungen gleichwertig sein werden *. Ich kann nicht denken, dass es eine viel ausgeklügeltere Vorstellung von Packen gibt, wenn man auf eine Dimension beschränkt ist. Vielleicht vermisse ich etwas?

* Wenn ich Ihre Einschränkung korrekt verstanden habe, wird die minimale Höhe immer die Anzahl der gefüllten Zellen in der Spalte mit der größten Anzahl gefüllter Zellen sein. Dies ist unabhängig davon, ob die Übersetzung nach oben oder nach unten angewendet wird.

Answer 3

Meiner bescheidenen Meinung nach besteht der erste Schritt darin, für jede Spalte die geringste erforderliche Höhe zu berechnen. Wenn Sie Ihr Bild als Beispiel verwenden, benötigt die erste Spalte mindestens eine Höhe von 10, die von den roten, grünen und kleinen blauen Rechtecken unterstützt wird. Dies wird leicht gemacht, indem jedes gegebene Rechteck durchlaufen wird und den Spalten, die es belegt, ihre entsprechende Höhe hinzugefügt wird. Auf diese Weise wird die maximale Anzahl in allen "Spaltenhöhen" gefunden, die ich die "Säule" nenne. In Ihrem Bild ist die "Säule" in Spalte 8:10 mit Höhe von 14, von Rechteck 1,2,4,6 (von unten nach oben nummeriert) beigetragen. Dies bedeutet, dass die Mindesthöhe der Verpackung mindestens die Höhe der "Säule" beträgt, da die "Säulen" -Säulen fest gefüllt sind und nicht weiter reduziert werden können. Und diese vier Stapelformen, wie Bild Rechteck up: (die nicht-säulen Rechteck nicht gezeigt)

Dann wird die Säule teilt das Bild in zwei Teile, einen in der Region auf der linken Seite der Säule ist, und eine andere auf der anderen Seite Seite. Auch die "nicht-säulenförmigen" Rechtecke (R3, 5, 7, 8) sind getrennt zu den beiden Regionen angeordnet. R3, R7 auf der LHS und R5, R8 auf der RHS.

Betrachten Sie nun zuerst den linken Seitenteil. I neu geordnet die Säule Rechtecken, wie sie in der Abbildung (Abb.3) gezeigt:

Mit der neu angeordneten Säule Rechteck Stapelreihenfolge, obwohl ich keinen starren Beweis habe, ist es sehr gut möglich, dass, egal was die Formen und die Anzahl der Rechtecke auf der linken Seite der Säule, alle gegebenen Rechtecke können in den leeren Raum auf der linken Seite passen (die Einschränkung hier ist, dass diese Rechtecke keine höhere solide Säule bilden können, sonst der Schritt Ich hätte es bereits entdeckt und nutze es als eigentliche Säule. Diese Anordnung gibt dem leeren Raum auf LHS die beste "Raumkonsistenz", was bedeutet, dass der leere Raum, der von jedem Säulenrechteck erzeugt wird, in aufsteigender Reihenfolge von unten nach oben gestapelt ist. Diese "Konsistenz" lässt die leeren Räume, die von jedem Säulenrechteck erzeugt werden, "zusammenwirken" und dann Retingles enthalten, die höher sind als jeder einzelne leere Raum, der durch ein einzelnes Säulenrechteck erzeugt wird. Zum Beispiel wird das grüne Rechteck im nächsten Bild unter Verwendung des leeren Raums, der durch das blaue und violette Rechteck zusammen erzeugt wird, angepasst.

Unter der Annahme, dass die obigen Aussagen zutreffen, werden die auf der LHS positionierten Rechtecke niemals einen höheren Stapel als die Säule bilden. Wenn diese Re-Tangle jedoch eine Kooperation zwischen den leeren Räumen erfordert, um auf die LHS zu passen, dann begrenzen sie tatsächlich die Auslagerungsmöglichkeit für die Säulenrechtecke. Verwenden Sie Abb.3 als Beispiel, das grüne Rechteck erfordert, dass Purpur und Blau Nachbarn sind, um zu passen. Um jedoch die bestmögliche Raumkonsistenz auf RHS zu erhalten, muss das Magenta zwischen Lila und Blau wechseln.Dies bedeutet, dass das Grün auf LHS es unmöglich macht, die beste Konsistenz für RHS zu erhalten, und folglich ermöglicht, dass auf RHS positionierte Rechtecke nicht in den leeren Raum passen und einen Stapel mit Löchern verursachen können und die von der Säule festgelegte Höhe überschreiten. Entschuldigung, dass ich einen solchen Fall hier nicht ausdenken kann, aber es macht einen Unterschied.

Zusammenfassend:
Schritt 1 ist die Säule zu finden, eine einfache Antwort kann hier gefunden werden, wenn jedes gegebene Rechteck in der Säule beteiligt ist - die Höhe der Säule ist die minimale Packungshöhe.

Schritt 2 ist, beide Seite auf die Säule zu untersuchen.
Fall a: Wenn auf einer Seite kein freies Rechteck positioniert ist, kann die andere Seite einfach mit der Methode der "besten Konsistenz" gefüllt werden, und die resultierende minimale Packungshöhe ist wiederum die Säulenhöhe.

Fall b: Wenn eine Seite keine freie Platzkonsistenz benötigt, kann diese Seite gefüllt werden und die andere Seite kann immer noch "die beste Konsistenz" verwenden. Beispiel: (Ihr Originalbild)

In diesem Fall wird der für die Anpassung in R3 erforderliche freie Speicherplatz ausschließlich von R6 und derselbe für R7 und R2 erstellt. Wenn also die Stapelreihenfolge von R6 und R2 mit einem anderen Säulenrechteck vertauscht wird, wird R3, R7 ungeeignet, wenn R3, R7 dem Austausch folgen.

Dann RHS, ohne die Säulenhöhe mit den RHS positionierten Rechtecken gefüllt werden kann: die in einem „best Konsistenz“ Fall für RHS führen kann.
Diese Nichtkonsistenzanforderung kann durch Vergleichen der Höhe des freien Rechtecks, in das es passen soll, und der Höhe des Säulenrechtecks, das den freien Platz dafür schafft, identifiziert werden. Wenn die Höhe des freien Rechtecks ​​nicht größer ist als die des anderen, ist kein zweites Rechteck der Säule erforderlich, was bedeutet, dass keine freie Raumkonsistenz erforderlich ist.

Fall c: Beide Seiten benötigen freie Speicherplatzkonsistenz. Hier treten Probleme auf. Nehmen Sie fig.3 als Beispiel. Das Grün in Abb.3 hatte die Kombination von Violett und Blau. Dies bedeutet, dass das Grün, Violett und Blau als Ganzes betrachtet wird, um die Stapelreihenfolge mit anderen Säulenrechtecken zu tauschen, um das freie Rechteck des LHS zu erhalten. Und innerhalb dieses Ganzen können sich Blau und Violett auch austauschen.
Wenn die RHS nicht passen kann, was zu einer Packungshöhe führt, die größer ist als die Säulenhöhe, dann ist es erforderlich, den zweiten Schritt zu wiederholen, aber zuerst die RHS und danach LHS zu montieren. Dann wird das Ergebnis der verglichenen niedrigeren Packungshöhe als das Endergebnis genommen. Die Logik für diesen Fall ist unklar, sehr gut möglich, hat eine bessere Alternative.

Ich weiß, das sollte nicht wirklich als eine richtige Lösung, sondern eher zufällige und lose Gedanken genannt werden, aber es wird offensichtlich nicht in die Kommentare passen. Verzeih mir meine plumpe Erklärung und schlechte Bildverarbeitung. Hoffe das hilft.