Większość algorytmów, o których była mowa o tej pory miała koszt czasowy i pamięciowy wielomianowy, tzn. rząd wielkości czasu potrzebnego do ich wykonania był ograniczony z góry przez funkcję wielomianową względem rozmiaru danych. Takie były algorytmy wyszukiwania, sortowania, algorytmy realizujące różne operacje na grafach i ogólniej na zbiorach. Wszystkie te algorytmy uważamy za realizowalne w rozsądnym czasie.

Problem znajdowania najdłuższego wspólnego podciągu jest wielomianowy, chociaż można przedstawić rozwiązanie, którego koszt jest wykładniczy. Problem mnożenia ciągu macierzy  też jest wielomianowy, znalezienie pełnego nawiasowania, przy którym liczba mnożeń skalarnych będzie najmniejsza metodą programowania dynamicznego zajmuje O(n ³) czasu. Zwróćmy jeszcze raz uwagę, że problem jest wielomianowy, jeśli chociaż jeden algorytm potrafi go rozwiązać z kosztem wielomianowym. Istnieją jednak zadania, których nie umiemy rozwiązać żadną ze znanych nam technik w czasie wielomianowym.

Problem "Wieże Hanoi"

Danych jest n krążków, umieszczonych w porządku rosnących średnic, na drążku A. Zadanie polega na przeniesieniu wszystkich krążków na drążek B, przy czym można wykorzystywać pomocniczy drążek C. Początkowo drążki B i C są puste. Przenoszenie drążków odbywa się wg. zasady : mniejszy krążek może być położony tylko na krążku większym.

Pytanie 1: Ile pojedynczych przeniesień krążków trzeba wykonać, dla n=3?

Tybetańczycy, którzy rozważali ten problem dla n = 64, wierzyli, że świat skończy się wcześniej nim zostanie przeniesiony ostatni z krążków. Dlaczego? Istnieje przecież prosty, rekurencyjny algorytm rozwiązujący ten problem, por. algorytm "move".

Zauważmy, że skoro n-1 pierwszych krążków zostało już przełożonych z drążka A na drążek C (w wyniku wywołania  move (n-1, A, C, B)), to na drążku A pozostał tylko jeden krążek (największy), a drążek B jest pusty. Możemy więc bezpiecznie przenieść ten jedyny krążek na drążek B, a następnie, stosując to samo postępowanie, przenieść  z C pozostałe n-1 krążków na drążek B.

Koszt algorytmu "move", mierzony liczbą przeniesień krążków, wyraża się następującym równaniem rekurencyjnym:

T(1) = 1,   T(n) = T(n-1) + 1 + T(n-1).

Rozwiązaniem tego równania jest funkcja wykładnicza T(n) = 2ⁿ - 1. Przy tempie przekładania 10⁶ krążków/sek. dla n= 64 praca zajęłaby więcej niż 0.5 miliona lat. Nie ma co się dziwić Tybetańczykom! Niestety nie jest znany żaden algorytm wielomianowy, który rozwiązywałby ten problem. Co więcej można wykazać, że 2ⁿ - 1 jest też dolnym ograniczeniem koniecznej liczby ruchów w rozwiązaniu tego problemu.

Problem permutacji

Dana jest liczba naturalna n. Wypisać wszystkie możliwe permutacje liczb od 1 do n.

Jest wiele różnych sposobów tworzenia kolejnych permutacji. Jedną z prostszych metod jest następująca: aby wypisać wszystkie permutacje liczb od 1 do n, wypiszmy wszystkie permutacje liczb od 2 do n, i w każdej z nich umieśćmy liczbę 1 na wszystkich możliwych n pozycjach: przed pierwszym elementem przed drugim itd.... przed (n-1)szym i po (n-1)szym. Taka metoda wydaje się być bardzo dobra, ale po zastanowieniu dojdziemy do wniosku, że pojawia się problem przechowywania wygenerowanych permutacji. (n-1)! ciągów do zapamiętania to bardzo dużo. Już dla małych n, możemy przekroczyć możliwości naszego komputera.

Pytanie 2: W jakiej kolejności zostaną wypisane permutacje dla n=3, jeśli stosujemy opisaną wyżej metodę rekurencyjnie?

Na szczęście istnieją algorytmy, które potrafią wypisać na bieżąco, kolejno tworzone permutacje, bez konieczności ich pamiętania. Przykładem niech będzie algorytm permutacje przedstawiony poniżej, por. R. Sedgewick, Algorithms, Addison Wesley Pub. 1983. W algorytmie tym permutacje są tworzone w tablicy tab[0:n] na pozycjach od 1 do n. Pozycja tab[0] jest pomocnicza. Generowanie permutacji odbywa się za pomocą rekurencyjnej procedury generuj, która dla danego k wypisuje wszystkie permutacje z ustaloną wartością now+1 na pozycji k-tej.

Chociaż problem wykorzystania pamięci został w tym algorytmie pomyślnie rozwiązany (ale uwaga na stos rekurencyjnych wywołań), to jednak koszt algorytmu nadal jest rzędu n!. Rozwiązaniem problemu permutacji jest przecież ciąg złożony z n! ciągów. Nie powinniśmy się dziwić, że wymaga to sporo czasu, bo nawet dla n=16, liczba n! jest olbrzymia ( 16! > 2⁵⁰). 

Trudno nazwać przedstawione tu algorytmy rozsądnymi.  Uznajmy więc, że rozsądne będą te algorytmy, dla których koszt czasowy realizacji jest wielomianowy. Każdy algorytm możemy więc zaklasyfikować do jednej z dwu klas tak jak na rysunku 15.1.

Linia prosta na tym rysunku ma symbolizować granicę podziału. Ale w rzeczywistości granica między tym co rozsądne i nierozsądne nie jest wcale oczywista. Rozważmy następujący przykład.

Przykład 1.1

Przypuśćmy, że mamy dwa algorytmy rozwiązujące ten sam problem: pierwszy, A1, o koszcie O(n¹⁰⁰) i drugi, A2, o koszcie O(2ⁿ). Który z nich wybrać? Algorytm A1 jest wielomianowy, a zatem "rozsądny", zgodnie z klasyfikacją na rysunku 15.1 Natomiast algorytm A2 jest algorytmem wykładniczym i nie chcemy, "z zasady", uznać go za rozsądny. Tymczasem  dla bardzo wielu n, algorytm A2 wygrywa w czasie z algorytmem A1. Wynika stąd, że granica między tym co rozsądne i możliwe do zastosowania, a tym czego w praktyce nie da się zastosować jest dość nieostra. J

Pytanie 3: Czy algorytm Dijkstry znajdowania najkrótszej ścieżki  z ustalonego źródła w grafie zorientowanym z dodatnimi wagami należy do algorytmów "rozsądnych" w naszej klasyfikacji? 

« poprzedni punkt

następny punkt »