Kontynuacja przedmiotu ,,Algorytmy i struktury danych''. Zawartość w przeważającej części dotyczy zagadnień optymalizacji kombinatorycznej w ujęciu algorytmicznym (problemy najkrótszych ścieżek, skojarzenia, problemy przepływowe, programowanie liniowe, algorytmy aproksymacyjne). Ponadto, przedstawiono wybrane zagadnienia algorytmów randomizowanych, geometrii obliczeniowej, algorytmów równoległych oraz szybkiej arytmetyki wielomianów.
Krzysztof Diks, Łukasz Kowalik, Wojciech Rytter, Piotr Sankowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
W tym wykładzie wymagamy od Czytelnika znajomości wykładu o maksymalnym przepływie.
Egzemplarz problemu maksymalnego przepływu o minimalnym koszcie stanowi graf skierowany \(G=(V,E)\), funkcje \(c:E\rightarrow\mathbb{R}_{\ge 0}\) i \(a:E\rightarrow \mathbb{R}\}\) oraz dwa wyróżnione wierzchołki \(s\) i \(t\). Podobnie jak w wykładzie o maksymalnym przepływie, \(c\) nazywamy funkcją przepustowości. Natomiast \(a\) jest funkcją kosztu oraz \(a(e)\) nazywamy kosztem krawędzi \(e\). W grafie \(G\) dopuszczamy możliwość istnienia wielu krawędzi o tym samym początku i końcu. Jest to naturalne założenie, gdyż koszty tych krawędzi mogą się różnić.
Przepływem nazywamy dowolną funkcję \(f:E\rightarrow\mathbb{R}_{\ge 0}\) taką, że:
Zauważmy, że powyższa definicja różni się nieco od definicji przepływu z wykładu o maksymalnym przepływie. Różnica polega na tym, że w tym rozdziale przepływ nie spełnia warunku skośnej symetryczności. Konieczność użycia nowej definicji wynika z faktu istnienia wielu krawędzi o tym samym początku i końcu. Oczywiście obie definicje są równoważne dla grafów, w których dla dowolnych wierzchołków \(u\) i \(v\) jest co najwyżej jedna krawędź spośród krawędzi \((u,v)\), \((v,u)\). Używana w tym rozdziale definicja jest bardziej naturalna i wygodniejsza podczas implementacji algorytmów, choć mniej wygodna przy dowodzeniu.
Kosztem przepływu \(f\) nazywamy liczbę \(cost(f) = \sum_{e\in E} a(e) f(e)\). Zgodnie z tą definicją, wartość \(a(e)\) interpretujemy jako koszt przesłania 1 jednostki przepływu po krawędzi \(e\). W tym rozdziale zajmujemy się następującym problemem optymalizacyjnym.
Problem 1
Znaleźć w sieci \((G,a,c,s,t)\) przepływ maksymalny o minimalnym koszcie (wśród przepływów maksymalnych).
Oprócz problemu 1, nieco inne zagadnienie wydaje się równie naturalne:
Problem 2
Dla danej sieci \((G,a,c,s,t)\) i liczby \(w \in \mathbb{R_{\ge 0}}\) znaleźć przepływ o minimalnym koszcie wśród przepływów o wartości \(w\).
Nietrudno dostrzec, że problemy 1 i 2 są równoważne. Oczywiście skoro umiemy wyznaczyć wartość maksymalnego przepływu, to problem 1 sprowadza się do problemu 2. Z drugiej strony, jeśli umiemy rozwiązać problem 1, mając dany egzemplarz \((G,a,c,s,t,w)\) problemu 2 wystarczy rozwiązać problem 1 dla egzemplarza \((G',a,c,s',t)\), gdzie graf \(G'\) powstaje z \(G\) przez dodanie nowego wierzchołka \(s'\) oraz krawędzi \((s',s)\) o koszcie 0 i przepustowości \(w\). W dalszej części wykładu będziemy mówić już wyłącznie o problemie 1.
Wprowadzenie kosztów krawędzi do naszego problemu wymusza nieco inną definicję sieci residualnej, jednak jej rola pozostaje ta sama. Dla danego przepływu \(f\) w sieci \((G=(V,E),a,c,s,t)\), sieć residualna \(G_f\) ma ten sam zbiór wierzchołków \(V\) co sieć \(G\). Krawędzie \(G_f\) chcemy określić w taki sposób, że przesłanie jednostki przepływu w \(G_f\) po krawędzi \(e=(u,v)\) odpowiada powiększeniu \(f\) wzdłuż krawędzi \(e\) o tę jednostkę lub pomniejszeniu \(f\) o tę jednostkę wzdłuż odwrotnej krawędzi, czyli wzdłuż \((v,u)\).
Zgodnie z powyższą intuicją, dla każdej krawędzi \(e\in E\) takiej, że \(f(e) < c(e)\), w zbiorze \(E_f\) sieci \(G_f\) umieszczamy krawędź \(e\) o przepustowości residualnej \(c_f(e) = c(e)-f(e)\) i koszcie \(a_f(e)=a(e)\). Natomiast dla każdej krawędzi \(e=(u,v)\in E\) takiej, że \(f(e) > 0\), w \(E_f\) umieszczamy krawędź \(\text{rev}(e)=(v,u)\) o przepustowości residualnej \(c_f(\text{rev}(e)) = f(e)\) i koszcie \(a_f(\text{rev}(e))=-a(e)\).
Jeśli \(f\) jest przepływem w \(G\), natomiast \(g\) jest przepływem w \(G_f\), to \(f+g\) definiujemy jako przepływ w \(G\), gdzie dla \(e\in E\) określamy \((f+g)(e) = f(e) + g(e) - g(\text{rev}(e))\). Łatwo widać, że \(|f+g| = |f|+|g|\) oraz \(cost(f+g)=cost(f)+cost(g)\).
Podobnie, jeśli \(f\) i \(f'\) są przepływami w \(G\) to \(f'-f\) definiujemy jako następującą funkcję \((f'-f):E_f \rightarrow\mathbb{R}_{\ge 0}\). Dla \(e \in E\), jeśli \(f'(e) > f(e)\), to \((f'-f)(e)=f'(e)-f(e)\), natomiast jeśli \(f'(e) < f(e)\), to \((f'-f)(\text{rev}(e))=f(e)-f'(e)\). Na pozostałych elementach \(E_f\) funkcja \(f'-f\) ma wartość 0. Łatwy dowód poniższego lematu pozostawiamy Czytelnikowi.
Lemat 3
Funkcja \((f'-f)\) jest przepływem w sieci residualnej \(G_f\) o wartości \(|f'-f|=|f'|-|f|\) i koszcie \(cost(f'-f)=cost(f')-cost(f)\). ♦
Następujący lemat jest często wykorzystywany w problemach związanych z przepływami.
Lemat 4
Każdy przepływ można rozłożyć na sumę cykli i ścieżek prostych od \(s\) do \(t\).
Dowód
Niech \(f\) będzie dowolnym przepływem. Użyjemy indukcji po liczbie krawędzi \(e\) takich, że \(f(e) > 0\).
Baza indukcji. Jeśli nie ma takich krawędzi to teza lematu jest prawdziwa (suma pusta).
Krok indukcyjny. Jeśli istnieje cykl \(C\), którego krawędzie mają dodatni przepływ, to definiujemy przepływ \(g\), który jest zerowy wszędzie poza \(C\), a na wszystkich krawędziach \(C\) ma wartość \(min_{e\in C} f(e)\). Żądaną w tezie rodzinę cykli i ścieżek otrzymujemy rozkładając na podstawie założenia indukcyjnego przepływ \(f-g\) na cykle i ścieżki i dodając do tej rodziny cykl \(C\).
Załóżmy więc, że nie istnieje opisany wyżej cykl. Niech \(e_0=(v_0,v_1)\) będzie dowolną krawędzią taką, że \(f(e_0)>0\). Wówczas z warunku zachowania przepływu albo \(v_1=t\) albo istnieje krawędź \(e_1=(v_1, v_2)\) taka, że \(f(e_1)>0\). Ponownie, albo \(v_2=t\) albo istnieje krawędź \(e_2=(v_2,v_3)\)... itd. Ponieważ wykluczyliśmy cykle, ta marszruta będzie ścieżką prostą, a więc ponieważ graf jest skończony, musi zakończyć się w \(t\). Podobnie, z warunku zachowania przepływu albo \(v_0=s\) albo istnieje krawędź \(e_{-1}=(v_{-1}, v_0)\) taka, że \(f(e_{-1})>0\). Ponownie, albo \(v_{-1}=s\) albo istnieje krawędź \(e_{-2}=(v_{-2},v_{-1})\)... itd: otrzymujemy ścieżkę prostą od \(s\) do \(v_0\). Suma tych dwóch ścieżek musi być ścieżką prostą od \(s\) do \(t\). Korzystając z założenia indukcyjnego analogicznie jak w przypadku cyklu, dostajemy tezę lematu. ♦
Jeśli \(X\) jest zbiorem krawędzi, to kosztem \(X\) nazwiemy \(a(X)=\sum_{e\in X}a(e)\). Przez koszt ścieżki lub cyklu rozumiemy koszt odpowiedniego zbioru krawędzi.
Lemat 5
Niech \(f\) będzie przepływem w \((G,a,c,s,t)\). Wówczas \(f\) jest przepływem o minimalnym koszcie wśród przepływów o wartości \(|f|\) wtw. gdy \(G_f\) nie zawiera cykli o ujemnym koszcie.
Dowód
Implikacja \((\rightarrow)\) jest oczywista, gdyż dodanie do \(f\) cyklu o ujemnym koszcie nie zmienia wartości \(f\), natomiast zmniejsza jego koszt.
Zajmijmy się implikacją \((\leftarrow)\). Niech \(f'\) będzie dowolnym przepływem o wartości \(|f'|=|f|\). Z lematu 3 \(f'-f\) jest przepływem w \(G_f\) o wartości 0. Z lematu 4 \(f'-f\) rozkłada się na sumę cykli i ścieżek od \(s\) do \(t\). Ponieważ \(|f'-f|=0\), więc w tym rozkładzie nie ma żadnych ścieżek. Z założenia, każdy z pozostałych cykli ma nieujemny koszt. Stąd, \(cost(f'-f) \ge 0\), a więc z lematu 3, \(cost(f')\ge cost(f)\). ♦
Korzystając z powyższego lematu dostajemy prosty algorytm znajdowania maksymalnego przepływu o minimalnym koszcie:
Jako ćwiczenie pozostawiamy pokazanie, że algorytm Bellmana-Forda można rozszerzyć tak, aby nie tylko wykrywać istnienie ujemnych cykli, ale także znaleźć pewien taki cykl w czasie \(O(|V|\cdot |E|)\).
Podobnie jak algorytm Forda-Fulkersona, powyższy algorytm nie ma własności stopu gdy przepustowości są liczbami rzeczywistymi. Jeśli jednak przepustowości i koszty są wymierne, algorytm zatrzyma się, zwracając poprawną odpowiedź. Czas jego działania będzie pseudowielomianowy (tzn. zależy wielomianowo od \(|V|\) oraz \(\max_{e\in E} c(e)\) i \(\max_{e\in E} a(e)\), zakładając że \(c\) i \(a\) są całkowitoliczbowe). W kolejnym rozdziale przedstawimy bardziej efektywny algorytm, działający w szczególnym przypadku, gdy dana na wejściu sieć nie ma cykli o ujemnym koszcie.
Załóżmy, że w sieci \((G,a,c,s,t)\) danej na wejściu nie ma cykli o ujemnym koszcie. Wówczas możemy zastosować następujący naturalny algorytm.
Zacznijmy od udowodnienia poprawności powyższego algorytmu, zwanego algorytmem najtańszej ścieżki. Z twierdzenia o maksymalnym przepływie i minimalnym przekroju, otrzymujemy że uzyskany po zakończeniu algorytmu przepływ \(f\) faktycznie jest maksymalny (zauważmy, ze nasz algorytm jest po prostu pewną implementacją algorytmu Forda-Fulkersona). Pozostaje pokazać, że \(f\) ma minimalny koszt. Wynika to z następującego niezmiennika pętli w naszym algorytmie:
Niezmiennik 1: \(f\) ma minimalny koszt wśród przepływów o wartości \(|f|\).
Zauważmy, że niezmiennik 1 jest spełniony na początku algorytmu, dla przepływu zerowego, bowiem dowolny przepływ o wartości 0 z lematu 4 rozkłada się na sumę cykli, a wiemy że cykle te mają nieujemne koszty: stąd, dowolny przepływ zerowy ma nieujemny koszt. Udowodnimy teraz, że niezmiennik 1 pozostaje zachowany po obrocie pętli.
Lemat 6
Niech \(f\) będzie pewnym przepływem o minimalnym koszcie spośród przepływów o wartości \(|f|\). Niech \(g\) będzie przepływem w sieci residualnej \(G_f\), który jest niezerowy tylko na krawędziach pewnej najtańszej ścieżki \(P\) od \(s\) do \(t\). Wówczas \(f+g\) jest najtańszym przepływem o wartości \(|f+g|\).
Dowód
Niech \(f'\) będzie dowolnym przepływem o wartości \(|f+g|\). Pokażemy, że \(cost(f')\ge cost(f+g)\).
Z lematu 3, \(f'-f\) jest przepływem w \(G_f\), o wartości \(|f'-f|=|f'|-|f|=|f+g|-|f|=|g|\). Z lematu 4, \(f'-f\) można rozbić na sumę cykli \(C_1,\ldots,C_k\) i ścieżek \(P_1\ldots,P_m\) od \(s\) do \(t\). Ponieważ \(f\) ma minimalny koszt, więc na mocy lematu 5 w \(G_f\) nie ma cykli o ujemnym koszcie, więc każdy z cykli \(C_1,\ldots,C_k\) ma nieujemny koszt. Z kolei dla każdego \(i=1,\ldots,m\) mamy \(a(P_i) \ge a(P)\), gdyż \(P\) jest najtańszą ścieżką. Oznaczmy przez \(|C_i|\) wartość przepływu, który płynie po cyklu \(C_i\), analogicznie definiujemy \(|P_i|\). Razem dostajemy
\[cost(f'-f) = \sum_{i=1}^k |C_i| a(C_i) + \sum_{i=1}^m |P_i| a(P_i) \ge \sum_{i=1}^m |P_i| a(P_i) \ge a(P) \sum_{i=1}^m |P_i| \ge a(P) |f'-f| = a(P) |g| = cost(g).\]
Ponieważ z lematu 3, \(cost(f'-f) = cost(f') - cost(f)\), otrzymujemy \(cost(f') \ge cost(f)+cost(g) = cost(f+g)\). ♦
Złożoność algorytmu zależy od tego, w jaki sposób wyszukujemy najtańszą ścieżkę w grafie. Zauważmy, że w sieci residualnej pojawiają się krawędzie o ujemnym koszcie, nie możemy więc użyć algorytmu Dijkstry. Jeśli skorzystamy z algorytmu Bellmana-Forda otrzymamy złożoność \(O(|f|\cdot|V|\cdot|E|)\).
Aby poprawić złożoność algorytmu skorzystamy z tricku podobnego jak w algorytmie Johnsona ((patrz odpowiedni wykład)). Przypomnijmy, że jeśli mamy funkcję \(\pi:V\rightarrow\mathbb{R}\) oraz dla każdej krawędzi \(e=(u,v)\) określimy \(a_{\pi}(e) = a(e) + \pi(u) - \pi(v)\) to wówczas najtańsza ścieżka względem wagi \(a_{\pi}\) jest także najtańszą ścieżką względem wagi \(a\) (lemat 8 z powyższego wykładu). Co więcej, jeśli \(\pi\) jest potencjałem, to \(a_{\pi}(e)\ge 0\) dla każdej krawędzi \(e\). Pomysł polega na tym, żeby najtańsze ścieżki obliczać algorytmem Dijkstry w sieci o wagach \(a_{\pi}\). Początkowy potencjał \(\pi\) wyznaczamy za pomocą algorytmu Bellmana-Forda, podobnie jak to było w algorytmie Johnsona. Okazuje się, że po zakończonej iteracji, potencjał dla nowej sieci residualnej można łatwo obliczyć w czasie liniowym.
Zmodyfikowany algorytm wygląda następująco.
Poprawność algorytmu wynika z następującego niezmiennika.
Niezmiennik 2: \(\pi\) jest potencjałem w grafie \(G_f\).
Na początku, gdy \(\pi\) jest po prostu funkcją odległości \(\delta\) w grafie, w którym za długość krawędzi przyjmujemy jej koszt, niezmiennik jest oczywisty, gdyż dla każdej krawędzi \(u,v\), mamy \(\delta(v) \le \delta(u) + a(u,v)\).
Dowód, że niezmiennik jest zachowany po obrocie pętli
Niech \(f\) będzie przepływem przed iteracją, \(f'\) przepływem po iteracji. Zakładamy, że \(\pi\) jest potencjałem w \(G_f\) tzn. dla każdej krawędzi \(e=(u,v)\in E_f\) mamy \(a_{\pi}(e)\ge 0\). Pokażemy, że \(\pi'=\pi+\delta\) jest potencjałem w \(G_{f\,^\prime}\), tzn. że dla każdej krawędzi \(e=(u,v)\in E_{f\,'}\) mamy \(a_{\pi'}(e)\ge 0\). Rozważmy dowolną krawędź \(e=(u,v)\in E_{f\,'}\).
Jeśli \(e \in E_f\), to \(\delta_{\pi}(v) \le \delta_{\pi}(u) + a_{\pi}(e)\). Stąd, \(0 \le a_{\pi}(e) + \delta_{\pi}(u) - \delta_{\pi}(v) = a(e) + \pi(u) - \pi(v) + \delta_{\pi}(u) - \delta_{\pi}(v) = a(e) + \pi'(u) - \pi'(v) = a_{\pi'}(e)\).
Jeśli natomiast \(e \not \in E_f\), to wiemy, że podczas iteracji przesyłano przepływ po krawędzi \(\text{rev}(e)\in E_f\). Stąd, krawędź \(\text{rev}(e)=(v,u)\) leży na najtańszej ścieżce od \(s\) do \(t\) w \(G_f\) z kosztami \(a_{\pi}\), a więc \(\delta_{\pi}(u)=\delta_{\pi}(v)+a_{\pi}(\text{rev}(e)) = \delta_{\pi}(v) + a(\text{rev}(e)) + \pi(v) - \pi(u)\). Stąd, \(\pi'(v) - \pi'(u) + a(\text{rev}(e)) = 0\). Ponieważ \( a(\text{rev}(e))=- a(e)\) otrzymujemy \(\pi'(u) - \pi'(v) + a(e) = 0\), czyli \(a_{\pi'}(e)=0\). ♦
Jeśli algorytm Dijkstry zaimplementujemy z użyciem kopców Fibonacciego to jedna iteracja naszego algorytmu zajmie czas \(O(|V|\log|V|+|E|)\). Otrzymujemy zatem następujące twierdzenie.
Twierdzenie
W sieci bez cykli o ujemnym koszcie można znaleźć najtańszy maksymalny przepływ \(f\) w czasie \(O(|V|\cdot|E|+|f|(|V|\log|V|+|E|))\).
Niech \(G=(V,E)\) będzie grafem skierowanym oraz niech \(w:E \rightarrow \mathbb{R}\) będzie dowolną funkcją wag krawędzi. Wagą skojarzenia \(M\) nazywamy liczbę \(w(M) = \sum_{e\in M} w(e)\). W problemie najlżejszego (najcięższego) skojarzenia należy wyznaczyć skojarzenie doskonałe (tzn. takie, że każdy wierzchołek jest skojarzony) o minimalnej (maksymalnej) wadze. Oczywiście problem najcięższego skojarzenia redukuje się do problemu najlżejszego skojarzenia: wystarczy przemnożyć wagi krawędzi przez \(-1\).
Łatwo zauważyć, że problem najlżejszego skojarzenia w grafie dwudzielnym \(G=(U,V,E)\) redukuje się do problemu maksymalnego przepływu o minimalnym koszcie. Mianowicie, budujemy sieć o zbiorze wierzchołków \(U \cup V \cup \{s,t\}\). Dla każdego wierzchołka \(u\in U\), umieszczamy w sieci krawędź \((s,u)\) o przepustowości 1 i koszcie 0. Podobnie, dla każdego wierzchołka \(v\in V\), umieszczamy w sieci krawędź \((v,t)\) o przepustowości 1 i koszcie 0. W końcu, dla każdej krawędzi \(uv \in E\) takiej że \(u\in U\) oraz \(v\in V\), umieszczamy w sieci krawędź \((u, v)\) o przepustowości 1 i koszcie \(w(u,v)\). Łatwo sprawdzić, że w takiej sieci nie ma cykli o ujemnym koszcie oraz że dowolny przepływ \(f\) o wartości \(|f|=|U|=|V|\) odpowiada skojarzeniu (jakiemu?) o wadze \(cost(f)\).
Wniosek
Najlżejsze (najcięższe) skojarzenie doskonałe w grafie dwudzielnym o \(n\) wierzchołkach i \(m\) krawędziach można wyznaczyć w czasie \(O(nm+n^2\log n)\).
Okazuje się, że nawet w dowolnym grafie możliwe jest wyznaczenie najlżejszego skojarzenia doskonałego w czasie wielomianowym. Algorytm ten nie korzysta ze sprowadzenia do przepływów i wykracza poza zakres tego wykładu.
W tym rozdziale przedstawimy kolejne bardzo naturalne rozwiązanie problemu dynamicznego słownika oparte na haszowaniu. Liczby całkowite ze zbioru \(S\) reprezentowanego przez nasz słownik będą przechowywane bezpośrednio w tablicy \(T[0..m - 1]\). Rozmiar \(T\) będzie większy niż \(n=|S|\), choć liniowy względem \(n\). Zwykle w zastosowaniach przyjmuje się \(m=2n\), do udowodnienia asymptotycznych oszacowań na czasy działania operacji wystarczy \(m=(1+\varepsilon)\cdot n\), natomiast my dla ustalenia uwagi przyjmiemy \(m=3n\). Algorytmy operacji słownikowych będą korzystały z pojedynczej funkcji haszującej \(h:U\rightarrow \{0..m-1\}\).
Algorytmy poszczególnych operacji są następujące:
NULL. Nie możemy jednak tak zostawić tablicy \(T\), ponieważ w spójnym bloku niepustych komórek zaczynającym się od pozycji \(p+1\) może znajdować się element (lub elementy) \(y\) taki, że \(h(y) \le p\); wówczas wynik operacji lookup(\(y\)) byłby niepoprawny. W tym celu znajdujemy pierwszy taki element \(y=T[r]\), wstawiamy go w \(T[p]\), i czyścimy jego komórkę, tzn. T[r] := NULL. Oczywiście tę operację powtarzamy tak długo, jak występuje opisana powyżej niepożądana sytuacja. Dla jasności poniżej podajemy pseudokod.procedure delete (x) begin p := h(x); while (T[p] <> x) and (T[p] <> NULL) p := p + 1; T[p] := NULL fill(p) end; procedure fill(p) begin r := p+1; while (T[r] <> NULL) and (h(T[r]) > p) r := r + 1; if (T[r] <> NULL) then begin T[p] := T[r]; T[r] := NULL; fill(r); end; end;
Poprawność opisanych algorytmów powinna być dość jasna (w zasadzie tylko w przypadku delete jest się nad czym zastanawiać).
Zauważmy, że opisane operacje (szczególnie lookup i insert) operują z reguły na spójnym bloku pamięci (chyba że, pechowo, algorytm wyszukiwania musi ,,przeskoczyć'' z końca tablicy na początek). Taki sposób dostępu do pamięci jest kluczowy dla praktycznej efektywności algorytmów, gdyż w komputerach o współczesnej architekturze z reguły wykonany zostanie odczyt pojedynczego bloku pamięci przy pierwszej operacji dostępu do tablicy T, natomiast wartości kolejnych komórek zostaną już odczytane z szybkiej pamięci typu cache. Z tego względu haszowanie liniowe jest rozwiązaniem najczęściej wybieranym w praktyce. W tym wykładzie dowiemy się, że odpowiednio wybierając funkcję haszującą możemy zagwarantować także teoretyczną efektywność wszystkich operacji słownikowych.
Pamiętamy z wcześniejszego wykładu, że przy haszowaniu przez łańcuchowanie, jeśli \(h\) jest wybrana losowo z rodziny uniwersalnej, to oczekiwane czasy operacji słownikowych są stałe. Od czasu uzyskania tego wyniku przez Cartera i Wegmana w 1977r. pozostawało otwartym pytanie, czy można uzyskać analogiczny wynik dla haszowania liniowego, używając rodziny uniwersalnej lub jakiejś innej rodziny funkcji haszujących. Dopiero w 2007 odpowiedzi udzielili Rasmus Pagh, Anna Pagh i Milan Ruzic.
Twierdzenie 1
Jeśli w haszowaniu liniowym \(h\) jest wybrana losowo z uniwersalnej rodziny funkcji haszujących Cartera i Wegmana (patrz Przykład 2 w I wykładzie o haszowaniu), to istnieje \(S\subset U\) taki, że całkowity oczekiwany czas wstawienia wszystkich elementów z \(S\) wynosi \(\Omega(n\log n)\).
Równocześnie pokazali oni także następujący wynik pozytywny:
Twierdzenie 2
Jeśli w haszowaniu liniowym \(h\) jest wybrana losowo z dowolnej 5-niezależnej rodziny funkcji haszujących, to oczekiwany czas operacji słownikowych jest stały, a dokładniej wynosi \(O((1-\alpha)^{-7/6})\), gdzie \(\alpha=n/m\).
Zacznijmy od tego, że wynik \(O((1-\alpha)^{-7/6})\) jest naprawdę dobry, gdyż \(O((1-\alpha)^{-1})\) to oczekiwany czas jaki dostajemy, gdy zamiast szukać wolnego miejsca na \(x\) używając kolejnych pozycji w tablicy \(T\), korzystamy z w pełni losowej permutacji pozycji (patrz np. podręcznik Cormena i innych), co jest bardzo wyidealizowanym założeniem. Twierdzenie 2 jest dość zaskakujące, gdyż w świetle twierdzenia 1, które ,,z grubsza'' mówi, że 2-niezależność nie wystarcza, mogłoby się wydawać, że również \(O(1)\)-niezależność nie jest wystarczająca. Dodatkowo dziwi tu liczba 5, na pierwszy rzut oka wygląda to na niedokładne szacowanie, nieoptymalny wynik. Nic bardziej błędnego, gdyż w 2010r. Patrascu i Thorup wykazali, że
Twierdzenie 3
Istnieje \(4\)-niezależna rodzina funkcji haszujących \(\mathcal{H}\) taka, że jeśli w haszowaniu liniowym \(h\) jest wybrana losowo z \(\mathcal{H}\), to istnieje \(S\subset U\) taki, że całkowity oczekiwany czas wstawienia wszystkich elementów z \(S\) wynosi \(\Omega(n\log n)\).
W dalszej części udowodnimy uproszczoną wersję twierdzenia 2.
Twierdzenie 4
Jeśli w haszowaniu liniowym \(h\) jest wybrana losowo z dowolnej 5-niezależnej rodziny funkcji haszujących \(\mathcal{H}\), oraz \(m\ge 3n\), to oczekiwany czas operacji słownikowych jest stały.
Zauważmy, że przyjęliśmy \(\alpha \le \frac{1}{3}\). Spójną składową tablicy \(T\) będziemy nazywać dowolny maksymalny ciąg kolejnych niepustych komórek tablicy \(T\). Niech \(cc(p)\) oznacza spójną składową zawierającą komórkę \(p\), natomiast \(|cc(p)|\) jej długość. Łatwo widać, że prawdziwy jest następujący lemat.
Lemat 5
Czas działania każdej z operacji insert(\(x\)), lookup(\(x\)) oraz delete(\(x\)) można oszacować przez \(O(|cc(h(x))|)\). ♦
Weźmy dowolne \(x\in U\). Zgodnie z lematem 5, aby wykazać twierdzenie 4 wystarczy, że oszacujemy przez pewną stałą oczekiwaną długość spójnej składowej zawierającej pozycję \(h(x)\). Oczywiście zawsze istnieje takie \(k\), że \(|cc(h(x))| \in \{2^k, \ldots, 2^{k+1}-1\}\). Podzielmy komórki \(T\) na równe bloki długości \(2^{k-2}\).
Przypomnijmy, że notacja \(\mathbf{1}_{\mathcal{E}}\), gdzie \(\mathcal{E}\) jest dowolnym zdarzeniem oznacza indykator zdarzenia \(\mathcal{E}\), czyli zmienną losową która przyjmuje wartość 1 gdy \(\mathcal{E}\) zaszło i 0 w przeciwnym przypadku (formalnie, \(\mathbf{1}_{\mathcal{E}}(\omega)=[\omega \in \mathcal{E}]\)).
Lemat 6
\(\mathbb{E}[|h(S)\cap B|] = \alpha|B| = \frac{1}{3} |B|\)
Dowód
Korzystamy z liniowości wartości oczekiwanej i jednostajności \(\mathcal{H}\), czyli faktu, że \(\mathbb{P}[h(e)=b] = 1/m\) dla dowolnych \(e\in U\), \(b\in [m]\). Zauważmy, że \(\mathbb{E}[|h(S)\cap B|] = \sum_{e \in S} \mathbb{E}[\mathbf{1}_{h(e)\in B}] = \sum_{e \in S} \mathbb{P}[h(e)\in B] = \sum_{e \in S}\sum_{b \in B}\mathbb{P}[h(e)=b] = n\cdot|B|\cdot \frac{1}{m}= \alpha|B| = \frac{1}{3} |B|\). ♦
Powiemy, że blok \(B=\{i, i+1, \ldots, i + 2^{k-2} - 1\}\) jest niebezpieczny, gdy \(|h(S) \cap B| \ge \frac{2}{3} |B|\). Uwaga! Zauważmy, że nie liczymy tu ile komórek \(B\) jest zajętych, a jedynie do ilu komórek \(B\) haszują się elementy \(S\).
Lemat 7
Jeśli \(h(x)\) jest w spójnej składowej długości \(\in \{2^k, \ldots, 2^{k+1}-1\}\) to jeden z \(O(1)\) bloków przecinających \(cc(h(x))\) jest niebezpieczny.
Dowód
Oznaczmy kolejne bloki przecinające \(cc(h(x))\) przez \(B_1, \ldots, B_k\). Zauważmy, że \(4 \le k \le 9\). Załóżmy przeciwnie, że wszystkie te bloki są bezpieczne. W szczególności oznacza to, że mniej niż \(\frac{2}{3}2^{k-2}\) elementów haszujących do \(B_1\) znajduje się w kolejnych blokach. W blokach \(B_2\) i \(B_3\) jest sumarycznie więcej niż \(2\cdot \frac{1}{3}|B|\) komórek, które nie zawierają elementów haszujących do \(B_2\) i \(B_3\). To oznacza, że nie wszystkie z tych komórek zostaną zajęte przez elementy haszujące do \(B_1\), a więc co najmniej jedna komórka pozostanie pusta (gdyż inne elementy nie mogą tam się pojawić). W takim razie \(k\le 3\), sprzeczność. ♦
Załóżmy teraz, że znamy wartość \(\rho=h(x)\) i chcemy oszacować prawdopodobieństwo, że \(|cc(\rho)| \in \{2^k,\ldots,2^{k+1}-1\}\).
Ponieważ \(cc(\rho)\) przecina co najwyżej 9 bloków, to jest co najwyżej 17 bloków \(B_1,\ldots, B_k\), które potencjalnie mogą przecinać się z \(cc(\rho)\). Z lematu 7 wiemy, że jeśli \(|cc(\rho)| \in \{2^k,\ldots,2^{k+1}-1\}\) to jeden z tych bloków jest niebezpieczny.
Stąd, \[\mathbb{P}[|cc(\rho)| \in \{2^k,\ldots,2^{k+1}-1\} | h(x)=\rho] \le \sum_{i=1}^k \mathbb{P}[|h(S)\cap B_i|\ge \frac{2}{3}|B_i| | h(x)=\rho].\]
Z symetrii i lematu 6 mamy dalej (*)
\[\mathbb{P}[|cc(\rho)| \in \{2^k,\ldots,2^{k+1}-1\} | h(x)=\rho] = O(1) \cdot \mathbb{P}[|h(S)\cap B|\ge \mathbb{E}(|h(S) \cap B|)+\frac{1}{3}|B| | h(x)=\rho],
\]
gdzie \(B\) jest pewnym konkretnym blokiem długości \(2^{k-2}\).
Od tej pory, dla uproszczenia zakładamy, że wszsytko jest warunkowane przez zdarzenie \(h(x)=\rho\) i będziemy pomijać w prawdopodobieństwach (i wartościach oczekiwanych) napis ,,\(| h(x)=\rho\)''. Zauważmy, że przy tym warunkowaniu, rodzina \(\mathcal{H}\) jest 4-niezależna.
Niech \(X_e = \mathbf{1}_{h(e) \in B}\) oraz \(X=\sum_{e\in S} X_e\). Przy takiej notacji, chodzi nam o to, żeby oszacować \(\mathbb{P}[X > 2\mathbb{E}(X)]\). Narzuca się, żeby w celu oszacowania powyższego prawdopodobieństwa użyć nierówności Chernoffa, problem polega jednak na tym, że zmienne \(X_e\) nie są niezależne (a jedynie 4-niezależne). Z nierówności Markowa dostajemy szacowanie przez \(\frac{1}{2}\), lecz jak się później okaże jest ono o wiele za słabe. Kolejny pomysł to użycie nierówności Czebyszewa -- dałaby ona lepsze oszacowanie, lecz w dalszym ciągu niewystarczające. Okazuje się, że wystarczy zrobić jeden krok dalej -- mianowicie użyć następującego faktu:
Nierówność czwartego momentu: \(\mathbb{P}[|X-\mathbb{E}X| > d] \le \frac{\mathbb{E}[(X-\mathbb{E}X)^4]}{d^4}.\)
Dowód nierówności
Dowodzimy tak samo jak nierówność Czebyszewa, tylko podnosimy do 4-tej potęgi:
\[\mathbb{P}[|X-\mathbb{E}X| > d] = \mathbb{P}[(X-\mathbb{E}X)^4 > d^4] \le \frac{\mathbb{E}[(X-\mathbb{E}X)^4]}{d^4},\]
gdzie ostatnia nierówność wynika z nierówności Markowa.♦
Pozostaje jedynie oszacować czwarty moment, czyli \(\mathbb{E}[(X-\mathbb{E}X)^4]\). Oznaczmy
Dla dowolnego \(e\) i parzystego \(j>0\) mamy
\[
\begin{align}
\mathbb{E}[Y_e^j] &= \left(1-\tfrac{|B|}{m}\right)^j \tfrac{|B|}{m} + \left(-\tfrac{|B|}{m}\right)^j\left(1-\tfrac{|B|}{m}\right) =
\left(1-\tfrac{|B|}{m}\right)^j \tfrac{|B|}{m} + \left(\tfrac{|B|}{m}\right)^j\left(1-\tfrac{|B|}{m}\right) =\\
&= \tfrac{|B|}{m} \left(1-\tfrac{|B|}{m}\right) \left(\left(1-\tfrac{|B|}{m}\right)^{j-1} + \left(\tfrac{|B|}{m}\right)^{j-1}\right) < \tfrac{|B|}{m}.
\end{align}
\]
Stąd, pamiętając o oznaczeniu \(\alpha = n/m\),
\[\mathbb{E}[Y^4] < n \frac{|B|}{m} + 6\frac{n^2}{2}\left(\frac{|B|}{m}\right)= \alpha|B| + 3(\alpha|B|)^2 < 4(\alpha|B|)^2.\]
Stąd i z nierówności 4-tego momentu mamy, że (**)
\[\mathbb{P}[X>2\mathbb{E}X] = \mathbb{P}[X-\mathbb{E}X > \mathbb{E}X] < \frac{4(\alpha|B|)^2}{(\alpha|B|)^4} = \frac{4}{\alpha^4}|B|^{-2}=O(|B|^{-2}).
\]
Stąd i z (*) mamy
\[
\begin{align}
\mathbb{E}[|cc(\rho)| | h(x)=\rho] &= \sum_l l\cdot \mathbb{P}[|cc(\rho)|=l | h(x)=\rho]\\
& < \sum_k 2^{k+1}\cdot \mathbb{P}[|cc(\rho)|\in\{2^k,\ldots,2^{k+1}-1\} | h(x)=\rho]\\
& <^{(*), (**)} \sum_k 2^{k+1}\cdot O(1)\cdot (2^{k-2})^{-2} \\
& = O(1) \sum_k 2^{-k} \\
& = O(1).
\end{align}
\]
Ponieważ jest to prawdziwe dla dowolnego \(\rho\in [m]\), więc \(\mathbb{E}[|cc(h(x))|]=O(1)\), a tym samym dowód twierdzenia 4 jest zakończony.
Literatura
Wynik przedstawiony w tym wykładzie został po raz pierwszy opisany w pracy
A. Pagh, R. Pagh, M. Ruzic. Linear probing with constant independence. SIAM J. Comput., 39(3):1107–1120, 2009.
Użyty tutaj sposób prezentacji dowodów jest jednak w głównej mierze inspirowany blogiem Mihai Pătraşcu oraz pracą
M. Pătraşcu, M. Thorup. The Power of Simple Tabulation Hashing, Proc. 43rd ACM Symposium on Theory of Computing (STOC 2011).
Twierdzenie 3 zostało udowodnione w pracy
M. Patrascu and M. Thorup. On the -independence required by linear probing and minwise independence. Proc. ICALP 2010.