Quadrate in Rechteck packen

[member42]

Hallo,
Ich habe z.B 7 Quadrate mit den Seitenlängen 1*1, 2*2...7*7 und möchte diese in einem Rechteck mit Größe 10*12 anordnen(ohne überlappen). Was wäre dann eine gute Vorgehensweise? Um alle möglichen Konfigurationen durchzuprobieren sind es, denke ich zuviele.

Danke im Vorraus.

 

[httpdigest]

Das ist ein Spezialfall von "2D Bin Packing", welches NP-hard ist. Um die optimale Konfiguration für die Anordnung der Rechtecke zu finden, gibt es mit sehr hoher Wahrscheinlichkeit keine bessere Lösung als einfach alles auszuprobieren.
Es gibt natürlich Algorithmen, die mit Hilfe von Annahmen und Heuristiken eine gute Lösung finden können. Ein Anfang wäre zum Beispiel erstmal, die Rechtecke absteigend nach ihrer Größe zu sortieren und dann die größten Rechtecke zuerst einzuordnen und dann mit Backtracking wieder zurückzugehen und eine andere Position zu finden, falls es insgesamt nicht passt.

 

[fhoffmann]

Als allererstes würde ich überprüfen, ob die 7 Quadrate überhaupt in das Rechteck passen:

public class Test {
   public static void main(String[] args) {
       int sum = 0;
       for(int i = 1; i <= 7; i++) {
           sum += i*i;
       }
       System.out.println(sum);
   }
}

 

[Xyz1]

nach ihrer Größe zu sortieren und

...und Iterationen so
links, rechts,
rechts, links,
links, rechts, usw.

bei mehr Rechtecken die Optimalität verschmerzbar zugunsten der Zeit

 

[member42]

Danke, jetzt weiß ich wo nach ich so googlen kann.

 

[Xyz1]

suche aber nicht nach NP-Schwere das trübt nur die Stimmung

 

[mihe7]

Zu Deiner Ausgangsfrage gibt es nur eine Antwort (s. @fhoffmann): es gibt keine Lösung, weil Deine Quadrate eine Fläche von 140 FE haben, Du aber nur 120 FE zur Verfügung hast.

Jetzt hat @httpdigest die Optimierung ins Spiel gebracht. Hier wäre interessant, zu erfahren, wonach den optimiert werden soll.

Was die Zahl der Kombinationen betrifft, hilft es, ein wenig zu rechnen. Du kannst, rein auf die Gesamtfläche bezogen, max 6 Quadrate verwenden. Es gibt 7 Möglichkeiten, 6 Quadrate aus 7 auszuwählen. Wir können davon ausgehen, dass das größte Quadrat zuerst zum Rechteck hinzugefügt wird. Für die restlichen 5 müssen max. alle erdenklichen Einfüge-Reihenfolgen (Permutationen) betrachtet werden. Das sind 5! = 120 Möglichkeiten. Insgesamt gibt es bei 6 Quadraten also 7 * 120 = 840 Kombinationen.

Das kann man jetzt für 5 aus 7, 4 aus 7 usw. weiterrechnen:

k | k aus 7 | Permutationen | Kombinationen
6 |       7 |           120 |           840
5 |      21 |            24 |           504
4 |      35 |             6 |           210
3 |      35 |             2 |            70
2 |      21 |             1 |            21
1 |       7 |             - |             7
Summe                                  1616

Wenn ich mich nicht irgendwo vertan habe, dann wäre es im konkreten(!) Fall also überhaupt kein Problem, alles durchzuprobieren.

Geht es z. B. nur darum, die größtmögliche Fläche zu bedecken, lässt sich außerdem der Suchraum hervorragend einschränken:

1. sobald eine valide Konfiguration gefunden wurde brauchen die restlichen Permutationen nicht weiter untersucht werden und
2. alle anderen Möglichkeiten mit kleinerer Fläche können sofort ausgeschlossen werden.

 

[Xyz1]

Moin @mihe7 !

Dein dingsbums da ist nicht falsch.

Es ändert aber nüschts an der np-schwere des Problems.

Wenn Du zB nicht 7 sondern 50 dinge in deinen Kofferaum packen willst, dann gibt es schon mehr Kombinationen.

 

[Xyz1]

2 Minuten Über der Bearbeitungszeit
https://www.wolframalpha.com/input/?i=derangements+of+50+elements
http://www.wolframalpha.com/input/?...Prefs"+->+{"MathWorld",+"Bin-PackingProblem"}
http://www.wolframalpha.com/input/?...in-packing+problem"}+->+{"FamousMathProblem"}
Und der Status ist noch: proved NP-complete

 

[mihe7]

Es ändert aber nüschts an der np-schwere des Problems.

Natürlich nicht, darum habe ich ausdrücklich das "konkret" betont.

Wenn Du zB nicht 7 sondern 50 dinge in deinen Kofferaum packen willst, dann gibt es schon mehr Kombinationen.

Wenn alle 50 reinpassen, ist es trivial

 

[JCODA]

Wenn ich mich nicht irgendwo vertan habe, dann wäre es im konkreten(!) Fall also überhaupt kein Problem, alles durchzuprobieren.

Deine Rechnung stimmt, wenn es nur um die Auswahl und die Reihenfolge des Einfügens geht. Allerdings besteht jede Einfügeoperation ja erneut aus vielen Möglichkeiten. Ich denke speziell hier kommen die Großen Faktoren hinzu. (Die auch etwas schwieriger zu berechnen sind...)

 

[mihe7]

Allerdings besteht jede Einfügeoperation ja erneut aus vielen Möglichkeiten.

Es war fast klar, dass ich irgendwas übersehen habe :-(

 

[member42]

Mein Beispiel war etwas schlecht gewählt, weil ich mich mit den Quadraten verrechnet habeMein Beispiel war etwas schlecht gewählt, weil ich mich mit den Quadraten verrechnet habe. Ich meinte sowas wie ein 10*15 Rechteck.
Jedenfalls Danke für die Denkanstöße.

 

[Xyz1]

Allerdings besteht jede Einfügeoperation ja erneut aus vielen Möglichkeiten.

2D ... es gibt doch nur ein Möglichkeit ein dingsbums (als nächstes) zu platzieren, ohne das eine Lücke entstünde....
der verbleibende Platz kann dann berechnet werden

Wenn alle 50 reinpassen, ist es trivial

ich bezweifle ein wenig, dass alle 50 passen würd.
Du würdst wahrscheinlich einfach alles ungeordnet in deinen Kofferraum schmeißen.

 

[JCODA]

Mal die Idee von @httpdigest in Python implementiert. Grauenhafter Code. Funktioniert aber:

import numpy as np

def pprint(field):
    print(*["".join([str(int(g)) for g in row]) for row in field],sep="\n")


def pack(elements, size, field = None):
    if field is None:
        field = np.zeros(size)
    if not elements:
        pprint(field)
        return True
  
    c_x, c_y, label = elements[0]
    avail = field == 0
  
    for x in range(0,size[0]-c_x+1):
        for y in range(0,size[1]-c_y+1):          
            if np.all(avail[x:x+c_x,y:y+c_y]):
                field[x:x+c_x,y:y+c_y] = label
                result = pack(elements[1:],size, field)       
                if result:
                    return True      
                field[x:x+c_x,y:y+c_y] = 0
                  

# elements are a list of triple tuples which contain an width, height and an integer label
                  
elems = [(i,i,i) for i in range(7,0,-1)]
print(elems)
result = pack(elems,(11,14))
if not result:
    print("There are no possible tilings :(")

liefert für die Quadrate von 1 bis 7 auf einem Rechteck von 11x14 folgende Ausgabe:
77777776666661
77777776666660
77777776666660
77777776666660
77777776666660
77777776666660
77777775555522
44443335555522
44443335555500
44443335555500
44440005555500

man kann diesen Code auch unter folgendem Link ausführen:
https://repl.it/@game4you/RectangularPacking

 

[mihe7]

2D ... es gibt doch nur ein Möglichkeit ein dingsbums (als nächstes) zu platzieren, ohne das eine Lücke entstünde....

Ja, ja, reitet ruhig darauf rum

 

[Xyz1]

reitet ruhig darauf rum

sorry, ich wollte dich nicht "bloßstellen"
habe nur laut gedacht

 

[mihe7]

sorry, ich wollte dich nicht "bloßstellen"

Das war auch nur ein Spaß. Den Gedanken mit der "eindeutigen" Einfügerei hatte ich auch, allerdings nicht bedacht, dass durch die unterschiedlichen Höhen...