Załóżmy, że jestem programistą i mam problem NP-zupełny, który muszę rozwiązać. Jakie są dostępne metody radzenia sobie z problemami NPC? Czy istnieje ankieta lub coś podobnego na ten temat?

Istnieje wiele dobrze zbadanych strategii; co jest najlepsze w twojej aplikacji, zależy od okoliczności.

• Poprawa czasu wykonywania najgorszego przypadku
  Korzystając ze szczegółowych informacji na temat problemu, często można ulepszyć naiwny algorytm. Na przykład istniejąalgorytmy dla Pokrycia Wierzchołków o c < 1,3 [1]; jest to ogromna poprawa w stosunku do naiwnego Ω ( 2 n ) i może sprawić, że rozmiary instancji będą odpowiednie dla ciebie.$O(c^n)$$c < 1.3$$\Omega(2^n)$

• Popraw oczekiwany czas działania
  Korzystając z heurystyki, często możesz opracować algorytmy, które są szybkie w wielu przypadkach. Jeśli te obejmują większość, które spotkasz w praktyce, jesteś złoty. Przykładami są SAT, dla których istnieją dość zaangażowane solwery, oraz algorytm Simplex (który rozwiązuje problem wielomianowy, ale nadal). Jedną z podstawowych technik, która jest często pomocna, jest rozgałęzienie i powiązanie .

• Ogranicz problem
  Jeśli możesz wprowadzić więcej założeń do swoich danych wejściowych, problem może stać się łatwy.

  • Właściwości strukturalne
    Twoje dane wejściowe mogą mieć właściwości, które upraszczają rozwiązanie problemu, np. Płaskość, dwustronność lub brak dodatkowej wartości dla grafów. Zobacz tutaj przykłady klas grafów, dla których CLIQUE jest łatwe.
  • 
    $O(2^kn^m)$$k$$m$$k$$n$
  • Ograniczanie wielkości wejściowych
    Ponadto niektóre problemy dopuszczają algorytmy działające w czasie pseudo-wielomianowym , tzn. Ich czas działania jest ograniczony przez funkcję wielomianową w liczbie, która jest częścią danych wejściowych; naiwna kontrola pierwotności jest przykładem. Oznacza to, że jeśli ilości zakodowane w twoich instancjach mają rozsądny rozmiar, możesz mieć proste algorytmy, które zachowują się dobrze dla ciebie.

• Osłabienie wyniku
  Oznacza to, że tolerujesz błędne lub niepełne wyniki. Istnieją dwa główne smaki:

  • Algorytmy probabilistyczne
    Prawidłowy wynik otrzymujesz tylko z pewnym prawdopodobieństwem. Istnieje kilka wariantów, najbardziej znaczące algorytmy Monte-Carlo i Las-Vegas . Znanym przykładem jest test pierwotności Millera-Rabina .
  • 
    $5$

Patrz Algorithmics na trudne problemy przez Hromkovič do dokładnego leczenia.

1. Prostota to piękno: ulepszone górne granice osłony wierzchołków autorstwa Chen Jianera, Iyada A. Kanja, Ge Xia (2005)

Inne odpowiedzi dotyczyły tego z bardziej teoretycznego punktu widzenia. Oto bardziej praktyczne podejście.

W przypadku „typowych” problemów z decyzją o zakończeniu NP ( „czy istnieje coś, co spełnia wszystkie te ograniczenia?” ), Zawsze tego najpierw spróbuję:

1. Napisz prosty program, który koduje wystąpienie problemu jako wystąpienie SAT .

2. Następnie weź dobry solver SAT , uruchom go (używając najszybszego komputera wielordzeniowego, jaki masz) i zobacz, co się stanie.

Spróbuj najpierw w mniejszych instancjach, aby dowiedzieć się, ile to może potrwać.

Zaskakująco często takie podejście jest znacznie lepsze niż próba wdrożenia własnego solvera specjalnie dla bieżącego problemu:

• Solwery SAT są bardzo sprytne i dobrze zoptymalizowane. Łatwo przewyższają Twoją własną implementację wyszukiwania wstecznego (bez względu na to, ile czasu tracisz na optymalizację kodu). Z łatwością przewyższają także wiele samodzielnych alternatyw, takich jak całkowite liniowe solvery programistyczne.

• Wymaga to bardzo małego programowania. Krok 1 jest stosunkowo prosty i nie ma krytycznego wpływu na wydajność; możesz używać języków skryptowych, takich jak Python. Ktoś inny już zadbał o wdrożenie wszystkiego, czego potrzebujesz do kroku 2.

W przypadku typowych problemów z optymalizacją NP-trudnych ( „znajdź najmniejszą rzecz, która spełnia wszystkie te ograniczenia” ) to podejście może, ale nie musi, działać.

Jeśli możesz łatwo przekształcić go w problem decyzyjny ( „czy istnieje coś takiego jak rozmiar 4, który spełnia wszystkie te ograniczenia?” , „A co z rozmiarem 3?” ), Świetnie, zastosuj to samo podejście jak powyżej w przypadku problemów decyzyjnych.

W przeciwnym razie możesz skorzystać z rozwiązania heurystycznego, które próbuje znaleźć małe rozwiązanie (niekoniecznie najmniejsze ). Na przykład:

1. Zakoduj swój problem jako (ważoną) instancję MAX-SAT .

2. Użyj heurystycznych solverów z pakietu UBCSAT . Rozwiązania heurystyczne równolegle trywialnie; spróbuj znaleźć klaster komputerowy z setkami komputerów. Możesz uruchamiać solwery tak długo, jak chcesz, a następnie wybrać najlepsze rozwiązanie, jakie do tej pory znalazłeś.

Sparametryzowana złożoność

Jednym ze sposobów ataku na trudność jest myślenie o problemie w sparametryzowanym kontekście złożoności.

$k$$f(k) \cdot p(n)$$k$$f(k)$

$O(n^{f(k)})$$\neq$

Oto niektóre przykłady z różnych klas hierarchii W:

1. Pokrywa wierzchołków to FPT (podobnie jak rozłączne ścieżki wierzchołków na niekierowanych grafach)
2. Niezależny zestaw i Clique są kompletne z W [1]
3. Zestawem dominującym jest W [2] -Complete.

Są to kolejne poziomy złożoności pozwalające na bardziej precyzyjne klasyfikowanie problemów NP, a jeśli chcesz więcej, możesz spojrzeć na Parameterized Circuit Complexity i W Hierarchy autorstwa Downey i wsp. (1998).

A jeśli chcesz jeszcze więcej, dobrze jest przeczytać sparametryzowaną teorię złożoności Fluma i Grohe .

I w końcu:

Sparametryzowana złożoność a algorytmy aproksymacyjne:

Wiadomo, że jeśli problem ma FPTAS ( schemat aproksymacji w pełni czasu wielomianowego ), to jest to również FPT (co jest oczywiste). Ale nie ma nic dobrze znanego w odwrotnym kierunku, są też prace nad relacją PTAS i XP, ale jest nie jest bardzo ścisła relacja między PTAS a hierarchią W (przynajmniej nie wiem w tej chwili).

Również w niektórych przypadkach możemy naprawić niektóre inne parametry, np .: długość najdłuższej ścieżki na wykresie jest ograniczona, a rozmiar rozwiązania jest ograniczony (np. W zestawie wierzchołków sprzężenia zwrotnego), ...

Przykładowe praktyczne zastosowania:

Być może niektórzy uważają, że sparametryzowana złożoność jest w praktyce bezużyteczna. Ale to źle. Wiele sparametryzowanych algorytmów jest wykrywanych w rzeczywistych aplikacjach, gdy możesz naprawić niektóre parametry, oto przykład:

1. $2^{.^{.^{.^2}}}O(n)$$2$$O(k)$$k=10$

2. Jednym z najszybszych i najdokładniejszych algorytmów heurystycznych dla TSP jest: Łączenie tras i dekompozycja gałęzi , która wykorzystuje parametryzację problemu (nie bezpośrednio, ale dekompozycja gałęzi i zastosowane podejście do programowania dynamicznego oparte jest na pewnych dobrych założeniach).

Kompletność NP dotyczy najgorszej niemożliwości. W zależności od problemu, nad którym pracujesz, wiele klas instancji może być rozwiązanych w rozsądnym czasie w praktyce (chociaż może być potrzebny bardziej wyspecjalizowany algorytm, aby uzyskać dobre czasy wykonywania).

Zastanów się, czy nie ma skutecznego ograniczenia problemu do problemu dzięki dostępnym dobrym rozwiązaniom, takim jak Boolean Satisfiability lub Integer Linear Programming.

$v_i$$v_j$$v_k$$G$$G$użyj tolerowanego algorytmu, aby rozwiązać problem w czasie wykładniczym . Wśród algorytmów wykładniczych czas działania niektórych z nich może być tolerowany, gdy wielkość wejściowa problemu jest mniejsza niż określona wartość.

Chociaż krótko poruszono niektóre odpowiedzi, chciałbym podkreślić, że w praktyce problemy NP-zupełne są rozwiązywane (lub przybliżane) przez cały czas. Głównym powodem, dla którego możesz rozwiązać problemy NP-complete w praktyce jest:

Przypadki spotykane w praktyce nie są „najgorszym przypadkiem”.

Innym powodem rozbieżności jest:

Formalna analiza algorytmów heurystycznych jest trudna.

W praktyce używasz algorytmów heurystycznych do rozwiązywania problemów z NP-zupełnym nadzieją na najlepsze. Wyniki są często oszałamiające.

Innym zagadnieniem poruszonym w innych odpowiedziach jest:

Czasami algorytmy wykładnicze są wystarczająco szybkie.

To oczywiście zależy od problemu. W przypadku dużych zbiorów danych mamy przeciwną maksymę:

Czasami jedynymi wykonalnymi algorytmami są quasilinear.

Obawiam się, że tłum tutaj jest raczej teoretycznie skłonny. Możesz uzyskać lepsze odpowiedzi na głównej stronie wymiany stosów.