Halo, halo! Sięgniemy znowu do matematyki, abyśmy wyjaśnili sobie jeszcze jeden ważny termin jaki dotyczy algorytmów. Brzmi "problem NP-zupełny". Zapraszam do środeczka po wyjaśnienia i nie uciekać mi od tego, tylko dlatego że głupio brzmi!
| Tweet |
PROBLEM NP-ZUPEŁNY WYMAGA SIĘGNIĘCIA DO HISTORII
Celem zrozumienia tego terminu, w grę wchodzi już nie sama matma, ale także historia. Sprawa dotyczy wynalezienia maszyny Turinga przez jednego z pionierów informatyki, Alana Turinga. Choć termin kompletnie nie rodzi sensu gramatycznego (dla mnie też był dziwaczny za pierwszym razem), to jednak spróbuję Wam nakreślić o co w nim chodzi. Rozbijmy sobie ten termin na drobne atomy, zastosujemy sobie takie "dziel i rządź" ;).
Na początek literki. Co to może znaczyć "NP"? Nawet nie myśl o "na przykład", bo nie o to idzie :D. Tu chodzi o anglojęzyczny termin "non-deterministic polynomial-time" ("niedeterministyczny czas wielomianowy"). Nie bez kozery przywołałem tu maszynę Turinga, bo ona ma duży związek z dzisiejszym tematem. Maszyna Turinga była pierwszym krokiem w stronę rozwiązywania algorytmów. W dzisiejszych czasach komputery są w pewnym sensie takimi samymi maszynami, gdyż także potrafią uruchamiać programy i wykonywać rozkazy (choć w skończonej przestrzeni bitów informacji w przeciwieństwie do maszyny Turinga). Wróćmy do powyższego pojęcia.
WYJAŚNIENIE ZAGADKI
Najpierw pierwszy człon: "non-deterministic". Tu wchodzimy na bardzo ważny "teren" wiedzy z jakim problem NP-zupełny ma dużą styczność. Ten "niedeterminizm" oznacza pewną losowość albo lepiej, brak możliwości przewidzenia wyniku. W kontekście algorytmów należy to rozumieć jako sytuację, w której po wprowadzeniu IDENTYCZNEGO zbioru danych wejściowych, uzyskujemy każdorazowo RÓŻNE wyniki. W ten sposób docieramy do tzw. niedeterministycznej maszyny Turinga, która w teorii posiadałaby możliwość kopiowania się na tyle sztuk, ile by wynikało z mocy zbioru możliwych działań (przejść). Deterministyczna odmiana tej maszyny jest w stanie wykonywać jeden rozkaz w tym samym czasie, a niedeterministyczna pozwalałaby na rozchodzenie się innych instancji maszyn zależnie od liczby przejść, do których ona zmierza. To właśnie oznacza "non-deterministic".
To wszystko o czym tu piszę, odnosi się do problemów decyzyjnych. Jest to taki rodzaj problemu, którego rozwiązanie przynosi odpowiedź w stylu TAK lub NIE. Na przykład:
- czy w danym grafie ważonym można znaleźć drogę od węzła A do węzła B?
- czy można osiągnąć daną sumę wartości elementów zawartych w plecaku o danej pojemności?
Została nam druga część pojęcia ("polynomial-time"). Zapytam w drugą stronę. Co może nie być wielomianowe? Złożoność czasowa algorytmów! Na tym się koncentruje problem NP-zupełny! To jest problem, który na podstawie wielu badań i dowodów został uznany za taki, który nie posiada żadnej znanej metody jego rozwiązania w czasie wielomianowym. Ująłem to W OGROMNYM skrócie, ogromnym jak te litery drukowane.
Formalna definicja jest o wiele bardziej przerażająca, więc już poeksplorujcie sobie sami zaglądając do innych witryn. Pozwolę sobie tylko to skwitować w ten sposób, że problem NP-zupełny pojawia się wówczas, kiedy powstaje czas wykładniczy (niewielomianowy) dla deterministycznej maszyny Turinga i można go sprowadzić do postaci wielomianowej używając niedeterministycznej maszyny Turinga. Różnica między nimi jest taka, że dla modelu niedeterministycznego, teoretycznie powstawałoby tyle maszyn Turinga, do ilu wszystkich możliwych stanów mogłaby ona przejść (co skutecznie podnosiłoby liczbę wykonywanych rozkazów w jednym czasie). Ale jak pisałem, tu wchodzimy już w taką "grubą matmę" i nie chcę mącić.
Czyli wniosek końcowy jest taki: "non-deterministic polynomial-time" to klasa problemów decyzyjnych i odnosi się do czasu wielomianowego osiąganego wyłącznie przy użyciu niedeterministycznej maszyny Turinga.
Jest jeszcze ta "zupełność". Czy to znaczy, że mogą być pewne "problemy NP-niezupełne" ;)? Chill out, wszystko wyjaśnię tak łatwo, jak będę w stanie. Samo "gołe NP" już wiemy co oznacza, a "NP-zupełność" (ang. "NP-completeness") to jest podzbiór problemów NP. Jest to taka grupa problemów, które mogą zostać zredukowane do dowolnego problemu "samo NP" w czasie wielomianowym. Cały czas miejmy jednak z tyłu głowy to, że ich rozwiązanie w czasie wielomianowym jest możliwe tylko przy użyciu niedeterministycznej maszyny Turinga.
ZNAKI ROZPOZNAWCZE NP-ZUPEŁNOŚCI?
Problem NP-zupełny można łatwo rozpoznać po wykładniczym wzroście czasu potrzebnego na rozwiązanie specyficznego problemu względem rozmiaru danych wejściowych. Widzieliście co się działo przy problemie komiwojażera, dyskretnym problemie plecakowym czy też problemie pokrycia zbioru. To są przypadki problemów NP-zupełnych, gdyż każdy z tych przykładów charakteryzuje się gwałtownym skokiem złożoności już przy niewielkich danych (O(n!) i O(2n)). A jak jeszcze można stwierdzić kiedy problem jest NP-zupełny?
Każdy z tych trzech przykładów wyróżnia jeden wspólny czynnik. Te problemy wymagały sprawdzenia wszystkich dostępnych kombinacji. I to jest podstawowy punkt zaczepienia! Może być jeszcze taka sytuacja, kiedy nie da się podzielić problemu na fragmenty (jak na przykład poprzez programowanie dynamiczne) i wtedy także pada podejrzenie, że może być to problem NP-zupełny.
PORADŹ CO MAM ZROBIĆ!
Remedium na to jest proste - trzeba przeskoczyć próbę rozwiązania w sposób dokładny i przesiąść się na aproksymację (oraz ewentualną zachłanność). Nie ma innej metody! Problem NP-zupełny przestanie być dylematem dopiero gdy wejdą komputery kwantowe ;). A na razie póki co, musimy się zadowolić rozwiązaniem przybliżonym, które w przeważającej części wcale nie jest takie "ble".
To już koniec? Tak, to koniec! Nie zamierzam Was obciążać skomplikowanymi tłumaczeniami i terminami, bo od tego są literatury ukierunkowane na matematykę i algorytmikę. Tu chciałem pokazać o co chodzi bez wchodzenia w enigmatyczne symbole, zwłaszcza z myślą o osobach, które chcą zdać ;).