Dlaczego problem plecakowy jest pseudowielomianem?

Wiem, że Knapsackjest to NP-kompletne, podczas gdy można to rozwiązać za pomocą DP. Mówią, że rozwiązanie DP jest pseudo-polynomial, ponieważ jest wykładnicze w „długości wejścia” (tj. Liczbie bitów wymaganych do zakodowania wejścia). Niestety nie dostałem. Czy ktoś może mi to wyjaśnić pseudo-polynomialpowoli?

Czas wykonywania wynosi O (NW) dla nieograniczonego problemu plecakowego z N przedmiotami i plecakiem o rozmiarze W. W nie jest jednak wielomianem długości danych wejściowych, co czyni go pseudo- wielomianem.

Rozważ W = 1 000 000 000 000. Aby przedstawić tę liczbę, wystarczy 40 bitów, więc rozmiar wejściowy = 40, ale obliczeniowe środowisko uruchomieniowe używa współczynnika 1 000 000 000 000, czyli O (2 ⁴⁰ ).

Więc dokładniej mówiąc, czas wykonania jest równy O (2 ^{bity w W} ), co jest wykładnicze.

Zobacz także:

• Jak zrozumieć, że problem plecaka jest NP-kompletny?
• NP-kompletność plecaka
• Złożoność algorytmu programowania dynamicznego dla problemu plecakowego 0-1
• Czas pseudowielomianu

W większości naszych problemów mamy do czynienia z dużymi listami liczb, które wygodnie mieszczą się w standardowych typach danych typu int / float. Ze względu na sposób, w jaki większość procesorów jest zbudowanych tak, aby obsługiwać liczby 4-8 bajtów naraz bez dodatkowych kosztów (w stosunku do liczb, niż mieszczą się na przykład 1 bajt), rzadko spotykamy się ze zmianą czasu działania wynikającą ze skalowania naszych liczb w górę lub w zakresach, które napotykamy w rzeczywistych problemach - więc dominującym czynnikiem pozostaje tylko sama liczba punktów danych, n lub m czynników, do których jesteśmy przyzwyczajeni.

(Możesz sobie wyobrazić, że notacja Big-O ukrywa stały współczynnik, który dzieli 32 lub 64 bity na dane, pozostawiając tylko liczbę punktów danych, gdy każda z naszych liczb mieści się w tylu lub mniej bitach )

Ale spróbuj przepracować z innymi algorytmami, aby działać na zestawach danych zawierających duże liczby całkowite - liczby, które wymagają więcej niż 8 bajtów do reprezentacji - i zobacz, jak to wpływa na środowisko wykonawcze. Wielkość zaangażowanych liczb zawsze robi różnicę, nawet w innych algorytmach, takich jak sortowanie binarne, gdy rozwiniesz się poza bufor bezpieczeństwa, które konwencjonalne procesory dają nam „za darmo”, obsługując partie 4-8 bajtów.

Sztuczka z algorytmem Knapsack, o którym mówiliśmy, polega na tym, że jest on niezwykle czuły (w porównaniu z innymi algorytmami) na wielkość konkretnego parametru W. Dodaj jeden bit do W i podwoisz czas działania algorytmu. Nie widzieliśmy tak dramatycznej reakcji na zmiany wartości w innych algorytmach przed tym, dlatego może się wydawać, że traktujemy plecak w inny sposób - ale to prawdziwa analiza tego, jak reaguje w sposób nie wielomianowy na zmiany wielkości wejściowej.

Czas działania algorytmu plecakowego zależy nie tylko od rozmiaru wejścia (n - liczba elementów), ale także od wielkości wejścia (W - pojemność plecaka) O (nW), który jest wykładniczy pod względem tego, jak jest reprezentowane w komputerze w postaci binarnej (2 ^ n). Złożoność obliczeniowa (tj. sposób przetwarzania bitów wewnątrz komputera) dotyczy tylko rozmiaru danych wejściowych, a nie ich wielkości / wartości .

Zignoruj ​​na chwilę listę wartości / wagi. Powiedzmy, że mamy instancję o pojemności plecaka 2. W danych wejściowych zajęłoby dwa bity. Teraz zwiększymy pojemność plecaka do 4, zachowując resztę wkładu. Nasz wkład wzrósł tylko o jeden bit, ale złożoność obliczeniowa wzrosła dwukrotnie. Jeśli zwiększymy pojemność do 1024, mielibyśmy tylko 10 bitów danych wejściowych dla W zamiast 2, ale złożoność wzrosła o czynnik 512. Złożoność czasu rośnie wykładniczo w rozmiarze W w reprezentacji binarnej (lub dziesiętnej) .

Innym prostym przykładem, który pomógł mi zrozumieć koncepcję pseudowielomianu, jest naiwny algorytm testowania pierwszości. Dla podanej liczby n sprawdzamy, czy jest ona podzielona po równo przez każdą liczbę całkowitą z zakresu 2..√n, więc algorytm wykonuje √ (n − 1) kroków. Ale tutaj n jest wielkością wejścia, a nie jego rozmiarem.

                     Now The regular O(n) case

Natomiast przeszukiwanie tablicy dla danego elementu przebiega w czasie wielomianowym: O (n). Zajmuje co najwyżej n kroków, a tutaj n jest rozmiarem wejścia (długością tablicy).

[ Spójrz tutaj ]

Obliczanie bitów wymaganych do przechowywania liczby dziesiętnej

Sposób, w jaki to rozumiem, jest taki, że pojemność byłaby O (W), gdyby moc wejściowa była tablicą [1, 2, ..., W] , która ma rozmiar W. Ale wejściowa pojemność nie jest tablica liczb, zamiast tego jest pojedynczą liczbą całkowitą. Złożoność czasowa dotyczy związku z wielkością danych wejściowych. Wielkości liczb całkowitych nie jest wartością całkowitą, ale liczba bitów reprezentujących go. Później konwertujemy tę liczbę całkowitą W na tablicę [1, 2, ..., W] w algorytmie, co prowadzi ludzi do błędnego myślenia, że ​​W jest rozmiarem, ale ta tablica nie jest danymi wejściowymi, a sama liczba całkowita.

Potraktuj dane wejściowe jako „tablicę elementów”, a rozmiar jako „ile elementów w tablicy”. Element wejściowy jest w rzeczywistości tablicą n elementów w tablicy, więc rozmiar = n. Dane wejściowe pojemności NIE są tablicą W liczb , ale pojedynczą liczbą całkowitą reprezentowaną przez tablicę bitów log (W). Zwiększ jego rozmiar o 1 (dodając 1 znaczący bit), W podwaja się, więc czas działania podwaja się, stąd wykładnicza złożoność czasowa.