Alg15.pdf

Katedra Aparatów Elektrycznych

Alg15 Dr J. Dokimuk

15. PROBLEMY NP – ZUPEŁNE

Problem plecakowy 01, komiwojaŜera, oraz setki innych są trudne w realizacji.

Gdyby opracowano efektywny algorytm dla któregokolwiek z nich to dysponowa

libyśmy efektywnymi algorytmami dla wszystkich problemów tej grupy.

Takiego algorytmu nie wynaleziono lecz nie udowodniono , Ŝe nie jest to moŜliwe.

161

Katedra Aparatów Elektrycznych

Alg15 Dr J. Dokimuk

Algorytm niedeterministyczny: odpowiada tylko za etap " przypuszczania ", nie moŜna dla

niego wyznaczyć unikalnej sekwencji kolejnych instrukcji.

Podczas realizacji zadań komputer moŜe generować dowolny (losowy) ciąg działań.

Wprowadzenie pojęcia algorytmu niedeterministycznego jest formalnym zabiegiem,

w celu stworzenia pojęcia sprawdzalności w czasie wielomianowym.

+ W praktyce nie korzysta się z algorytmów niedeterministycznych do rozwiązywania problemów decyzyjnych.

Niedeterministyczny algorytm „ rozwiązuje " problem decyzyjny , jeśli dla dowolnego przypadku

1. dla którego odpowiedzią jest „ tak ", istnieje pewien ciąg działań, dla którego na etapie

weryfikacji otrzymamy wynik „prawda".

2. dla którego odpowiedzią jest „ nie ", nie istnieje Ŝaden ciąg działań, dla którego na

etapie weryfikacji otrzymamy wynik „prawda".

Algorytm wielomianowy niedeterministyczny: algorytm niedeterministyczny , którego etap

weryfikacji jest algorytmem wielomianowym.

Zbiór NP ( N ondeterministic P olynomial): zbiór wszystkich problemów decyzyjnych , które

moŜna rozwiązać za pomocą niedeterministycznych algorytmów wielomianowych.

Problem decyzyjny naleŜy do zbioru NP jeŜeli istnieje dla niego algorytm

weryfikujący w czasie wielomianowym.

162

Algorytmy i Struktury Danych – wykład/1st

To jest tematyka problemów NPzupełnych .

Algorytm wielomianowy: jego pesymistyczna złoŜoność czasowa ograniczona jest z góry przez

funkcję wielomianową, zaleŜną od rozmiaru danych wejściowych n .

Istnieje taki wielomian g(n ) , Ŝe: W ( n )

O ( g(n) ).

Uwaga: algorytmy złoŜoności o czasowej 2 n , 2 n/100 , n! nie są algorytmami wielomianowymi.

- nlg(n) nie jest wielomianem , jednak spełniona jest nierówność: nlg ( n ) < n 2 , zatem

algorytm o takiej złoŜoności spełnia kryterium dla algorytmów wielomianowych.

Problem trudny: jeŜeli nie mo Ŝna rozwiązać go za pomocą algorytmu wielomianowego .

Trudność jest własnością problemu , nie zaś algorytmów go rozwiązujących.

Nie moŜe istnieć Ŝaden rozwiązujący go algorytm wielomianowy.

Wiele algorytmów, o nie wielomianowej pesymistycznej złoŜoność czasowej,

posiada dobrą efektywnością dla duŜego zbioru danych Wejściowych.

Znalezienie algorytmu wielomianowego dla pewnych danych wejściowych nie oznacza,

Ŝe problem jest łatwy do rozwiązania dla wszystkich danych wejściowych (dla których

znalezienie algorytmu wielomianowego moŜe okazać się niemoŜliwe) .

Podział problemów ze względu stopień trudności:

1. dla których wynaleziono algorytmy wielomianowe ,

2. których trudność została udowodniona,

3. których trudność nie została udowodniona,

jednak nie udało się opracować algorytmów wielomianowych .

Nie oznacza to, Ŝe musi istnieć algorytm wielomianowy rozwiązujący ten problem decyzyjny .

Decyzyjny problem komiwojaŜera naleŜy do zbioru NP , gdyŜ istnieje weryfikujący go algorytm w

czasie wielomianowym, mino Ŝe nie opracowano algorytmu rozwiązującego ten problem.

Istnieje duŜo problemów, dla których nie udało się stworzyć algorytmu rozwiązującego je w

czasie wielomianowym , ale udowodniono, Ŝe naleŜą one do zbioru NP , poniewaŜ opracowano

dla nich niedeterministyczne algorytmy wielomianowe .

KaŜdy problem naleŜący do zbioru P naleŜy takŜe do zbioru NP .

KaŜdy problem naleŜący do zbioru P moŜna rozwiązać za pomocą algorytmu wielomianowego:

moŜna wygenerować dowolny ciąg na etapie niedeterministycznym, i

uruchomić algorytm wielomianowy na etapie deterministycznym.

Wynikiem weryfikacji dla danego ciągu wejściowego będzie odpowiedź „tak",

jeśli istnieje rozwiązanie dla konkretnego przypadku.

Problemy decyzyjne , dla których udowodniono, Ŝe nie naleŜą do zbioru NP , są

dokładnie tymi samymi problemami, dla których udowodniono, Ŝe są trudne.

Problem optymalizacyjny : jego wynikiem jest optymalne rozwiązanie problemu.

Problem decyzyjny : jego wynikiem jest odpowiedź „tak" lub „nie" dla danego problemu.

Problem plecakowy 01 : znana jest waga i wartość przedmiotów oraz pojemność W plecaka.

O ptymalizacyjny : wyznaczyć maksymalną wartości przedmiotów, które moŜna upchnąć w plecaku.

Decyzyjny: dana jest wartości P , określić , czy istnieje moŜliwość takiego spakowania plecaka, by

łączna waga zapakowanych przedmiotów nie przekraczała W , a łączna wartość tych

przedmiotów wynosiła co najmniej P .

Problem komiwojaŜera: trasą w waŜony grafie skierowanym jest droga rozpoczynająca się i

kończąca w tym samym wierzchołku, przechodząca raz przez

wszystkie pozostałe wierzchołki grafu.

Optymalizacyjny: znaleźć trasę o minimalnej łącznej wadze naleŜących do niej krawędzi.

Decyzyjny: dana jest dodatniej liczba całkowita d , określić czy -w badanym grafie - istnieje trasa o

łącznej wadze naleŜących do niej krawędzi nie większej od d .

Gdyby znaleziono algorytm wielomianowy dla problemów optymalizacyjnych ,

istniałby algorytm wielomianowy dla odpowiednich problemów decyzyjnych .

Rozwiązanie problemu optymalizacyjnego daje rozwiązanie stosownego problemu decyzyjnego.

Zbiór P: zbiór problemów decyzyjnych , które moŜna rozwiązać algorytmami wielomianowymi .

Teoretycznie problem plecakowy 01 moŜe naleŜeć do zbioru P .

Nie opracowano algorytmu wielomianowego rozwiązującego ten problem, lecz nikt

nie udowodnił , Ŝe nie da się go rozwiązać w czasie wielomianowym.

Dany problem decyzyjny nie naleŜy do zbioru P jeŜeli udowodnimy , Ŝe

opracowanie dla niego algorytmu wielomianowego jest niemoŜliwe .

Problem CNF spełnialności

Zmienna logiczną (boolowską), x jest prawdziwe wtedy i tylko wtedy, gdy x jest fałszywe.

Literał jest logiczną zmienną lub negacją logicznej zmiennej.

Klauzula jest sekwencją literałów, oddzielonych za pomocą operatora logicznego OR (v).

Koniunkcyjna postać normalna ( C onjunctive N ormal F orm CNF) logicznego wyraŜenia jest

sekwencją klauzul , oddzielonych za pomocą logicznego operatora AND (

) .

Decyzyjny problem CNFspełnialności : określić dla logicznego wyraŜenia CNF , czy istnieje

takie przyporządkowanie wartości zmiennych (zbiór przyporz ą dkowa ń warto ś ci

„prawda" i „fałsz" do zmiennych u Ŝ ytych w wyra Ŝ eniu), dla którego całe wyraŜenie

będzie prawdziwe .

Dla wyraŜenia CNF

Przykład wyraŜenia logicznego w postaci CNF:

(

)

(

)

(

)

nie istnieją przypisania, dla których będzie ono

prawdziwe , dla problemu CNFspełnialności odpowiedź jest NIE .

Dla wyraŜenia

(

)

istnieją przypisania, dla których będzie ono

prawdziwe , dla problemu CNF-spełnialności odpowiedź jest TAK . (x1=P, x2=x3=F)

(

)

(

)

Katedra Aparatów Elektrycznych

Alg15 Dr J. Dokimuk

Istnieją algorytmy wielomianowe, które dla wyraŜenia logicznego CNF i zbioru przyporządkowań

wartości logicznych do zmiennych sprawdzają , czy wyraŜenie jest logiczne.

Nie istnieje algorytm wielomianowy rozwiązujący ten problem, lecz nie udowodniono,

Ŝe tego problemu nie da się rozwiązać w czasie wielomianowym

S. Cook (1971 r.) udowodnił, Ŝe jeśli problem CNF -spełnialności naleŜy do zbioru P , to P = NP .

163

Katedra Aparatów Elektrycznych

Alg15

164

Algorytmy i Struktury Danych – wykład/1st

Dr J. Dokimuk

Twierdzenie 2.2. (Cook, 1971r.): Problem CNFspełnialności jest problemem NPzupełnym .

Twierdzenie 2.3. Problem C jest problemem NPzupełnym , jeśli spełnione są dwa warunki:

1. Problem C naleŜy do zbioru NP . (weryfikowany wielomianowo)

2. Dla innego problemu NPzupełnego B prawdziwe jest wyraŜenie : B

C .

W oparciu o Tw. Cooka i Tw. 2.3 moŜna wykazać, Ŝe

wybrany problem decyzyjny jest NPzupełny , dowodząc jedynie Ŝe:

1. problem ten naleŜy do zbioru NP,

2. CNFspełnialność

Rysunek przedstawia zbiór wszystkich problemów decyzyjnych , gdzie P jest

podzbiorem zbioru NP ; Ü nie ma jednak pewności, Ŝe tak faktycznie jest.

Niepewność wynika z faktu, Ŝe nie udało się dowieść, Ŝe istnieje

problem w zbiorze NP , który nie naleŜy do zbioru P .

Pytanie czy zbiory P i NP są sobie równe, jest waŜną kwestią w

informatyce, poniewaŜ duŜa grupa problemów decyzyjnych naleŜy

do zbioru NP .

Gdyby okazało się, Ŝe P = NP , moglibyśmy opracować algorytmy wielomianowe dla większości

znanych dzisiaj problemów decyzyjnych .

Aby udowodnić, Ŝe P ≠ NP naleŜy znaleźć problem naleŜący do zbioru NP , który

nie naleŜałby do zbioru P .

Aby udowodnić, Ŝe P = NP , naleŜy znaleźć algorytm wielomianowy dla kaŜdego z

problemów naleŜących do zbioru NP . Zadanie upraszcza się, gdyŜ wykazano , Ŝe konieczne

jest znalezienie wielomianowego algorytmu tylko dla jednej z klas problemów.

NaleŜy rozwiązać problem decyzyjny A , mając algorytm rozwiązującym problem B .

ZałóŜmy, Ŝe mamy algorytm dający realizację y problemu B na podstawie kaŜdej moŜliwej

realizacji x problemu A , przy czym

algorytm dla realizacji y problemu B zwróci odpowiedź „ tak " wtedy i

tylko wtedy, gdy odpowiedź dla realizacji x problemu A brzmi „ tak ".

Taki algorytm nazwano algorytmem transformacji :

i ma postać funkcji y = Trans(x) ,

odwzorowującej dowolne realizacje problemu A

w odpowiednie realizacje problemu B .

Trans jest algorytmem transformacji, odwzorowującym realizację x problemu decyzyjnego A

w realizację y problemu decyzyjnego B .

Łącznie z algorytmem dla problemu B daje algorytm rozwiązujący problem decyzyjny A .

Mamy dane wejściowe x dla problemu A i chcemy odpowiedzi „tak" lub „nie" .

Zastosujemy algorytm Trans do przekształcenia danych x w dane wejściowe y dla

problemu B w taki sposób, Ŝeby odpowiedź problemu B dla danych y była dokładnie

odpowiedzią problemu A dla danych x .

Problem A jest wielomianowo redukowalny do problemu B , jeśli istnieje wielomianowy

algorytm transformacji z problemu decyzyjnego A do problemu decyzyjnego B : A

problemy

decyzyjne

wybrany problem (problem CNFspełnialności redukuje się do naszego problemu).

Zbiór problemów NP-zupełnych jest podzbiorem zbioru NP , zgodne z definicją.

Problemy decyzyjne nie naleŜące do zbioru NP nie mogą

być problemami NPzupełnymi .

NNP

Jeśli P

NP to: P

NPzupełne =

(brak wspólnych elementów)

PowyŜsza zaleŜność wynika z faktu, Ŝe gdyby jakiś problem w zbiorze P

był NPzupełny , to na podstawie Tw.2.1 moglibyśmy uznać, moŜliwość

rozwiązania problemu ze zbioru NP w czasie wielomianowym.

Uwaga: nie jest wykluczone, Ŝe P i NP to ten sam zbiór.

_____________________________________________________________________________

Zbiór P problemów decyzyjnych rozwiązywanych w czasie wielomianowym.

Zbiór NP problemów decyzyjnych zgadywanych i weryfikowanych w czasie wielomianowym.

Zbiór NPzupełny: wszystko albo nic.

Gdyby dla jakiegokolwiek problemu NPzupełnego znaleziono algorytm wielomianowy,

byłby to algorytm dla wszystkich z nich.

KaŜdy problem NPzupełny redukuje się w czasie wielomianowym do kaŜdego innego;

trudność rozwiązania jednego pociąga za sobą trudność rozwiązania wszystkich.

Aby wykazać, Ŝe problem

Algorytm

dla

problemu B

tak

nie

Trans

jest NPzupełny , wystarczy udowodnić, Ŝe problem

redukuje się (w czasie wielomianowym) co najmniej do jednego problemu Q

NPzupełnego i co najmniej jeden problem R NPzupełny , redukuje się do

Pokazanie, Ŝe jakiś problem jest NPzupełny , jest sygnalizacją moŜliwych

trudności w jego rozwiązaniu.

B .

Jeśli złoŜoność czasowa algorytmu transformacji jest wielomianowa

i istnieje wielomianowy algorytm rozwiązujący problem B ,

to algorytm dla problemu A musi być wielomianowy .

Twierdzenie 2.1 . Jeśli problem decyzyjny B naleŜy do zbioru P oraz A

B to problem

decyzyjny A takŜe naleŜy do zbioru P .

Problem B nazywamy NPzupełnym , jeśli spełnione są dwa warunki:

1. Problem B naleŜy do zbioru NP .

2. Dla kaŜdego innego problemu A naleŜącego do zbioru NP prawdziwe jest

wyraŜenie: A

B ( A REDUKOWALNE DO B )

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: