Algorytmy i struktury danych/Wstęp: elementarne techniki algorytmiczne i struktury danych

W tym drugim, wstępnym module opiszemy nieformalnie kilka podstawowych technik algorytmicznych i elementarnych struktur danych. Niektóre z nich były wstępnie omawiane na kursie Metody programowania. Teraz rozważymy je przede wszystkim w aspekcie złożoności obliczeniowej i analizy algorytmów.

Metoda dziel i zwyciężaj

Metoda ta polega na podzieleniu problemu na podproblemy, które rozwiązujemy niezależnie, a następnie "scalamy". Metoda działa dobrze, gdy "scalanie" podproblemów jest łatwe, oraz same podproblemy są "małe" w stosunku do rozmiaru problemu $n$.

Jako przykład rozważmy jeszcze raz problem wyznaczenia przywódcy tablicy (patrz Wstęp: poprawność i złożoność algorytmów.). Stosując metodę dziel i zwyciężaj, możemy otrzymać następujący algorytm:

Algorytm Rekurencyjny Przywódca

---

1   if $n=1$ then przywódcą jest pojedynczy element tablicy
2   else 
3       podziel tablicę na dwie połowy;
4       rekurencyjnie oblicz przywódcę lewej i prawej połowy tablicy;
5       sprawdź w czasie $O(n)$, który z nich jest przywódcą całości

Jeśli algorytm ten wykonuje $T(n)$ kroków, to:

$T(n)\ =\ T(\lfloor {\frac {n}{2}}\rfloor )+T(\lceil {\frac {n}{2}}\rceil )+O(n),\ T(1)=1$

Rozwiązaniem jest $T(n)=O(n\log n)$ (jak wiadomo z kursu matematyki dyskretnej).

Metoda zachłanna

Metoda ta dobrze działa w sytuacjach, gdy maksymalizujemy lub minimalizujemy pewną wartość. Algorytm w każdej iteracji ma do wyboru pewną liczbę "lokalnych" akcji. W przypadku maksymalizacji wybiera tę, która lokalnie maksymalizuje wartość docelową. W przypadku minimalizacji wybiera akcję o minimalnej wartości. Przedyskutujemy tę metodę na następujących dwóch przykładach.

Wieże na szachownicy

Przypuśćmy, że mamy szachownicę $n$ na $n$, na polu $(i,j)$-tym leży $x(i,j)$ monet. Chcemy umieścić $n$ wież na szachownicy tak, aby żadne dwie się nie atakowały. Zyskiem jest suma monet na wybranych pozycjach. Lokalna akcja to wybranie jednej dopuszczalnej pozycji. Zysk akcji to liczba monet na pozycji. Algorytm zachłanny działa trywialnie: wybieramy pozycję z maksymalnym $x(i,j)$. Można łatwo zobaczyć, że ten algorytm niekoniecznie da optymalny zysk - da jednak co najmniej połowę optymalnego zysku. Pozostawiamy to jako ćwiczenie. Bardziej formalnie można wyrazić ten problem w terminach skojarzeń w grafach. Najciekawszym przypadkiem jest sytuacja, gdy tablica $x(i,j)$ jest zerojedynkowa.

Minimalne Sklejanie Par

Przypuśćmy, że mamy ciąg $n$ nieujemnych liczb $p_{1},p_{2},\ldots ,p_{n}$. Lokalna akcja sklejania polega na pobraniu dwóch elementów z ciągu i zastąpieniu ich przez sumę ich wartości. Kosztem akcji jest suma wartości "sklejanych" elementów. Ciąg operacji sklejania kończy się, gdy skleiliśmy wszystko do jednej wartości.

Interesuje nas obliczenie minimalnego sumarycznego kosztu sklejania $n$ elementów w jeden element. Metoda zachłanna zawsze wybiera akcję o minimalnej wartości.

Algorytm Schemat-Zachłanny

---

1   while zbiór możliwych lokalnych akcji jest niepusty do
2      wykonaj akcję o minimalnym koszcie;
3   return suma kosztów wykonanych akcji;

<flash>file=Sklejanie_par.swf|width=550|height=400</flash>

Można to zapisać bardziej formalnie:

Algorytm Optymalne-Sklejanie-Par

---

1   $wynik:=0$;
2   while mamy co najmniej dwa elementy do
3      zastąp dwa najmniejsze elementy $a,b$ przez $a+b$
4      $wynik:=wynik+a+b;$

Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten wyznacza ciąg sklejeń o najmniejszym koszcie. Co będzie, jeśli zamiast obliczać minimalny koszt chcielibyśmy wyznaczyć ciąg, który maksymalizuje sumaryczny koszt? Pozostawiamy to jako ćwiczenie. Algorytm ten jest "szkieletem" efektywnego konstruowania tzw. "drzewa Huffmana".

W naszym przykładzie mogliśmy sklejać elementy, które niekoniecznie są sąsiednie, kolejność elementów w ciągu nie odgrywała roli. Zastanówmy się, co będzie, gdy wprowadzimy do gry kolejność elementów. Załóżmy teraz, że możemy sklejać tylko elementy sąsiednie. Tak zmodyfikowany problem nazwijmy problemem Minimalnego Sklejania Sąsiadów. Możemy w poprzednim algorytmie zastąpić zwrot "dwa najmniejsze elementy" przez "dwa sąsiednie elementy o minimalnej sumie".

Niespodziewanie, nasz algorytm nie zawsze oblicza minimalną wartość, czyli nie jest poprawny. Kontrprzykładem jest ciąg

$(p1,p2,p3,p4)=(100,99,99,100).$

Programowanie dynamiczne

Rozwiązaniem danego problemu często jest kombinacja rozwiązań podproblemów, na które można problem rozłożyć. Natomiast nie od razu wiemy, jaka dekompozycja jest optymalna; początkowo mamy niedeterministyczny wybór wielu różnych dekompozycji. W sytuacji, gdy nie wiemy, jaka dekompozycja jest optymalna, nie możemy uruchomić rekursji, ponieważ na każdym etapie mielibyśmy wiele wyborów i w sumie złożoność mogłaby być wykładnicza.

W takich sytuacjach stosujemy metodę zwaną programowaniem dynamicznym. Metoda ta, z grubsza biorąc, wygląda następująco: Jeśli problem możemy rozbić na podproblemy i liczba wszystkich potencjalnych podproblemów jest wielomianowa, to zamiast korzystać z rekursji możemy obliczyć wartości wszystkich podproblemów stosując odpowiednią kolejność: od "mniejszych" podproblemów do "większych". Rozmiary problemów muszą być odpowiednio zdefiniowane, nie powinno być zależności cyklicznej.

Wartości obliczone dla podproblemów zapamiętujemy w tablicy. Mając obliczone wartości podproblemów, na które można rozbić dany problem, wartość problemu obliczamy korzystając z wartości zapamiętanych w tablicy.

Najistotniejsze jest tutaj określenie zbioru potencjalnych podproblemów. Z reguły zbiór ten jest znacznie większy niż zbiór podproblemów będących częściami jednego optymalnego rozwiązania.

Spróbujmy skonstruować wielomianowy algorytm dla problemu minimalnego sklejania sąsiadów korzystając z programowania dynamicznego. Jeśli mamy dany ciąg $p_{1},p_{2},\ldots p_{n}$, to w tym przypadku podproblem można utożsamić z pewnym przedziałem $[i..j]$. Niech $wynik[i,j]$ będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu $(p_{i},p_{i+1},\ldots p_{j})$;

oznaczmy ponadto

$\sigma _{i,j}\ =\ \sum _{k=i}^{j}\ p_{k}$

Algorytm Optymalne-Sklejanie-Sąsiadow

---

1   for $i:=1$ to $n$ do $wynik[i,i]:=0;$
2   for $j:=2$ to $n$ do
3      for $i:=j-1$ downto $1$ do
4         $wynik[i,j]:=\min _{i\leq k<j}\ (wynik[i,k]+wynik[k+1,j]+\sigma _{i,j})$

5   return $wynik[1,n]$;

W algorytmie zasadniczą instrukcję

$wynik[i,j]:=\min _{i\leq k<j}\ (wynik[i,k]+wynik[k+1,j]+\sigma _{i,j})$

można wykonywać w dowolnym przyzwoitym porządku ze względu na (i,j) (na przykład po przekątnych, zaczynając od głównej przekątnej). Przyzwoitość polega na tym, że jest już ostatecznie policzone to, z czego w danym momencie korzystamy.

Algorytm ma złożoność czasową $O(n^{3})$ i jest to "typowa" złożoność algorytmów tego typu. Duża złożoność wynika stąd, że liczymy wartości dla mnóstwa podproblemów, które mogą być zupełnie nieistotne z punktu widzenia optymalnego rozwiązania.

Dygresja

Problem sklejania sąsiadów można rozwiązać inaczej, modyfikując w sposób nietrywialny algorytm Optymalne-Sklejanie-Par. W algorytmie tym instrukcję

zastąp dwa najmniejsze elementy $a,b$ przez $a+b$

zamieńmy na:

zastąp dwa sąsiednie elementy $a,b$ o minimalnej sumie przez $a+b$
przesuń $a+b$ przed najbliższy na prawo (w ciągu) element $c$ większy od $a+b$
(na koniec ciągu, jeśli takiego $c$ nie ma)

Otrzymany algorytm (wersja algorytmu Garsia-Wachsa) liczy koszt minimalnego sklejania sąsiadów. Jest to przykład pozornie prostego algorytmu, dla którego odpowiedź na pytanie, "dlaczego to działa" jest niezwykle skomplikowana i wykracza poza zakres tego kursu. Pozostawiamy jako ćwiczenie implementację tego algorytmu w czasie $O(n\log n)$, przy założeniu, że jest on poprawny. Jeśli liczby $p_{i}$ są liczbami naturalnymi z przedziału $[1..n]$, to istnieje nawet (bardzo trudna) implementacja w czasie liniowym.

Konstruowanie algorytmu metodą transformacji

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.

Liczba inwersji

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

---

1  $wynik:=0;$
2  for $i:=1$ to $n$ do 
3     $j:=0;$
4     while $j<n$ and $A[i]>B[j+1]$ do $j:=j+1;$
5     $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)$.

Wykrywanie fałszywej monety

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:

• L - gdy waga(A)<waga(B)
• P - gdy waga(A)>waga(B)
• R - gdy wagi są równe.

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:

$przeskaluj(A_{n-1})=(B1,A1),(A1,B1),(A2,B2),...(A_{n-1},B_{n-1})$

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,117,351,1053$.

Dygresja

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.

Znaczenie struktury danych

Podstawową strukturą danych jest struktura "obsługująca" operacje Delete(x,S), Insert(x,S), dla zadanego zbioru S. Operacja delete pobiera z S i zwraca jako wartość "pewien" element S. Nie interesuje nas na razie, który element zostanie usunięty. Niedeterminizm pozwala nam użyć w takim wypadku jednej z kilku struktur danych, które omawiamy poniżej. W niektórych zastosowaniach istotne jest, który element jest pobierany, i wtedy nazwy operacji Insert i Delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie tym strukturom. Będziemy jednak też używać nazewnictwa Delete, Insert, o ile nie prowadzi to do niejednoznaczności. Elementarne struktury danych, w których określone są operacje Insert, Delete, to:

• lista,
• stos,
• kolejka.

Są one punktem wyjścia do bardziej skomplikowanych struktur, w szczególności różnego typu drzew.

Prosty przypadek kolejki priorytetowej

Wariantem kolejki jest kolejka priorytetowa typu min. Jest to struktura danych, która "obsługuje" ciąg operacji insert, delete, gdzie operacja delete zawsze pobiera minimalny (maksymalny) element. Operację tę nazwiemy w tym przypadku DeleteMin (DeleteMax). Operacja delete jest tutaj w dużym stopniu zdeterminowana.

Załóżmy, że ciąg operacji Insert można podzielić na dwa ciągi następujące po sobie; w każdym z nich w operacji Insert wstawiamy elementy w porządku rosnącym. Wtedy kolejkę priorytetową można łatwo zaimplementować tak, by operacje Insert, Delete można było wykonać w czasie stałym.

Pokażemy na przykładzie algorytmu Optymalne-Sklejanie-Par zastosowanie tego typu kolejki priorytetowej. W algorytmie tym podstawową operacją jest:

zastąp dwa minimalne elementy $a,b$ przez $a+b$.

Operacja ta jest równoważna operacjom:

$a=DeleteMin(S)$; $b=DeleteMin(S)$; $Insert(a+b,S)$;

W szczególnym przypadku, rozważonym poniżej, operacje Insert, DeleteMin można zaimplementować w czasie stałym. Załóżmy, że początkowy zbiór $S$ jest posortowany i jego elementy są umieszczone na stosie $ST$ w kolejności rosnącej (od szczytu "w dół"). Załóżmy, że mamy dodatkowo zwykłą kolejkę $Q$ początkowo pustą. Wtedy ciąg operacji

$a=DeleteMin(S)$; $b=DeleteMin(S)$; $Insert(a+b,S)$

możemy wykonać w czasie stałym: element minimalny jest na wierzchołku $ST$ lub na początku kolejki $Q$, element $a+b$ wstawiamy na koniec $Q$. Zatem algorytm Optymalne-Sklejanie-Par możemy zaimplementować w czasie liniowym, gdy początkowy zbiór jest od razu posortowany. Widzimy na tym przykładzie, w jaki sposób złożoność algorytm zależy od struktury danych związanych z algorytmem.

W następujących dwóch przykładach możemy sobie pozwolić na niedeterministyczny wariant operacji Delete.

Maksymalna bijekcja

Przypuśćmy, że mamy funkcję $f:\{1,2,\ldots n\}\rightarrow \{1,2,\ldots n\}$, zadaną tablicą $f[1..n]$, i chcemy znaleźć rozmiar maksymalnego podzbioru, na którym ta funkcja jest bijekcją.

Dwie funkcje

Jest to zadanie bardzo podobne. Mamy dwie częściowo określone funkcje $f_{1},f_{2}$ ze zbioru $[1..n]$ w siebie. Chcemy znaleźć taką permutację $\pi =(i_{1},i_{2},\ldots i_{n})$, żeby $\pi (f_{k}(i))>\pi (i),\forall \ 1\leq i\leq n,\ k=1,2$, jeśli $f_{k}(i)$ określone.

Oba te przykłady możemy wyrazić w terminach teorii grafów. Zbiorem wierzchołków jest tutaj zbiór $[1..n]$. W pierwszym przykładzie krawędzie są postaci $(i,f(i))$, w drugim postaci $(i,f_{k}(i)$, gdzie $k=1,2$.

W pierwszym przykładzie chcemy znaleźć maksymalny podzbiór grafu, na którym podgraf indukowany jest zbiorem cykli.

W drugim przypadku mamy szczególny przypadek tzw. sortowania topologicznego grafu. Wierzchołek nazywamy roboczym, gdy nie wchodzi do niego żadna krawędź. Niech $S$ będzie początkowo zbiorem wszystkich wierzchołków roboczych. Algorytmy dla obu powyższych problemów działają w podobny sposób. Pobieramy element $v\in S$, odpowiednio przetwarzamy i usuwamy z grafu. Wskutek usunięcia $v$ pewne nowe wierzchołki stają się roboczymi i wstawiamy je do S. Kontynuujemy, dopóki S jest niepusty.

W przypadku problemu maksymalnej bijekcji po prostu usuwamy $v$, a w przypadku numeracji $\pi$ $\pi (v)$ staje się kolejnym numerem. Pomimo interpretacji teorio-grafowej nie musimy implementować żadnej reprezentacji grafu: wszystko się dzieje w wejściowych tablicach i w dodatkowej tablicy licznik[v], w której trzymamy dla każdego $v$ liczbę krawędzi aktualnie wchodzących do $v$. Konkretną implementację pozostawiamy jako ćwiczenie. Zbiór S jest tutaj zbiorem wierzchołków roboczych, które są w pewnym sensie akcjami do wykonania. Do S wkładamy akcje, które mamy wykonać; kolejność nie jest istotna. S może być listą, stosem lub kolejką.

Panorama Warszawy

Rozważmy inny przykład algorytmu, którego złożoność istotnie zależy od (bardzo prostej) struktury danych (lista jednokierunkowa, która się zamienia w drzewo skierowane w strone korzenia).

Przypuśćmy, że mamy na wejściu $n$ trójek postaci $[p,q,s]$, gdzie $p,q\in \{1,2,\ldots ,n\},s\geq 0$. Każdej trójce odpowiada funkcja $f_{p,q,s}$ taka, że:

$f_{p,q,s}(i)\ =\ s$, gdy $p\leq i\leq q$, oraz $f_{p,q,s}(i)\ =\ 0$ w przeciwnym przypadku.

Naszym zadaniem jest dla każdego $1\leq i\leq n$ obliczyć wartość $F(i)$ będącą maksimum z danych funkcji $f_{p,q,s}$ dla argumentu $i$. Można podać następującą interpretację. Każda funkcja $f_{p,q,s}$ opisuje kształt wieżowca w Warszawie patrząc z prawej strony Wisły. Wtedy funkcja $F$ opisuje panoramę centrum Warszawy.

Załóżmy, że trójki $(p,q,s)$ są posortowane ze względu na $s$. Wtedy rozważamy kolejno funkcje $f_{p,q,s}$ w kolejności rosnącego $s$ i nadajemy za każdym razem końcowe wartości dla pozycji z przedziału $[p,q]$, dla których jeszcze wartości nie są obliczone. Taki algorytm miałby złożoność kwadratową.

Początkowo elementy trzymamy w liscie jednokierunkowej, element i-ty wskazuje na (i+1)-szy dla i<n+1. Element n na n+1. Zakładamy więc, że mamy na przykład tablice NEXT taką, że NEXT[i]=i+1, dla i<n+1, NEXT[n+1]=n+1, oraz początkowo Wynik[i]=0 dla każdego i. Trójki trzymamy w trzech tablicach, i-ta trójka jest dana przez P[i], Q[i], S[i]. Nasze podstawowe założenie:

tablica S jest posortowana malejąco

Jeśli przetwarzamy w kolejnej iteracji przedział $[p,q]$, to zaczynamy od elementu p i poruszamy się na liście dopóki nie przekroczymy q, w tym momencie jesteśmy w jakimś elemencie r. Wszystkie elementy, które przeglądaliśmy, zmieniają swoje dowiązanie na r. W pewnym sensie możemy powiedzieć, że kompresujemy ścieżkę, którą przeszliśmy. Koszt iteracji to, z grubsza, długość ścieżki (liczba dowiązań, które się zmieniły). Z listy jednokierunkowej robi nam się drzewo jednokierunkowe.

Algorytm Panorama-Warszawy1

---

1  for $i:=1$ to n do 
2         $j:=P[i];$
3         while $j\leq Q[i]$  do 
4             $Wynik[j]\ :=\ \max(Wynik[j],S[i]);$
5             $j:=NEXT[j];$
*
6       Kompresja ścieżki:
*  
7           $k:=P[i];$
8          while $k<j$  do 
9             $pom:=NEXT[k];NEXT[k]:=j;k:=pom;$

Algorytm ten powstał w ten sposób, że do algorytmu naiwnego doszyliśmy dodatkową część: Czaso-Przyspieszacz.

Dosyć łatwo pokazać, że czas tego algorytmu będzie rzędu co najwyżej $n^{3/2}$, a więc lepszy niż algorytmu naiwnego. Jeśli "kompresujemy" ścieżkę długości k (w części Czaso-Przyspieszacz), to zmniejszamy sumaryczną odległość elementów do korzenia (elementu n) o wielkość co najmniej taką, jak suma liczb 1,2,3..,k, a więc mniej więcej o $k^{2}$. Początkowa suma jest rzędu $n^{2}$. Za każdym razem zmniejszamy tę sumę o kwadrat kosztu danej iteracji.

Jeśli mamy n liczb, których kwadraty w sumie dają $n^{2}$, to suma tych liczb jest co najwyżej $n^{3/2}$. Zapisując bardziej matematycznie:

$a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+\ldots a_{n}^{2}\leq n^{2}\ \Rightarrow \ a_{1}+a_{2}+a_{3}+\ldots a_{n}\leq n\cdot {\sqrt {n}}$

Podobne algorytmy poznamy w module o problemie find-union, wtedy też będziemy mogli lepiej zanalizować algorytm rozwiązujący problem Panoramy.

Rozważmy jeszcze przypadek (nazwijmy go "specjalnym"), gdy wszystkie przedziały odpowiadające wejściowym funkcjom maja wspólne przecięcie teorio-mnogościowe. Nazwijmy ten przypadek specjalnym. Wtedy mamy bardzo prosty algorytm działający w czasie liniowym.

Algorytm Panorama-Warszawy2

---

1  $lewy:=Q[1]+1;prawy:=Q[1];$

2  for $i:=1$ to n do 
3         for $j:=lewy-1$ downto P[i] do 
4             $Wynik[j]\ :=\ \max(Wynik[j],S[i]);$
5         for $j:=prawy+1$ to Q[i] do 
6             $Wynik[j]\ :=\ \max(Wynik[j],S[i]);$

7        $lewy:=min(lewy,P[i]),prawy:=max(prawy,Q[i]);$

Dlaczego przypadek specjalny jest interesujący? Otóż wykorzystując algorytm dla tego przypadku, możemy łatwo otrzymać algorytm typu dziel i zwyciężaj działający w czasie $O(n\log n)$.

Podzielmy przedział [1..n] na dwie połowy. Rozważmy najpierw tylko te wieżowce, których przedziały są całkowicie w lewej części. Stosujemy do nich algorytm rekurencyjny. Podobnie robimy dla prawej połowy. Zostają nam jeszcze wieżowce, których przedziały mają punkty wspólne z obu połówkami, a to jest właśnie przypadek specjalny, który rozwiązaliśmy w prosty sposób.

Pomimo tego wydaje się, że algorytm Panorama-Warszawy1 jest znacznie prostszy, gdyż nie wymaga rekursji ani specjalnych przypadków.

Sortowanie kolejkowe i stosowe

Działanie stosu i kolejki świetnie ilustrują różne warianty problemu sortowania z użyciem stosów i kolejek. Niech $\pi$ będzie permutacją liczb $\{1,2,\ldots n\}$. Możemy posortować $\pi$ stosując niedeterministyczny algorytm:

while na wyjściu nie są wypisane wszystkie elementy do
   wykonaj dokładnie jedną z trzech instrukcji:
     (1) wstaw kolejny element $\pi (i)$ do jednej z kolejek; i=i+1
     (2) lub wypisz $\pi (i)$ na wyjściu; i=i+1 
     (3) lub pobierz i wypisz na wyjściu pierwszy element jednej z kolejek

Zdefiniujmy liczbę kolejkową permutacji $\pi$ jako minimalną liczbę kolejek potrzebnych do posortowania permutacji $\pi$. Na przykład dla $\pi =(1,2,3)$ liczba ta wynosi 0, a dla $\pi =(3,2,1)$ wynosi 2.

Jak wyznaczyć liczbę kolejkową w czasie liniowym? Porównajmy ten problem z problemem maksymalnego malejącego podciągu. Pozostawiamy to jako ćwiczenie.

Podobnie definiujemy liczbę stosową. W tym wypadku w powyższym nieformalnym algorytmie zastępujemy kolejkę przez stos. Można również zdefiniować liczbę kolejkowo-stosową, pytając o minimalną liczbę stosów i kolejek, które razem posortują daną permutację. Jest to trudne pytanie.

W poprzedniej wersji sortowania każdy element może trafić tylko do jednej kolejki. Rozważmy teraz wersję, w której mamy $k$ kolejek $Q_{1},Q_{2},Q_{3},\ldots Q_{k}$ i element może trafiać do kolejek o coraz mniejszych numerach.

Pojedyncza operacja polega na wstawieniu kolejnego elementu z $\pi$ do jednej z kolejek, wypisaniu bezpośrednio na wyjście, o ile jest on pierwszym niepobranym elementem w $\pi$ lub pierwszym elementem pewnej kolejki, albo przełożeniu pierwszego elementu pewnej kolejki $Q_{i}$ do kolejki $Q_{j}$ dla $j<i$.

Można pokazać, że do posortowania każdej permutacji wystarczy logarytmiczna liczba kolejek.

Podobny fakt zachodzi, gdy kolejki zastąpimy stosami. Pozostawiamy ten problem (zarówno dla kolejek jak i dla stosów) jako ćwiczenie.

Sortowanie kolejkowe

Załóżmy, że każdy element ciągu $\pi$ jest początkowo listą jednoelementową. Oznaczmy zbiór tych list przez $S$. Załóżmy też, że umiemy scalić dwie posortowane listy w czasie proporcjonalnym do sumy ich długości za pomocą operacji merge (patrz następne wykłady).

Algorytm Sortowanie-Kolejkowe-1

---

1  while $|S|>1$ do 
2       $lista1:=delete(S);lista2:=delete(S);$
3       $insert(merge(lista1,lista2),S)$

Pozostawiamy jako ćwiczenie pokazanie tego, że jeśli S jest kolejką, to algorytm ten działa w czasie $O(n\log n)$, a jeśli $S$ jest stosem, to algorytm działa w czasie kwadratowym. Widać na tym przykładzie przewagę kolejki nad stosem. Załóżmy, że mamy posortować tablicę $A[0,1,\ldots ,n-1]$ i $n$ jest potęgą dwójki. Wtedy następujący algorytm wykonuje ten sam ciąg scaleń co algorytm Scalanie-Kolejkowe. Dowód tego pozostawiamy jako ćwiczenie.

Algorytm Sortowanie-Kolejkowe-2

---

Scalanie-Kolejkowe bez kolejki
1  $m:=1;$
2  while $m<n$ do
3     for $i:=0$ to $n/(2m)$ do
4        $merge(A[i..i+m-1],A[i+m..i+2m-1]);$
5     $m:=2m;$