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

Nie ma formalnej teorii ani gotowych "recept" na konstrukcję efektywnych algorytmów. Opiszemy nieformalnie kilka podstawowych technik. Niektóre z nich są wstępnie omawiane na kursie metod programowania. Tutaj 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 podproblemy są "małe" w stosunku do rozmiaru problemu $n$ .

Jako przykład rozważmy jeszcze raz problem wyznaczenia przywódcy tablicy (patrz Moduł 1. 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 begin
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
6   end;

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

T (n) = T (⌊ \frac{n}{2} ⌋) + T (⌈ \frac{n}{2} ⌉) + 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 (tzn. takiej, że wieża umieszczona na tej pozycji nie atakuje żadnej wieży umieszczonej dotychczas. Zysk akcji to liczba monet na pozycji. Algorytm zachłanny działa trywialnie: wybieramy pozycję z maksymalnym x(i,j). Łatwo widać, że ten algorytm niekoniecznie da optymalny zysk, ale da 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 zero-jedynkowa.

Przejdziemy teraz do wersji minimalizacyjnej.

Minimalne Sklejanie Par

Przypuśćmy, że mamy ciąg $n$ nieujemnych liczb $p_{1}, p_{2}, \dots, 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    $w y n i k : = 0$ ;
2   while mamy co najmniej dwa elementy do begin
3      zastąp dwa minimalne elementy a,b przez a+b
4       $w y n i k : = w y n i k + a + b;$ 
5   end

Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten daje minimalny ciąg sklejeń. Co będzie, jeśli zamiast obliczać minimalny koszt chcielibyśmy wyznaczyć ciąg, który maksymalizuje sumaryczny koszt? Pozostawiamy to jako ćwiczenie.

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 minimalne 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

(p 1, p 2, p 3, p 4) = (100, 99, 99, 100)

Programowanie dynamiczne

Rozwiązaniem danego problemu często jest kombinacja wartości podproblemów na które można problem rozłożyć. Natomiast nie bardzo 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. Przykładem jest rekurencyjne liczenie liczb Fibonacciego.

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. 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ść tego 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}, \dots p_{n}$ , to w tym przypadku podproblem można utożsamić z pewnym przedziałem $[i . . j]$ . Niech $w y n i k [i, j]$ będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu $(p_{i}, p_{i + 1}, \dots p_{j})$ ;

oznaczmy ponadto

σ_{i, j} = \sum_{k = i}^{j} p_{k}

Algorytm Optymalne-Sklejanie-Sąsiadow

1   for  $i : = 1$  to n do  $w y n i k [i, i] : = 0;$ 
2   for  $i : = 1$  to n do
3      for  $j : = i + 1$  to n do
4          $w y n i k [i, j] : = \min_{i \leq k < j} w y n i k [i, k] + w y n i k [k + 1, j] + σ_{i, j}$ 
5   return  $w y n i k [1, n];$

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 minimalne 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ć chirurgia algorytmiczna, ponieważ możemy amputować chore lub zbędne tkanki algorytmu, aby go usprawnić. Czasami potrzebne jest wzmocnienie algorytmu poprzez doklejenie mu jakiegoś turbo-przyspieszacza (np. funkcji buty siedmiomilowe).

Większość prostych algorytmów z Modułu 1 można potraktować jako produkty transformacji algorytmów naiwnych. Pozostawiamy jako ćwiczenie pokazanie tego. Pokażemy jedynie prosty przykład obliczania liczby inwersji.

Liczba inwersji

Mając dane dwie posortowane rosnąco tablice $A [1 . . n], B [1 . . n]$ , należy wyznaczyć liczbę 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   $w y n i k : = 0;$ 
2  for  $i : = 1$  to n do begin
3     $j : = 0;$ 
4    while  $j < n$  and  $A [i] > B [j + 1]$  do  $j : = j + 1;$ 
5     $w y n i k : = w y n i k + j;$ 
6  end

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 jeszcze bardziej skomplikowany przykład. Podamy przykład transformacji 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, \dots, 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 $o p_{1}, o p_{2}, . . ., o p_{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ć LR ani RL. 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

$A 1 (n) = (A_{1}, B_{1}), (A_{2}, B_{2}) . . . (A_{n}, B_{n})$ oraz $A 2 (n) = (C_{1}, D_{1}), (C_{2}, D_{2}) . . . (C_{n}, D_{n})$ ,

to definiujemy algorytm

A 1 \cup A 2 = (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 $p r z e s k a l u j (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:

p r z e s k a l u j (A_{n - 1}) = (B 1, A 1), (A 1, B 1), (A 2, B 2), . . . (A_{n - 1}, B_{n - 1})

Docelowy algorytm definiujemy rekurencyjnie:

A_{n} = p r z e s k a l u j (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, Delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie tym strukturom, ale będziemy 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.

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 = D e l e t e M i n (S)$
;
$b = D e l e t e M i n (S)$
;
$I n s e r t (a + b, S)$
;

W dalszej części kursu pokażemy, jak każdą z operacji Insert, DeleteMin zaimplementować w czasie logarytmicznym. W szczególnym przypadku, rozważonym poniżej, można je zaimplementować w czasie stałym. Załóżmy, że początkowy zbiór $S$ jest posortowany i jego elementy są umieszczone na stosie $S T$ 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 = D e l e t e M i n (S)$
;
$b = D e l e t e M i n (S)$
;
$I n s e r t (a + b, S)$

możemy wykonać w czasie stałym: element minimalny jest na wierzchołku $S T$ 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, \dots n} \to {1, 2, \dots 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ę $π = (i_{1}, i_{2}, \dots i_{n})$ , żeby $π (f_{k} (i)) > π (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 $π$ , $π (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ą.

Pokażemy jeszcze jeden ciekawy problem, dla którego właśnie lista jest świetną strukturą danych.

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 sie 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, \dots, 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. Zakladamy wiec ze mamy na przyklad tablice NEXT taka, ze NEXT[i]=i+1, dla i<n+1, NEXT[n+1]=n+1, oraz poczatkowo Wynik[i]=0 dla kazdego i. Trojki trzymamy w trzech tablicach, i-ta trojka jest dana przez P[i], Q[i], S[i]. Nasze podstawowe zalozenie:

tablica S jest posortowana malejaco

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

Algorytm Panorama-Warszawy

1  for  $i : = 1$  to n do 
2         $j : = P [i];$ 
3        while  $j \leq Q [i]$   do 
4            if  $W y n i k [j] = 0$ then   $W y n i k [j] : = S [i];$ 
5             $j : = N E X T [j];$ 
5         $k : = P [i];$ 
6       while  $k < j$   do 
7              $p o m : = N E X T [k]; N E X T [k] : = j; k : = p o m;$

Dosyć łatwo pokazać, ze czas tego algorytmu będzie rzędu co najwyżej $n^{3 / 2}$ , a wiec lepiej niż algorytmu naiwnego. Jeśli kompresujemy ścieżkę długości k to zmniejszamy sumaryczna odległość elementów do korzenia (elementu n) o wielkość mniej więcej $k^{2}$ . Początkowa suma jest rzędu $n^{2}$ . Za każdym razem zmniejszamy te 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} + \dots a_{n}^{2} \leq n^{2} \Rightarrow a_{1} + a_{2} + a_{3} + \dots a_{n} \leq n \cdot \sqrt{n}$

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

Sortowanie kolejkowe i stosowe

Działanie stosu i kolejki świetnie ilustrują różne warianty problemu sortowania z użyciem stosów i kolejek. Niech $π$ będzie permutacją liczb ${1, 2, \dots n}$ . Możemy posortować $π$ 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  $π (i)$  do jednej z kolejek; i=i+1
     (2) lub wypisz  $π (i)$  na wyjściu; i=i+1 
     (3) lub pobierz i wypisz na wyjściu pierwszy element jednej z kolejek

Zdefiniujmy liczbę kolejkową permutacji $π$ jako minimalną liczbę kolejek potrzebnych do posortowania permutacji $π$ . Na przykład dla $π = (1, 2, 3)$ liczba ta wynosi 0, a dla $π = (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}, \dots Q_{k}$ i element może trafiać do kolejek o coraz mniejszych numerach.

Pojedyncza operacja polega na wstawieniu kolejnego elementu z $π$ do jednej z kolejek, wypisaniu bezpośrednio na wyjście, o ile jest on pierwszym niepobranym elementem w $π$ 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 $π$ 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 begin
2     $l i s t a 1 = d e l e t e (S); l i s t a 2 = d e l e t e (S);$ 
3     $i n s e r t (m e r g e (l i s t a 1, l i s t a 2), S)$ 
4  end

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, \dots, 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 begin
3    for  $i = 0$  to  $n / (2 m)$  do
4       $m e r g e (A [i . . i + m - 1], A [i + m . . i + 2 m - 1]);$ 
5     $m = 2 m;$ 
6  end

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

Spis treści

Metoda dziel i zwyciężaj

Metoda zachłanna

Wieże na szachownicy

Minimalne Sklejanie Par

Programowanie dynamiczne

Dygresja

Konstruowanie algorytmu metodą transformacji

Liczba inwersji

Wykrywanie fałszywej monety

Dygresja

Znaczenie struktury danych

Prosty przypadek kolejki priorytetowej

Maksymalna bijekcja

Dwie funkcje

Panorama Warszawy

Sortowanie kolejkowe i stosowe

Sortowanie kolejkowe

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia