Verpacken von Rechtecken in einem geradlinigen Polygon

Angesichts einer Reihe von Achsen ausgerichteten Rechtecken (um 90 Grad drehbar) und einem geradlinigen Polygon, möchte ich bestimmen, ob die Rechtecke alle in diesem Polygon und wenn möglich verpackt werden können , finde eine willkürliche Packung.Verpacken von Rechtecken in einem geradlinigen Polygon

Ist das NP hart? Würden irgendwelche Annahmen diese Frage lösbar machen? (z. B. Beschränken des Polygons, um orthogonal konvex zu sein) Jede Art von Referenz wäre nett?

Quelle

2017-03-01 Woofas

Ja, es ist NP schwer, auch wenn das Containerpolygon selbst ein Rechteck ist (siehe [Korf 2003] (http://www.aaai.org/Papers/ICAPS/2003/ICAPS03-029.pdf)). Eine große Vielzahl von ungefähren Algorithmen existieren, google nur "Rechteckverpackung". –

@ n.m. das war nützlich, ich würde aufheben, wenn dein Kommentar in eine Antwort umgewandelt würde, noch hilfreicher, wenn du den Abschnitt über das Drehen der Rechteckverpackung in die Nadelpackung zitierst, um die NP-Härte zu beweisen, danke! – Woofas

Ich verstehe den Beweis selbst nicht ganz, habe nicht viel Zeit, mich durchzuarbeiten. –

Es gibt eine ähnliche Aufgabe auf usaco über das Packen von Rechtecken. Ich habe es nur durch Backtracking gelöst. Here ist die Erklärung der Lösung

Quelle

2017-03-01 11:45:33 oybek

Die Verbindung ist tot. – zwcloud

Ja, es ist NP schwer, auch wenn das Container-Polygon selbst ein Rechteck ist (siehe Korf 2003).

Eine große Vielfalt von ungefähren Algorithmen existiert, google nur "Rechteckverpackung".

Bei einer gegebenen Bin-Packung können wir eine entsprechende Instanz der Rechteckpackung wie folgt erzeugen. Für jede Nummer im Bin-Packing-Problem erzeugen wir ein Rechteck mit Einheitenhöhe, dessen Breite der Wert der Zahl ist. So jede Zahl erzeugt einen Streifen dieser Breite und Einheitshöhe. Wir erzeugen auch ein umschließendes Rechteck, dessen Höhe Anzahl der Bins ist, und deren Breite die Kapazität der Bins ist. Somit entspricht jedes Fach einem horizontalen Streifen des umschließenden Rechtecks. Im resultierenden Rechteckpackungsproblem muss jeder Streifen einer Reihe (Fach) des umschließenden Rechtecks zugewiesen werden, so dass die Summe der Breiten (Nummern) der jeder Zeile (Bin) zugewiesenen Streifen nicht Überschreiten Sie die Breite (Fachkapazität) des umschließenden Rechtecks. Beachten Sie, dass die Streifen ausgerichtet sind und nicht gedreht werden können. Somit entspricht dieses Rechteckpacking Problem dem ursprünglichen bin-packing Problem. Wenn wir irgendein Rechteckpackungsproblem in Polynomialzeit lösen können, dann können wir jedes Bin-Packing-Problem in polynomieller Zeit lösen. Daher ist die Rechteckpackung NP-hart, und da sie auch in NP ist, ist sie NP-vollständig.

Quelle

2017-03-01 11:49:13

Verpacken von Rechtecken in einem geradlinigen Polygon

Antwort

Verwandte Themen