Twoje ulubione oszustwo związane z NP-zupełnością

Oryginalny post: Your Favorite NP-Complete Cheat

Autor: Jeff Atwood

Czy kiedykolwiek słyszałeś, żeby inżynier oprogramowania odnosił się do jakiegoś problemu mianem "NP-zupełny"? To wymyślny, żargonowy skrót do "niesamowicie trudny".

Najbardziej znana cecha problemów NP-zupełnych to to, że nieznany jest sposób na ich szybkie rozwiązanie; to oznacza, że czas jaki jest wymagany na rozwiązanie danego problemu przy użyciu obecnie znanych algorytmów, wzrasta bardzo szybko w miarę wzrostu rozmiaru problemu. W rezultacie, czas potrzebny do rozwiązania nawet średnioskomplikowanych takich problemów, z łatwością osiąga miliardy bądź biliony lat używając jakiejkolwiek ilości mocy obliczeniowej, jaka jest dziś dostępna. W konsekwencji, określenie tego, czy jest możliwe szybkie rozwiązanie tych problemów, jest jednym z głównych nierozwiązanych problemów w dzisiejszej informatyce.

Mimo iż metody wyznaczania rozwiązań problemów NP-zupełnych w rozsądnym czasie pozostają nieznane, informatycy i programiści ciągle napotykają na takie problemy. Biegły programista powinien umieć rozpoznać problem NP-zupełny po to, aby nieświadomie nie tracił czasu na rozwiązanie problemu, który jak do tej pory umykał pokoleniom informatyków.

Chcesz być biegłym programistą, nieprawdaż? Pewnie, że chcesz!

Problemy NP-zupełne są jak ostra pornografia. Nikt nie potrafi dokładnie zdefiniować, co czyni problem NP-zupełnym, ale będziesz to wiedział jak go zobaczysz. Tym razem, powstrzymam się od zwyczaju wrzucania obrazka do zobrazowania moich myśli.

(Uaktualnienie: Starałem się dać poetycką aluzję do problemu P=NP, ale w oparciu o komentarze jest ona mylna i niewątpliwie zła. Tak więc zredaguję to zdanie. Przekieruję Cię do tej ankiety o P=NP (pdf); poczytaj komentarze od profesorów informatyki (włącznie z Knuthem), aby załapać ideę, jak życiowe to może być.)

Wobec tego, polecam książkę, którą Anthony Scian mi polecił: Computers and Intractability: A Guide to the Theory of NP-Completeness.

książka p=np

Tak jak wszystkie książki programistyczne, które polecam, ta jest ponadczasowa. Pierwotnie wydana w 1979 roku, godne naśladowania świadectwo zdolnych ludzi podejmujących naprawdę trudne problemy w dziedzinie informatyki: "Nie potrafię znaleźć skutecznego algorytmu, ale nawet Ci wszyscy znani ludzie nie potrafią."

Tak więc ile problemów jest NP-zupełnych? Całe mnóstwo.

Nawet jeśli jesteś laikiem, mogłeś doświadczyć NP-zupełności pod postacią Sapera, tak jak to wyjaśnia Ian Stewart. Ale dla programistów, założyłbym się, iż najbardziej znanym problemem NP-zupełnym jest Problem komiwojażera.

Mając daną ilość miast oraz koszty podróży z jednego miasta do drugiego, jaka jest najtańsza droga przechodząca przez każde miasto dokładnie raz i kończąca się w mieście początkowym?

Rozwiązanie metodą brute-force -- próbowanie każdej możliwej permutacji miast -- może działać jedynie dla małych sieci miast, ale szybko staje się nie do utrzymania. Nawet gdybyśmy użyli teoretycznych procesorów, które mogłyby mieć nasze dzieci, albo dzieci naszych dzieci. Co gorsza, każdy inny algorytm, który wymyślimy, aby znaleźć optymalną ścieżkę dla akwizytora, ma ten sam problem. Jest to wspólna charakterystyka problemów NP-zupełnych: są ćwiczeniami z heurystyk i przybliżeń, tak jak zostało to zilustrowane przez ten oto komiks xkcd:

xkcd np-complete

Co robią biegli programiści, kiedy napotkają na trudny problem? Oszukują. I Ty też powinieneś! W rzeczy samej, niektóre ze współczesnych aproksymacji dla Problemu komiwojażera są nadzwyczaj efektywne.

Zostało wynalezionych wiele algorytmów aproksymacyjnych, które szybko dają dobre rozwiązania o wysokim prawdopodobieństwie. Współczesne metody pozwalają znaleźć rozwiązanie dla niesamowicie dużych problemów (miliony miast) w rozsądnym czasie, z prawdopodobieństwem bycia odchylonym o 2-3% od optymalnego rozwiązania.

Niestety nie wszystkie problemy NP-zupełne mają dobre przybliżenia. Ale te które mają, zmuszają mnie do przemyślenia: jeśli poprzez oszustwo potrafimy zbliżyć się tak bardzo do optymalnego rozwiązania, to czy ma znaczenie to, że nie istnieje algorytm, który znajduje to optymalne rozwiązanie? Jeśli już, to z problemów NP-zupełnych nauczyłem się jednego: czasem dojście do mądrego oszustwa może być bardziej interesujące, niż bezskuteczne poszukiwanie doskonałego rozwiązania.

Rozważmy algorytm "First Fit Decreasing" dla Problemu pakowania, który jest NP-zupełny. Nie jest idealny, ale za to jest niesamowicie prosty i szybki. Algorytm jest tak prosty, że prawdę mówiąc, jest regularnie pokazywany na warsztatach z zarządzania czasem. A.. i gwarantuje on, że zbliżysz się na przynajmniej 22% do idealnego rozwiązania za każdym razem. Nie tak źle, jak na podłe oszustwo.

Tak więc jakie jest Twoje ulubione oszustwo związane z NP-zupełnością?

Data publikacji oryginału: 15 listopada, 2008

3 komentarze:

Konradzik pisze...

Hm, zapewne metoda branch & bound dla problemu komiwojażera - mam jakąś słabość do drzew.

Z tego co pamiętam z pierwszych wykładów na studiach, rozwiązanie jednego, dowolnego problemu NP-zupełnego rozwiązywałoby wszystkie problemy NP-zupełne. Nigdy nie potrafiłem sobie tego wyobrazić, ale to jedno zapadło mi w pamięć.

rafek pisze...

Chciałeś pewnie powiedzieć o redukcjach wielomianowych (a dokładniej o rodzinie redukcji wielomianowych obliczalnych na deterministycznej maszynie Turinga w czasie wielomianowym). Redukcje wielomianowe mają następującą własność: jeśli problem K1 jest redukowalny wielomianowo do problemu K2 oraz K2 należy do klasy P, to K1 również należy do klasy P. Używa się tego zazwyczaj do ustalania, że jakiś problem należy do klasy NP -- poprzez pokazanie odpowiedniej redukcji.

batman pisze...

Nie ma rzeczy niemożliwych. Są tylko rzeczy nieopłacalne.
Dobrego programistę pozna się po tym, że nie będzie ślepo brnął w problem, tylko znajdzie jego obejście. Innymi słowy, oszuka.

Prześlij komentarz

Related Posts with Thumbnails