Algorytmy z powracaniem
- Typy problemów obliczeniowych:
- Problem decyzyjny to taki problem obliczeniowy, w
którym rozwiązaniem jest odpowiedź TAK lub NIE np. czy graf G
zawiera cykl Hamiltona?
- Problem przeszukiwania to taki problem
obliczeniowy, w którym szukamy rozwiązania spełniającego pożądane
kryteria lub potwierdzenia, że takie rozwiązanie nie istnieje np.
znajdź cykl Hamiltona w grafie G
- Problem optymalizacyjny wymaga znalezienia
rozwiązania optymalnego względem określonego kryterium np. znajdź
cykl Hamiltona o minimalnej sumie wag krawędzi
- Klasy złożoności obliczeniowych:
- Klasa złożoności NP zawiera problemy
decyzyjne, których rozwiązanie da się zweryfikować w
czasie wielomianowym
(np. czy podana ścieżka jest cyklem Hamiltona w
grafie G)
- Klasa złożoności P zawiera problemy
decyzyjne, które da się rozwiązać w czasie
wielomianowym (np. czy graf G zawiera cykl
Eulera?)
- Klasa złożoności NP-hard (NP-trudne) zawiera
problemy, do których można przetransformować w czasie wielomianowym
wszystkie problemy z klasy NP
- Klasa złożoności NP-complete (NP-zupełne) zawiera
problemy z klasy NP, które są NP-trudne
- Klasa złożoności strong NP-complete (silnie
NP-zupełne) zawiera problemy NP-zupełne, które są nieliczbowe lub takie,
które pozostaną NP-zupełne nawet przy ograniczeniu wartości parametrów
liczbowych do wielomianu od wielkości instancji
- Praktyczne konsekwencje:
- Jeżeli problem decyzyjny jest NP-zupełny, to odpowiadający mu
problem przeszukiwania lub optymalizacyjny jest NP-trudny (jeśli trudno
odpowiedzieć czy graf posiada cykl Hamiltona, to na pewno trudno go
wskazać lub wybrać optymalny spośród wszystkich)
- Jeżeli w czasie wielomianowym rozwiązać można problem przeszukiwania
lub optymalizacyjny, to jego wariant decyzyjny należy do klasy P (jeśli
łatwo znaleźć rozwiązanie, to równie łatwo zweryfikować czy podane
rozwiązanie jest poprawne)
- Aby wykazać, że problem jest NP-zupełny, należy:
- Najpierw wykazać, że jest to problem z klasy NP
- Następnie udowodnić, że można do niego przetransformować w czasie
wielomianowym inny problem NP-zupełny
- Problem obliczeniowy a złożoność obliczeniowa:
- Klasa złożoności to cecha problemu obliczeniowego
- Złożoność obliczeniowa to cecha algorytmu
Programowanie dynamiczne
- Istnieją różne warianty problemu plecakowego:
- Na zajęciach omawialiśmy binarny (0-1) wariant, w którym każdy
przedmiot występuje raz
- W innych wariantach przedmiotów może być więcej lub
pojemność plecaka i wielkości przedmiotów mogą być wyrażane w wielu
wymiarach
- Istnieje również wariant ciągły problemu plecakowego, w którym
możemy umieszczać w plecaku ułamkowe wielkości przedmiotów
- Inne podejście do rozwiązywania problemu plecakowego dają algorytmy
zachłanne
- Są to algorytmy iteracyjne, w których algorytm na każdym kroku
wybiera rozwiązanie najlepsze spośród rozwiązań sąsiadujących i powtarza
ten krok dopóki to możliwe
- Algorytmy zachłanne zawsze kończą działanie w lokalnym optimum
zależnym od punktu początkowego
- Zazwyczaj algorytmy zachłanne łatwo zaprojektować i działają one
bardzo szybko, jednak niewiele jest problemów, dla których dają one
gwarantowany rozwiązanie optymalne
- Przykładowe algorytmy zachłanne dla problemu plecakowego:
- Posortuj nierosnąco przedmioty wg wartości i dopóki jest miejsce w
plecaku, umieszczaj przedmioty wg kolejności sortowania
- Jak wyżej, ale posortuj przedmioty niemalejąco wg wagi
- Jak wyżej, ale posortuj nierosnąco wg współczynnika wartość /
waga