Czy trudno jest wypełnić pojemniki minimalnymi ruchami?

33

Jest koszy i rodzajów piłek. th bin ma etykiet na , jest to oczekiwana liczba kulek typu .nmiai,j1jmj

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.bjjjwjici

Rozważ możliwe rozwiązanie z kulkami typu w bin , wtedy koszt to. Chcemy znaleźć możliwie najniższe koszty.xi,jjii=1nj=1m|ai,jxi,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.{wj}

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.wjwj+1jO(nm)

Problem ma równoważne sformułowanie programu liczb całkowitych. Biorąc pod uwagę dla : ai,j,ci,bj,wj1in,1jm

Minimize:i=1nj=1m|ai,jxi,j|subject to:j=1mxi,jwj=ci for all 1ini=1nxi,jbj for all 1jmxi,j0 for all 1in,1jm

Moje pytanie brzmi,

Czy powyższy program liczb całkowitych NP-trudny, gdy dzieli dla wszystkich ?wjwj+1j

Algorytm, aby określić, czy jest możliwe rozwiązanie w czasO(nm) :

Zdefiniuj i d_j = w_ {j + 1} / w_j . Niech a \% b będzie resztą, gdy a jest podzielone przez b .wm+1=wm(maxjcj+1)dj=wj+1/wja%bab

  1. Jeśli istnieje plik ci który nie jest podzielny przez w1 , zwróć „brak wykonalnego rozwiązania”. (niezmienny ci dzieli wj będzie zawsze utrzymywany w kolejnej pętli)
  2. dla j od 1 do m :

    1. ki=1n(ci/wj)%dj . (wymagane minimum piłek owj )
    2. Jeśli bj<k , zwróć „brak wykonalnego rozwiązania”.
    3. cici((ci/wj)%dj) dla wszystkich . (usuń minimalną liczbę wymaganych kulek o )iwj
    4. bj+1(bjk)/dj . (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ą sn=1wj2

Wiadomo, że jeśli i wszystkie są potęgami , to ten szczególny przypadek można rozwiązać w czasie wielomianowym. n=1wj2

Minimize:j=1m|ajxj|subject to:j=1mwjxj=c0xjbj for all 1jm

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

Chao Xu
źródło

Odpowiedzi:

0

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 wagiwjpodziel 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? .wj+1j

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 dzieliwjiwjwjwj+1ró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żdegowjwj+1wjj. 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.wj

Tak więc, powyższy program liczb całkowitych pozostaje NP-trudny, nawet jeśli dzieli dla wszystkich . wjwj+1j 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=1wp

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 (~wj+1wjppjp=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,Jwjwj+1jwjj1,2,6,30,210,2310,30030,...pjjlog(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ą. wj+1wjRpRpjwjwj+1j101,2657,7,3169,210100

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.wji

Jeff
źródło
1
Ale faktoryzacja pierwotna nie jest uważana za trudną dla NP. Uważa się, że jest to środek pośredni NP.
rus9384,
2
Nie widzę tutaj redukcji. Jaka jest faktyczna redukcja? Biorąc dane wejściowe faktoryzacji pierwotnej i jakoś wyprowadzać faktoryzację za pomocą rozwiązania programu liczb całkowitych.
Chao Xu,
2
Czy miałbyś na myśli „powyższy program liczb całkowitych jest trudny dla NP”? Pojedynczy program nie może być trudny do NP.
Yuval Filmus,
1
W rzeczywistości rozkład na czynniki pierwsze znajduje się w . Tak więc jest to -hard if . NPcoNPNPNP=coNP
rus9384,
2
Niestety dodatkowe zmiany nie wyjaśniły tego. Rzeczywista redukcja byłaby pomocna.
Chao Xu,