Metody rozwiązywania problemów NP

Wprowadzenie

Problemy klasy NP obarczone są dużą złożonością czasową. Złożoność czasowa wpływa z kolei na realny czas wykonywania danego algorytmu, który z założenia powinien być maksymalnie krótki, a jeżeli jest to niemożliwe – mieścił się w określonym czasie. Istotnym problemem dla klasy problemów NP-Trudnych jest fakt, że znalezienie rozwiązania wymaga złożoności czasowej wykładniczej, a zatem niemożliwym jest efektywne przetwarzanie danych wejściowych na współczesnych komputerach. Fakt ten wymusza z kolei dostosowywanie algorytmów do realnych możliwości komputerów, a zatem koniecznym jest redukowanie kosztów czasowych algorytmów, często poświęcając przy tym jakość uzyskiwanych wyników, czyli uzyskiwanych rozwiązań. Niniejszy rozdział będzie się więc koncentrował na przeglądzie ogólnych metod rozwiązywania problemów klasy NP.

Metody przeszukiwania brute-froce

U podstaw wszystkich problemów NP-Trudnych znajduje się metoda rozwiązywania problemów poprzez zastosowanie techniki przeszukiwania brute-force. Metoda ta polega na sprawdzeniu wszystkich możliwości w celu znalezienia najlepszego możliwego rozwiązania problemu dla zadanych danych wejściowych. Technika przeszukiwania brute-force ma dwie kluczowe zalety:

• zawsze zostanie znalezione najlepsze możliwe rozwiązanie (jeżeli rozwiązanie istnieje);
• jest łatwa do zaimplementowania.

Metoda przeszukiwania brute-force nadaje się zatem przy pierwszym rozpoznaniu danego problemu bowiem mamy możliwość napisania prostego algorytmu, rozwiązującego dany problem małym nakładem pracy. Wspomniana metoda jest jednak obarczona bardzo poważną wadą tj. złożoność czasowa algorytmu rośnie wykładniczo, a zatem sprawdzać się będzie tylko i wyłącznie dla bardzo małej liczby danych wejściowych, nieprzekraczających rzędu 15-40 rekordów. Problem wykładniczej złożoności czasowej obrazuje poniższa tabela:

 
Z powyższej tabeli wynika więc, że posiadając algorytm o złożoności czasowej O(2ⁿ) czas pracy algorytmu wyniesie co najmniej 12 lat przy 60 rekordach w danych wejściowych. Warto w tym miejscu również dodać, że w rzeczywistości czas ten będzie znacznie dłuższy, ponieważ przedstawiona tabela zakłada, że każda operacja algorytmu wymaga jednego cyklu procesora, co w rzeczywistości jest nieosiągalne. W praktyce więc ‘konieczną liczbę operacji’ oraz ‘przybliżony czas trwania obliczeń’ z powyżej tabeli można przemnożyć przez wartość wynoszącą co najmniej 50 cykli lub większą, co da znacznie bardziej realne czasy wykonywania algorytmów, uruchamianych na współczesnych komputerach.

Metody heurystyczne

Kolejną metodą rozwiązywania problemów NP-Trudnych poszukiwanie rozwiązania metodą heurystyczną. Metoda heurystyczna jest to metoda polegająca na poszukiwaniu rozwiązania problemu NP-Trudnego ze złożonością co najwyżej wielomianową. Algorytm heurystyczny charakteryzuje się tym, że z dużym prawdopodobieństwem rozwiązanie optymalne problemu nie zostanie znalezione, jednak znalezione rozwiązanie będzie bliskie optymalnemu. Bliskie optymalnemu z kolei oznacza, że w wyniku działania algorytmu heurystycznego powinieneś uzyskać rozwiązanie względnie satysfakcjonujące zużywając przy tym mniejszą ilość zasobów czasowych niż przy algorytmie o złożoności wykładniczej. Algorytmy heurystyczne zazwyczaj mają wyznaczoną pesymistyczną granicę błędu w stosunku do rozwiązania optymalnego, także w wielu przypadkach znajdują one swoje zastosowanie w codziennym życiu.

Metody genetyczne

Najmniej przewidywalną metodą rozwiązywania problemów NP-Trudnych ze względu na jakość uzyskiwanych rozwiązań jest metoda genetyczna. Metoda genetyczna w dużym uproszczeniu polega na zaimplementowaniu algorytmu, który potrafi wygenerować rozwiązanie, a następnie stara się to rozwiązanie poprawić. Wynik każdego rozwiązania dokonanego w przeszłości wpływa na wyniki uzyskiwane w przyszłości. Celem algorytmów genetycznych jest poprawianie jakości uzyskiwanych rozwiązań wraz z przyrostem liczby przeprowadzonych treningów na bazie danych testowych. Największymi problemami algorytmów genetycznych są:

• algorytm genetyczny w wyniku treningu bardzo często traci zdolność znajdywania rozwiązania optymalnego;
• przetrenowanie algorytmu genetycznego prowadzi do wyraźnego spadku zdolności rozwiązywania problemów na które system nie był trenowany;
• nie da się określić pesymistycznej granicy błędu w stosunku do rozwiązania optymalnego;
• sposób rozwiązywania problemu jest niepowtarzalny tj. trenując algorytm tymi samymi danymi w innej kolejności uzyskamy zupełnie inny genotyp, który może generować zarówno lepsze jak i gorsze wyniki niż wcześniej wytrenowany algorytm;
• algorytm genetyczny może przestać generować wyniki satysfakcjonujące dla danych, które wcześniej były dla nas akceptowalne.

Pomimo, iż liczba wad wynikająca z rozwiązywania problemów metodą genetyczną jest przytłaczająca, to mimo wszystko jest ona interesującym obszarem badań naukowych ze względu na małą złożoność czasową jaką można uzyskać w tego typu algorytmach.

Metody losowe

Uproszczoną wersją metody genetycznej jest rozwiązywanie problemów metodą losową. Metoda losowa w przeciwieństwie do metody genetycznej wymaga znacznie mniejszego nakładu pracy, a ponadto nie wyklucza znalezienia optymalnego rozwiązania. Istotnym problemem algorytmów wykorzystujących metodę losową jest fakt, że wraz ze wzrostem liczby danych wejściowych, drastycznie maleje szansa na znalezienie rozwiązania optymalnego. Pomimo, iż znalezienie rozwiązania optymalnego może okazać się niemożliwe przy zastosowaniu tej metody to metoda losowa nie wyklucza znajdywania rozwiązań bliskich optymalnemu.