Ist es NP-schwer, Behälter mit minimalen Bewegungen zu füllen?

Es gibt Behälter und Arten von Bällen. Der te Behälter hat die Bezeichnungen für , dies ist die erwartete Anzahl von Bällen des Typs .$n$$m$$i$$a_{i,j}$$1\leq j\leq m$$j$

Sie beginnen mit Bällen vom Typ . Jeder Ball vom Typ hat das Gewicht und möchte die Bälle so in die Behälter legen, dass der Behälter das Gewicht . Eine Verteilung der Bälle so, dass die vorherige Bedingung erfüllt ist, wird als praktikable Lösung bezeichnet.$b_j$$j$$j$$w_j$$i$$c_i$

Betrachten Sie eine praktikable Lösung mit $x_{i,j}$ Kugeln vom Typ $j$ in bin $i$ , dann sind die Kosten $\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$. Wir wollen eine kostengünstige Lösung finden.

Dieses Problem ist eindeutig NP-schwer, wenn es keine Einschränkung für $\{w_j\}$ . Das Teilmengenproblem reduziert sich auf das Vorhandensein einer realisierbaren Lösung.

Wenn wir jedoch die Bedingung hinzufügen, dass $w_j$$w_{j+1}$ für jedes $j$ dividiert , funktioniert die Teilmengen-Summenreduktion nicht mehr, sodass nicht klar ist, ob das resultierende Problem NP-hart bleibt. Die Prüfung auf das Vorhandensein einer realisierbaren Lösung nimmt nur $O(n\,m)$ Zeit in Anspruch (am Ende der Frage angefügt), aber dies gibt uns nicht die realisierbare Lösung mit minimalen Kosten.

Das Problem hat eine äquivalente ganzzahlige Programmformulierung. Gegeben für : $a_{i,j},c_i,b_j,w_j$$1\leq i\leq n,1\leq j\leq m$

$$\begin{align*} \text{Minimize:} & \sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}| \\ \text{subject to:} & \sum_{j=1}^m x_{i,j}w_j = c_i \text{ for all } 1\leq i\leq n\\ & \sum_{i=1}^n x_{i,j} \leq b_j \text{ for all } 1\leq j \leq m\\ & x_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\ \end{align*}$$

Meine Frage ist,

Ist das obige Ganzzahlprogramm NP-hart, wenn für alle dividiert ?$w_j$$w_{j+1}$$j$

Ein Algorithmus , um zu entscheiden , ob es eine realisierbare Lösung ist in Zeit$O(n\,m)$ :

Definiere und . Sei der Rest, wenn durch geteilt wird .$w_{m+1}=w_m(\max_{j} c_j + 1)$$d_j = w_{j+1}/w_j$$a\%b$$a$$b$

1. Wenn es ein , das nicht durch teilbar ist , geben Sie "no feasible solution" zurück. (Die Invariante dividiert wird immer in der folgenden Schleife beibehalten)$c_i$$w_1$$c_i$$w_j$

2. für von bis :$j$$1$$m$

   1. $k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$ . (das Minimum an Gewichtsbällen erforderlich)$w_j$
   2. Wenn , wird "keine realisierbare Lösung" zurückgegeben.$b_j<k$
   3. $c_i \gets c_i - ((c_i/w_j)\% d_j)$ für alle . (Entfernen Sie die Mindestanzahl der erforderlichen Gewichtsbälle )$i$$w_j$
   4. $b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$ . (Gruppiere kleinere Bälle zu einem größeren Ball)
3. return "es gibt eine machbare lösung".

Eine polynomielle für den Sonderfall, bei dem und von s sind$n=1$$w_j$$2$

Es ist bekannt, dass, wenn und alle Potenzen von , dieser Sonderfall in Polynomzeit gelöst werden kann. $n=1$$w_j$$2$

$$\begin{align*} \text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\ \text{subject to:} & \sum_{j=1}^m w_j x_j = c\\ & 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\ \end{align*}$$

Die Lösung wurde von Yuzhou Gu angedeutet , und eine Zusammenfassung finden Sie hier .

Etwas Hintergrund. Das obige Problem ist das Rucksackproblem mit Einschränkungen. Die effizienteste Rucksack-Problemlösung mit oder ohne Einschränkungen kann in pseudopolynomialer Zeit gelöst werden, immer noch NP-Hard. Für einige Variationen siehe https://en.wikipedia.org/wiki/Knapsack_problem#Definition . Die erste Einschränkung bei dieser Variante besteht darin, dass der Wert von Gegenständen (Bällen), die in den Rucksack (Mülleimer) gelegt werden sollen, keine Rolle spielt. Das Problem beschränkt sich dann auf die Zeit, die benötigt wird, um die Gegenstände in den Rucksack zu legen. Das ursprüngliche Problem erfordert, dass die wertvollsten Gegenstände in möglichst kurzer Zeit abgelegt werden. Eine weitere Einschränkung bei dieser Version ist, dass die Gewichte und alle anderen Argumente Ganzzahlen sind. Und die Einschränkung des Interesses ist, dass die Gewichte$w_j$ Teilen $w_{j+1}$ für alle . Hinweis: Das Fractional-Knapsack-Problem kann in Polynomialzeit gelöst werden, bietet jedoch nicht die praktischste Lösung für das ursprüngliche Problem. Dieses Problem verwendet ganze Zahlen, die sich gleichmäßig teilen (keine rationalen Lösungen). Vielleicht sehen, was die große Sache mit dem Rucksackproblem ist? .$j$

Die Hauptfrage sollte vielleicht lauten: " dieses Problem immer noch NP-schwer, wenn durch ein Polynom begrenzt ist, das , da das Problem weniger komplex ist (in P), wenn es begrenzt ist? Der Grund, warum ich dies sage, liegt daran, dass das Problem es kann Es wird gezeigt, dass es in P ist, wenn begrenzt ist, und NP-hart, wenn nicht notwendigerweise teilt. i w j w j w j + $w_j$$i$$w_j$$w_j$$w_{j+1}$Gleichmäßig (die Gewichte sind einfach zufällig) begrenzen alle Einschränkungen die Komplexität dieses Problems auf diese beiden Bedingungen. Diese Bedingungen (1. das Zufallsgewicht-Rucksackproblem ohne die Artikelwertbeschränkung und 2. das teilbare Gewicht-Rucksackproblem ohne die Artikelwertbeschränkung) negieren sich im Hinblick auf die Verringerung der Komplexität, da die Quotienten der Gewichte selbst zufällig sein können ( besonders wenn unbegrenzt), wodurch exponentielle Zeitberechnungen auferlegt werden (dies wird im folgenden Beispiel gezeigt). Darüber hinaus, da dividieren , an Größe zunimmt exponentiell für jedenw j + 1 w j$w_j$$w_{j+1}$$w_j$$j$. Dies liegt daran , anstatt zufällig gewichteten Elemente des Verwendens (Kugeln , deren Gewichtseinheit alle Einheitsgewichte unter 100 oder 50 oder sogar 10 begrenzt sein kann), bewirkt , dass die Beschränkung , anstatt die Zeitkomplexität von der Anzahl der Ziffern des abzuhängen , das gleiche wie Versuchsteilung, die exponentiell ist.$w_j$

Also ja, das obige Integer-Programm bleibt NP-hart, auch wenn für alle dividiertw j + 1$w_j$$w_{j+1}$$j$ . Und das ist leicht zu beobachten.

Beispiel 1: Es sei$n = 1$ und Zweierpotenzen. Durch die Konstante 2 wird das gesamte Problem in quadratischer Zeit gelöst, wie Ihr Beispiel zeigt. Die Gewichte sind nicht zufällig und daher wird die Berechnung effizient gelöst.$w_p$

Beispiel 2: Es seials, wobeidie Primzahl ist, die, so dass. Dies gilt als$w_{j+1}$$w_j * p$$p$$j$$p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$$w_j$ für alle dividiert . Wir bekommen jedes w j ist das Produkt aller Primzahlen bis j . Die Werte der Einheitsgewichte erhöhen als solche: 1 , 2 , 6 , 30 , 210 , 2310 , 30030 , . .$w_{j+1}$$j$$w_j$$j$. Da esüber den Primzahlsatzeine Schranke gibt ( p j ~ j l o g ( j ) ), da die Quotienten alle Primzahlen sind, erhalten wir die Komplexität NP-Intermediate.$1, 2, 6, 30, 210, 2310, 30030, ...$$p_j$$j log (j)$

Beispiel 3: Sei definiert als w j ∗ R p , wobei R p eine zufällig gewählte Primzahl von zwei bis unendlich ist, entsprechend j . Dies gilt für dieses Problem, da w j w j + 1 für alle j teilt. Wir erhalten die ersten 5 Quotienten (zufällig von zwei nach unendlich fallend) als 101 , 2657 , 7 , 3169 , $w_{j+1}$$w_j * R_p$$R_p$$j$$w_j$$w_{j+1}$$j$$101, 2657, 7, 3169, 2$. Wir sehen, dass das Gewicht auch beim 5. Ball elf Stellen hat. Glücklicherweise war der fünfte Quotient zwei und keine Primzahl in der Größenordnung von oder mehr. $10^{100}$

Beispiel drei oben ist, was passiert, wenn nicht durch ein Polynom entsprechend i begrenzt ist (zufällige Gewichte) . Die zeitliche Komplexität ist exponentiell, NP-schwer. Addieren Sie für eine gewisse Perspektive einfach alle Gewichte und prüfen Sie, ob sie passen. Es gibt jedoch keine Lösung, um das Problem durch Aufteilen der Gewichte erheblich schneller zu lösen, als jede Untergruppe zu testen, ob es funktioniert. Nach ein paar Dutzend Bällen betreten Sie immer noch das Reich der Billionen von Teilmengen oder Billionen von Ziffern.$w_j$$i$