Cesty: Algoritmy pro PPSP (obousmerny Dijkstra, A*)

[ga.git] / 8-qheap / 8-qheap.tex

diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex
index 325f702cdd4eecd5105473beab21d02e9278c07d..6168943a43851d51bcc251fa4be0a98163fa766e 100644 (file)
--- a/8-qheap/8-qheap.tex
+++ b/8-qheap/8-qheap.tex
@@ -125,17 +125,19 @@ R
 hodnot vrátí rank prvku~$x$. K~tomu potøebujeme pøedev¹ím umìt indexovat tvarem
 stromu.
 
-\s{Pozorování:} Tvar trie je jednoznaènì urèen hodnotami $c_1,\ldots,c_n$
+\s{Pozorování:} Tvar trie je jednoznaènì urèen hodnotami $c_1,\ldots,c_{r-1}$
 (je to toti¾ kartézský strom nad tìmito hodnotami -- blí¾e viz kapitola o~dekompozicích
-stromù), hodnoty v~listech jsou $x_1,\ldots,x_n$ v~poøadí zleva doprava.
+stromù), hodnoty v~listech jsou $x_1,\ldots,x_r$ v~poøadí zleva doprava.
 
-Kdykoliv chceme indexovat tvarem stromu, mù¾eme tedy indexovat pøímo vektorem
-$(c_1,\ldots,c_n)$, který má pouze $k\log w=\O(k^2)$ bitù. Pro zjednodu¹ení ostatních
-operací ale zvolíme trochu jinou, ekvivalentní reprezentaci:
+Kdykoliv chceme indexovat tvarem stromu, mù¾eme místo toho pou¾ít pøimo vektor
+$(c_1,\ldots,c_r-1)$, který má $k\log w$ bitù. To se sice u¾ vejde do vektoru,
+ale pro indexování tabulek je to stále pøíli¹ (v¹imnìte si, ¾e $\log w$ smí být
+vùèi~$k$ libovolnì vysoký -- pro~$w$ známe pouze dolní mez). Proto reprezentaci
+je¹tì rozdìlíme na dvì èásti:
 
 \itemize\ibull
 \:$B := \{c_1,\ldots,c_r\}$ (mno¾ina v¹ech pozic bitù, které trie testuje, ulo¾ená ve~vektoru setøídìnì),
-\:$C: \{1,\ldots,r\} \to B: B[C(i)]=c_i$.
+\:$C: \{1,\ldots,r\} \to B$ taková, ¾e $B[C(i)]=c_i$.
 \endlist
 
 \s{Lemma R':} $\rank_X(x)$ lze spoèítat v~konstantním èase~z:
@@ -171,9 +173,9 @@ po
 \:$k$, $r$ -- kapacita haldy a aktuální poèet prvkù (èísla),
 \:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvkù v libovolném poøadí (pole èísel),
 \:$\varrho$ -- permutace na~$\{1,\ldots,r\}$ taková, ¾e $x_i=X[\varrho(i)]$
-  a $x_1<x_2<\ldots<x_r$ (vektor o~$r\cdot\log r$ bitech),
+  a $x_1<x_2<\ldots<x_r$ (vektor o~$r\cdot\log k$ bitech),
 \:$B$ -- mno¾ina \uv{zajímavých} bitových pozic (setøídìný vektor o~$r\cdot\log w$ bitech),
-\:$C$ -- funkce popisující znaèky: $c_i=B[C(i)]$ (vektor o~$r\cdot\log r$ bitech),
+\:$C$ -- funkce popisující znaèky: $c_i=B[C(i)]$ (vektor o~$r\cdot\log k$ bitech),
 \:pøedpoèítané tabulky pro rùzné funkce.
 \endlist
 
@@ -195,6 +197,7 @@ po
 \:Pøepoèítáme $c_{i-1}$ a $c_i$. Pro ka¾dou zmìnu $c_j$:
 \::Pokud je¹tì nová hodnota není v~$B$, pøidáme ji tam.
 \::Upravíme $C(j)$, aby ukazovalo na~tuto hodnotu.
+\::Upravíme ostatní prvky~$C$, ukazující na hodnoty v~$B$, které se vlo¾ením posunuly.
 \::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(\cdot)$, sma¾eme ji z~$B$.
 \endalgo