Algorithmus zum Finden der kleinsten Fläche besetzt mit n Rechtecken

Question

Ich habe eine Reihe von rechteckigen, Ich möchte das kleinste Rechteck finden, die alle kleinen abdecken kann. keine Rotation ist erlaubt.

Mit roher Gewalt will ich meine Antwort finden. Ich versuche es in Java zu codieren. Ich weiß, ich sollte alle Permutationen meiner n Artikel überprüfen und den kleinsten Bereich finden. Und um es einfacher zu machen, habe ich zuerst versucht, möglichst wenig Platz zu finden. Dann habe ich ein zweidimensionales Array mit booleschen Werten verwendet, um zu überprüfen, ob jede Zelle belegt ist oder nicht. Aber ich konnte es nicht herausfinden (codiere es).

Wie überprüft man, ob meine Artikel in meinem begrenzten Bereich platziert werden können? Zum Beispiel habe ich mein erstes Element in x[0][0] bis x[10][1] gefunden und mache alle Zellen in diesem Bereich wahr, aber ich weiß nicht, wie ich meinem Programm mitteilen soll, dass es eine andere Zelle für das nächste Element prüfen soll. Können Sie mir Schritte nennen, die mein Algorithmus implementieren muss?

Answer 1

Ihre Probleme fallen unter die Kategorie der 2D-Behälterverpackung. Es ist ein NP-schweres Problem, so dass es keinen effizienten Polynomzeitalgorithmus gibt, um es zu lösen. (Außer P == NP).

Sie könnten entweder Brute-Force-Algorithmus oder clevere Heuristiken ausprobieren, die Ihnen eine ziemlich optimale Lösung bieten.

Siehe die folgenden Links:
1. How is 2D bin packing achieved programmatically? (Für verschiedene Algorithmen diskutiert)
2. http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu (Für Details der Implementierung)
3. http://www.binpacking.4fan.cz/ (zur Visualisierung verschiedener Heuristiken)

---

Ihre Brute Force-Algorithmus ist sehr ineffizient. Die Permutation, in der die Rechtecke platziert werden können, ist sehr groß und schwer zu finden. Ich schlage vor, dass Sie die oben erwähnten Algorithmen ausprobieren, die einfacher zu implementieren sind als das Finden aller Permutationen.