Czy trudno jest wypełnić pojemniki minimalnymi ruchami?

Jest koszy i rodzajów piłek. th bin ma etykiet na , jest to oczekiwana liczba kulek typu .$n$$m$$i$$a_{i,j}$$1\leq j\leq m$$j$

Zaczynasz od kul typu . Każda kula typu ma masę i chce umieścić kulki w pojemnikach tak, aby bin miał masę . Rozmieszczenie kulek, które utrzymują poprzednie warunki, nazywa się wykonalnym rozwiązaniem.$b_j$$j$$j$$w_j$$i$$c_i$

Rozważ możliwe rozwiązanie z kulkami typu w bin , wtedy koszt to. Chcemy znaleźć możliwie najniższe koszty.$x_{i,j}$$j$$i$$\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$

Ten problem jest wyraźnie trudny do rozwiązania, jeśli nie ma ograniczeń dla . Problem sumy podzbiorów sprowadza się do istnienia wykonalnego rozwiązania.$\{w_j\}$

Jeśli jednak dodamy warunek, że dzieli dla każdego , wówczas redukcja sumy podzbiorów nie będzie już , więc nie jest jasne, czy wynikający z tego problem pozostaje trudny do NP. Sprawdzenie, czy istnieje wykonalne rozwiązanie, zajmuje tylko czas (załączony na końcu pytania), ale nie daje nam to możliwego do zrealizowania minimalnego kosztu.$w_j$$w_{j+1}$$j$$O(n\,m)$

Problem ma równoważne sformułowanie programu liczb całkowitych. Biorąc pod uwagę dla : $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*}$$

Moje pytanie brzmi,

Czy powyższy program liczb całkowitych NP-trudny, gdy dzieli dla wszystkich ?$w_j$$w_{j+1}$$j$

Algorytm, aby określić, czy jest możliwe rozwiązanie w czas$O(n\,m)$ :

Zdefiniuj i d_j = w_ {j + 1} / w_j . Niech a \% b będzie resztą, gdy a jest podzielone przez b .$w_{m+1}=w_m(\max_{j} c_j + 1)$$d_j = w_{j+1}/w_j$$a\%b$$a$$b$

1. Jeśli istnieje plik $c_i$ który nie jest podzielny przez $w_1$ , zwróć „brak wykonalnego rozwiązania”. (niezmienny $c_i$ dzieli $w_j$ będzie zawsze utrzymywany w kolejnej pętli)

2. dla $j$ od $1$ do $m$ :

   1. $k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$ . (wymagane minimum piłek o$w_j$ )
   2. Jeśli $b_j<k$ , zwróć „brak wykonalnego rozwiązania”.
   3. $c_i \gets c_i - ((c_i/w_j)\% d_j)$ dla wszystkich . (usuń minimalną liczbę wymaganych kulek o )$i$$w_j$
   4. $b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$ . (grupuj mniejsze piłki w większą piłkę)
3. powrót „istnieje realne rozwiązanie”.

Wielomianowe rozwiązanie czasowe dla specjalnego przypadku, w którym , a są potęgą s$n=1$$w_j$$2$

Wiadomo, że jeśli i wszystkie są potęgami , to ten szczególny przypadek można rozwiązać w czasie wielomianowym. $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*}$$

Rozwiązanie zostało zasugerowane przez Yuzhou Gu , a opis można znaleźć tutaj .

Trochę tła. Powyższym problemem jest problem plecaka z ograniczeniami. Najbardziej wydajne rozwiązanie problemu plecakowego z ograniczeniami lub bez może być rozwiązane w czasie pseudo wielomianowym, wciąż NP-Hard. Niektóre odmiany można znaleźć na stronie https://en.wikipedia.org/wiki/Knapsack_problem#Definition . Pierwszym ograniczeniem w tym wariancie jest to, że wartość przedmiotów (piłek), które należy umieścić w plecaku (pojemnikach), nie ma znaczenia. Problem ogranicza się do czasu, jaki zajmuje włożenie przedmiotów do plecaka. Pierwotny problem wymaga umieszczenia najcenniejszych przedmiotów w jak najkrótszym czasie. Kolejnym ograniczeniem w tej wersji jest to, że wagi i wszystkie inne argumenty są liczbami całkowitymi. Ograniczeniem zainteresowania jest to, że wagi$w_j$podziel dla wszystkich . Uwaga: problem ułamkowego plecaka można rozwiązać w czasie wielomianowym, ale nie przedstawia on najbardziej praktycznych rozwiązań pierwotnego problemu. Ten problem wykorzystuje liczby całkowite, które dzielą się równomiernie (brak racjonalnych rozwiązań). Być może zobacz, o co chodzi z problemem plecaka? .$w_{j+1}$$j$

Być może głównym pytaniem powinno być „czy ten problem jest nadal NP-Hard, gdy jest nieograniczony przez wielomian odpowiadający , ponieważ problem jest mniej złożony (w P), gdy jest ograniczony? Powodem, dla którego mówię, że jest tak, ponieważ problem może być pokazane jako P, gdy jest ograniczone, i NP-Hard, gdy niekoniecznie dzieli$w_j$$i$$w_j$$w_j$$w_{j+1}$równomiernie (wagi są po prostu losowe), wszystkie ograniczenia ograniczają złożoność tego problemu do tych dwóch warunków. Warunki te (1. problem plecaka losowego ciężaru bez ograniczenia wartości przedmiotu i 2. problem plecaka wagowego podzielnego bez ograniczenia wartości przedmiotu) negują się nawzajem pod względem zmniejszenia złożoności, ponieważ iloraz wag może być losowy ( szczególnie gdy nie ma ograniczeń), co nakłada wykładnicze obliczenia czasu (zostanie to pokazane w poniższym przykładzie). Dodatkowo, ponieważ dzieli , powiększa się wykładniczo dla każdego$w_j$$w_{j+1}$$w_j$$j$. Wynika to z faktu, że zamiast używać losowo ważonych przedmiotów (kule, których masa jednostkowa może być ograniczona do wag jednostkowych poniżej 100 lub 50, a nawet 10), ograniczenie powoduje, że złożoność czasowa zależy od liczby cyfr , tak samo jak podział próbny, który ma charakter wykładniczy.$w_j$

Tak więc, powyższy program liczb całkowitych pozostaje NP-trudny, nawet jeśli dzieli dla wszystkich . $w_j$$w_{j+1}$$j$ I łatwo to zaobserwować.

Przykład 1: niechibędą potęgami dwóch. Ze względu na ciągłe dwa, cały problem jest rozwiązywany w czasie kwadratowym, jak pokazuje twój przykład. Wagi nie są losowe, dlatego obliczenia są rozwiązywane skutecznie.$n = 1$$w_p$

Przykład 2: niechzostanie zdefiniowane jako, gdziejest liczbą pierwszą odpowiadającą, tak że. Ma to zastosowanie, ponieważdzielidla wszystkich. Otrzymujemy, że każdyjest iloczynem wszystkich liczb pierwszych do. Wartości ciężarów jednostkowych wzrost w następujący sposób:. Ponieważ istnieje ograniczenie (~$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$$w_{j+1}$$j$$w_j$$j$$1, 2, 6, 30, 210, 2310, 30030, ...$$p_j$$j log (j)$, poprzez twierdzenie o liczbie pierwszej), ponieważ ilorazami są wszystkie liczby pierwsze, otrzymujemy złożoność NP-Pośrednia.

Przykład 3: niechzostanie zdefiniowane jako, gdziejest losowo wybraną liczbą pierwszą od dwóch do nieskończoności, odpowiadającą. Dotyczy to tego problemu, ponieważdzielidla wszystkich. Otrzymujemy pierwsze 5 ilorazów (losowo spada z dwóch do nieskończoności), jako. Widzimy, że nawet przy piątej piłce waga ma jedenaście cyfr. Na szczęście piąty iloraz wynosił dwa i nie był liczbą pierwszą rzędulub większą. $w_{j+1}$$w_j * R_p$$R_p$$j$$w_j$$w_{j+1}$$j$$101, 2657, 7, 3169, 2$$10^{100}$

Powyższy przykład trzeci ma miejsce, gdy nie jest ograniczone (wagi losowe) wielomianem odpowiadającym . Złożoność czasowa jest wykładnicza, NP-twarda. Dla pewnej perspektywy po prostu zsumuj wszystkie ciężary i sprawdź, czy pasują. Ale nie ma rozwiązania, aby rozwiązać go znacznie szybciej, dzieląc wagi, niż wypróbować każdy podzbiór, aby sprawdzić, czy działa. Po kilkudziesięciu piłkach wciąż wchodzisz w sferę nawet trylionów podzbiorów lub trylionów cyfr.$w_j$$i$