Twoje ulubione oszustwo związane z NP-zupełnością
devblogi
Oryginalny post: Your Favorite NP-Complete Cheat
Autor: Jeff Atwood
Tłumaczenie: Rafał Legiędź (z www.devblogi.pl)
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.
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:
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ą?
Jeśli spodobał Ci się ten artykuł, zajrzyj na www.devblogi.pl, gdzie regularnie zamieszczamy tłumaczenia najpoczytniejszych blogów o tworzeniu oprogramowania.
Wszelkie prawa do zamieszczonego tłumaczenia są zastrzeżone; prawa autorskie do tłumaczenia zachowuje tłumacz.