Behälterverpackungsproblem mit fester Behältergröße
Ich studiere Bin Packing Problem für meine Diplomarbeit und treffe diese Definition der Entscheidung verson des Problems in dem Buch "Computers and Intractability" von Michael R. Garey und David S. Johnson:
INSTANZ: Endliche Menge $U$ von Gegenständen, eine Größe $s(u) \in Z$ für jede $u \in U$, eine positive Ganzzahl-Bin-Kapazität $B$und eine positive ganze Zahl $K$.
FRAGE: Gibt es eine Partition von $U$ in disjunkte Mengen $U_1, U_2, ..., U_k$ so dass die Summe der Größen der Elemente in jedem $U_i$ ist $B$ oder weniger.
Und es gibt einen merkwürdigen Kommentar zu seiner Lösung in der Polynomzeit, nämlich "Lösbar in der Polynomzeit für jede feste $B$ durch erschöpfende Suche. "
Jetzt ist meine Frage, wie es möglich ist, im Internet zu suchen. Ich habe nichts als diese Frage gefunden: NP-Härte des Behälterverpackungsproblems für feste Behältergröße, aber die Antwort überzeugt mich nicht, es scheint falsch, oder vielleicht ziehe ich einfach an verstehe es nicht Kannst du mir dabei helfen?
Antworten
Mit einer festen Behältergröße haben Sie auch eine feste Anzahl von Möglichkeiten, einen Behälter (teilweise) zu füllen. Angenommen, es gibt$p$ Möglichkeiten, das zu tun.
Wenn Sie jeden der lösen $k$ Behälter getrennt, würden Sie bekommen $p$ Möglichkeiten für jeden Behälter und dann $p^k$Möglichkeiten insgesamt. Dies ist exponentiell und nicht das, was wir möchten. Beachten Sie, dass viele dieser Möglichkeiten nicht mit den tatsächlich verfügbaren Artikelgrößen übereinstimmen. Es handelt sich also lediglich um eine Obergrenze.
Anstatt jedem Bin eine Partition zuzuweisen, können Sie das Gegenteil tun - jeder Partition eine bestimmte Anzahl von Bins (möglicherweise Null) zuweisen. Sie haben dann$(k+1)^p$mögliche Wege dieser Zuordnung. Dies hat einen festen Exponenten, ist also in der Anzahl der Bins polynomisch. Das Grad$p$ dieses Polynoms kann sehr groß sein, und dies ist auch eine Obergrenze, da die meisten dieser Zuweisungen die falsche Gesamtzahl von Bins haben, aber alles, was keine Rolle spielt - es reicht aus, um zu zeigen, dass es ein Polynom ist.
Angenommen, die Behältergröße ist $3$. Es sind nur$6$ Mögliche Möglichkeiten, einen Behälter teilweise oder vollständig zu füllen: $1$, $1+1$, $1+1+1$, $2$, $2+1$, $3$. Lassen$a,b,c,d,e,f$Seien Sie Variablen, die angeben, wie viele Behälter für jede dieser Möglichkeiten zum Befüllen vorhanden sind. Jede Variable muss einen ganzzahligen Wert von haben$0$ zu $k$inklusive. Es gibt also nicht mehr als$(k+1)^6$Möglichkeiten zu überprüfen. In der Tat gibt es weit weniger, da wir auch haben$a+b+c+d+e+f=k$. Angenommen, wir möchten prüfen, ob$a=b=c=d=0$, $e=f=4$ist eine gültige Müllverpackung. Wir haben vier Behälter, die eine Größe enthalten$2$ und eine Größe $1$ Artikel und vier Behälter mit einer Größe $3$Artikel. Wenn Ihr Inventar$U$Enthält vier Artikel jeder Größe, haben Sie eine gültige Verpackung. Jedoch viele Behälter der Größe$3$ Sie haben, gibt es nur $6$ Variablen, die Sie bestimmen müssen, und die in der Anzahl der Bins polynomisch sind.