Algorytm efektywny otrzymujemy często startując od prostszego, ale mało efektywnego algorytmu.
Następnie staramy się za pomocą prostych transformacji przekształcić prosty algorytm w algorytm docelowy. Można to również nazwać stosowaniem metody kolejnych przybliżeń w aspekcie inżynierii algorytmicznej. Czasami można to (w przenośni algorytmicznej) nazwać chirurgią algorytmiczną, ponieważ możemy amputować chore lub zbędne tkanki algorytmu, aby go usprawnić. Czasami, zamiast amputacji, potrzebne jest wzmocnienie algorytmu poprzez doszycie pewnej dodatkowej części (np. funkcji buty siedmiomilowe, funkcji większy-biceps lub czaso-przyspieszacz). Oczywiście w chirurgii zdarzają się pomyłki i można doszyć to, czego nie należałoby doszywać, np. funkcję czaso-wstrzymywacz. Słaba kondycja algorytmu może mieć przyczyny niezwiązane z chirurgią, np. nadwaga algorytmiczna, lub tzw. połknięcie paradygmatu. Istotna jest również prostota algorytmu. Stosując zbyt wiele transformacji i udziwnień, możemy przerobić algorytm, który jest naiwny, ale zrozumiały, w genialny algorytm, który jest zdziwaczały i niezrozumiały. Algorytm, który stracił zdrowy rozsądek, może być świetnym wynikiem teoretycznym, może być nawet przedmiotem podziwu w sensie artystycznym, ale jego praktyczne stosowanie może być niewielkie (nie dotyczy to dydaktyki).
Większość prostych algorytmów z wykładu Wstęp: poprawność i złożoność algorytmów można potraktować jako produkty transformacji algorytmów naiwnych. Pokazanie tego pozostawiamy jako ćwiczenie. Pokażemy teraz dwa proste przykłady transformacji.
Mając dane dwie posortowane rosnąco tablice \( A[1..n], B[1..n] \), należy wyznaczyć liczbę (inwersji) par \( i,j \) takich, że \( A[i]>B[j] \). Liczbę inwersji między tablicami \( A \), \( B \) oblicza następujący naiwny algorytm:
Algorytm Liczba-Inwersji-Naiwnie
wynik := 0; for i := 1 to n do j:= 0; while j < n and A[i] > B[j+1] do j := j+1; wynik := wynik + j;
Algorytm ma złożoność kwadratową. Załóżmy, że początkową wartością \( j \) jest zero. Wtedy przyglądając się dokładniej algorytmowi widzimy, że bez szkody dla poprawności instrukcję \( j := 0; \) można przesunąć przed pętlę for i złożoność stanie się liniowa. Dowód pozostawiamy jako ćwiczenie. W ten sposób mamy prostą transformację kwadratowego algorytmu naiwnego na algorytm liniowy.
Przykład ten był dosyć ubogi i dlatego przedyskutujemy dodatkowo bardziej skomplikowany przykład. Podamy transformację pewnego prostego algorytmu \( B(n) \) w nietrywialny algorytm \( A_n \). Transformacja ta bazuje na własnościach \( B(n) \). Kluczem do efektywnej transformacji jest analiza własności algorytmu \( B(n) \).
Mamy zbiór monet o numerach 1,2,..,N, wszystkie o tej samej wadze, i wiemy że wśród nich jest dokładnie jedna fałszywa moneta o innej wadze. Modelem algorytmu jest ciąg ważeń na wadze szalkowej. Niech waga(A) oznacza sumę wag monet ze zbioru A. W jednym ważeniu możemy wykonać operację Porównaj(A,B), gdzie A,B są rozłącznymi podzbiorami zbioru \( \{ 1,2,\ldots,N\} \). Otrzymujemy jedną z trzech możliwych odpowiedzi:
Algorytmem w naszym modelu jest ciąg operacji \( op_1, op_2,..., op_n \) taki, że z otrzymanego ciągu odpowiedzi można jednoznacznie wyznaczyć fałszywą monetę i określić, czy jest ona cięższa czy lżejsza niż inne. Operację Porównaj(A,B) będziemy w skrócie zapisywać jako parę (A,B). Nasz algorytm można zatem zapisać jako ciąg par rozłącznych zbiorów, na przykład:
Algorytm dla n=2, N=3: ({1}, {2}), ({1}, {3})
Algorytm dla n=3, N=12: ({1,2,3,10},{4,5,6,11}), ({1,2,3,11},{7,8,9,10}), ({1,4,7,11},{2,5,8,12})
Naszym głównym zadaniem jest dla danego n znalezienie algorytmu ważeń, który maksymalizuje N.
Pokażemy najpierw, jak rozwiązać zadanie dla \( N=3^{n-1} \). Załóżmy, że liczba monet jest potęgą trójki i monety są ponumerowane \( 0,1,2.. 3^{n}-1 \) . Niech S(k,0), S(k,1) oznaczają zbiory numerów monet, które na k-tym bicie (licząc od końca) w reprezentacji trójkowej mają odpowiednio 0, 1. Gdybyśmy wiedzieli od razu, czy fałszywa moneta jest lżejsza czy cięższa, to mamy następujący prosty algorytm, który działa podobnie jak wyszukiwanie ternarne:
\( (S(1,0), S(1,1)), (S(2,0),S(2,1)), ... (S(n,0),S(n,1)) \)
Ponieważ nie znamy statusu fałszywej monety, dodajemy jedno porównanie i otrzymujemy algorytm B(n), który obsługuje za pomocą n ważeń \( N = 3^{n-1} \) monet (mamy teraz tylko n-1 bitów ternarnych).
\( B(n)= (S(1,0),S(1,2)), (S(1,0),S(1,1)), ... (S(n-1,0),S(n-1,1)) \)
Dzięki dodaniu na początku jednego ważenia, już po pierwszych dwóch ważeniach wiemy, jaki jest status fałszywej monety (lżejsza, cięższa). Poza tym wynikiem pierwszych dwóch ważeń nie może być LP ani PL. Te dwie własności algorytmu B(n) są kluczem do transformacji tego algorytmu w algorytm \( A_n \).
Jeśli mamy w naszym modelu algorytmy
\( A1(n) = (A_1,B_1),(A_2,B_2)...(A_{n},B_{n}) \) oraz \( A2(n) = (C_1,D_1),(C_2,D_2)...(C_{n},D_{n}) \),
to definiujemy algorytm
\( A1 \cup A2 = (A_1 \cup C_1, B_1 \cup D_1), (A_1 \cup C_2, B_2 \cup D_2) ... (A_n \cup C_n, B_n \cup D_n) \)
Załóżmy, że mamy algorytm \( A_{n-1} = (A_1,B_1),(A_2,B_2)...(A_{n-1},B_{n-1}) \) na zbiorze rozmiaru \( N_{n-1} \) i oznaczmy przez \( przeskaluj(A_{n-1}) \) algorytm, który działa na zmodyfikowanych numerach monet: do każdego numeru dodajemy \( 3^{n-1} \). Ponadto dodajemy jedno porównanie:
Docelowy algorytm definiujemy rekurencyjnie:
\( A_n= przeskaluj(A_{n-1}) \cup B(n) \)
Poprawność takiej konstrukcji wynika stąd, że na podstawie wyników dwóch pierwszych ważeń wiemy, czy fałszywa moneta jest mniejsza od \( 3^{n-1} \). Jeśli tak, to traktujemy odpowiedzi jak w B(n), jeśli nie, to jak w A(n-1). Zostawiamy jako ćwiczenie opisanie sposobu takiego przełączania się.
W ten sposób mamy algorytym, który za pomocą n ważeń obsługuje \( N_n \) monet, gdzie
\( N_2=3; N_n=3^{n-1}+N_{n-1} \)
Dla n = 2,3,4,5,6,7 mamy więc: \( N_n = 3, 12, 39, 120, 363, 1092 \).
Teoretycznie interesujące w tym jest to, że są to maksymalne wartości N. Pozostawiamy dowód jako ćwiczenie. Istnieją różne optymalne algorytmy dla tego problemu. Wzór rekurencyjny na liczbę monet można zapisać również w postaci
\( N_2=3; N_n=3*N_{n-1}+3 \).
Na podstawie tego wzoru można otrzymać drugi algorytm, który pozostawiamy jako ćwiczenie. Jest jeszcze następujący zwarty wzór, z którego wynika trzeci algorytm rozwiązujący problem bezpośrednio (bez rekursji)
\( N_n=(3^{n}-3)/2 \).
Na razie byliśmy zainteresowani głównie zmaksymalizowaniem liczby \( N_n \) oraz ogólną strukturą algorytmów ważenia. Pozostawiamy jako ćwiczenie pokazanie, że wszystkie trzy powyższe algorytmy można zaimplementować tak, aby wypisywały one na wyjściu odpowiadającą im ciągi ważeń w czasie liniowym ze względu na rozmiar wyjścia.