From fc18e50494f61c270020b11f9d6a4c7443ff7203 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 May 2007 09:02:27 +0200 Subject: [PATCH] Drobne korektury. --- 10-cesty/10-cesty.tex | 44 +++++++++++++++++++++---------------------- 1 file changed, 22 insertions(+), 22 deletions(-) diff --git a/10-cesty/10-cesty.tex b/10-cesty/10-cesty.tex index fb5e6e6..57db49c 100644 --- a/10-cesty/10-cesty.tex +++ b/10-cesty/10-cesty.tex @@ -1,11 +1,11 @@ \input ../lecnotes.tex -\prednaska{10}{Hledání nejkrat¹í cesty}{(zapsali L. Banáková, O. Hoferek, J. Bøeèka)} +\prednaska{10}{Nejkrat¹í cesty}{(zapsali L. Banáková, O. Hoferek, J. Bøeèka)} \s{Problém:} Je dán graf G, kde $l(u,v)$~=~délka hrany~$(u,v)$. Dále jsou dány vrcholy $s,c~\in~V(G)$. Chceme najít cestu $s=v_1, v_2, \dots, v_k=c$ takovou, aby $$l(v_1, v_2) + l(v_2, v_3) + \dots + l(v_{k-1}, v_k)$$ bylo minimální. Takovéto -cestì budeme øíkat nejkrat¹í cesta z~$s$~do~$c$. +cestì budeme øíkat {\I nejkrat¹í cesta} z~$s$~do~$c$. \noindent Bez újmy na obecnosti budeme pøedpokládat, ¾e graf G je orientovaný, bez smyèek a @@ -39,13 +39,13 @@ maxim \proof \noindent -,,$\Rightarrow$``: Zjevné, indukcí podle bìhu algoritmu. +\uv{$\Rightarrow$}: Zjevné, indukcí podle bìhu algoritmu. \noindent -,,$\Leftarrow$``: Doká¾eme sporem. Uva¾me, ¾e existuje vrchol dostupný, ale algoritmem -neoznaèený. Vezmìme takovýto ,,¹patný`` vrchol $v$, který je $s$ nejblí¾e. Uva¾me +\uv{$\Leftarrow$}: Doká¾eme sporem. Uva¾me, ¾e existuje vrchol dostupný, ale algoritmem +neoznaèený. Vezmìme takovýto \uv{¹patný} vrchol $v$, který je $s$ nejblí¾e. Uva¾me nejkrat¹í cestu $(s,v)$: $s,\dots,u,v$. Pøedchozí vrchol na této cestì $u$ -musí být ,,dobrý``. Vrchol $u$ se dostane do fronty, pak je z~ní vybrán a tím +musí být \uv{dobrý}. Vrchol $u$ se dostane do fronty, pak je z~ní vybrán a tím se zpracuje i vrchol $v$ $\Rightarrow$ spor. \s{Definice:} {\I Vzdálenost vrcholù} $d(u,v)$ je délka nejkrat¹í cesty $(u,v)$, @@ -71,7 +71,7 @@ $v~\in~V(G)$. \endalgo \noindent -Prùbìh tohoto algoritmu si mù¾eme ukázat na následujícím obrázku (,,praseèí graf``): +Prùbìh tohoto algoritmu si mù¾eme ukázat na následujícím obrázku (\uv{praseèí graf}): \figure{praseci-graf.eps}{Praseèí graf}{75mm} @@ -165,7 +165,7 @@ na p Nahlédnìme nyní, zda by vedlo k~vylep¹ení èasové slo¾itosti, kdybychom pøi~implementaci Dijkstrova algoritmu pou¾ili jako datovou strukturu pro ukládání vidìných vrcholù rùzné typy hald. -Provádìli bychom s~nimi operace DeleteMin (maximálnì $n$-krát) a Decrease (maximálnì $m$-krát). Zmínìné +Provádìli bychom s~nimi operace \ (maximálnì $n$-krát) a \ (maximálnì $m$-krát). Zmínìné operace mají pro rùzné typy hald následující èasové slo¾itosti: \medskip @@ -173,22 +173,22 @@ operace maj \vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & #\cr & halda & $k$-regulární halda & Fibonaciho halda\cr \noalign{\medskip\hrule\bigskip} -DeleteMin & $\O(\log{n})$ & $\O(k.\log_k{n})$ & $\O(\log{n})$\cr -Decrease & $\O(\log{n})$ & $\O(\log_k{n})$ & $\O(1)$\cr}} +\ & $\O(\log{n})$ & $\O(k\log_k{n})$ & $\O(\log{n})$\cr +\ & $\O(\log{n})$ & $\O(\log_k{n})$ & $\O(1)$\cr}} \medskip -Pou¾ijeme-li klasickou haldu, dostaneme celkovou èasovou slo¾itost $\O((m~+~n).\log{n})$, co¾ znamená, -¾e jsme si pomohli v pøípadech, kdy je graf ,,øídký``. U $k$-regulární haldy se celková èasová slo¾itost -rovná $\O(n.k.\log_k{n}+m.\log_k{n})$, ideálnì pro $k~=$~${m}\over{n}$~:~$\O(m.\log_{{m}\over{n}}{n})$. Prozkoumejme, -jak se nám v tomto pøípadì bude mìnit èasová slo¾itost pro rùznì ,,husté`` grafy: +Pou¾ijeme-li klasickou haldu, dostaneme celkovou èasovou slo¾itost $\O((m+n)\log{n})$, co¾ znamená, +¾e jsme si pomohli v pøípadech, kdy je graf \uv{øídký}. U $k$-regulární haldy se celková èasová slo¾itost +rovná $\O(nk\log_k{n}+m\log_k{n})$, ideálnì pro $k=m/n$: $\O(m\log_{m/n}{n})$. Prozkoumejme, +jak se nám v tomto pøípadì bude mìnit èasová slo¾itost pro rùznì \uv{husté} grafy: \itemize\ibull -\:$m \approx n \rightarrow \O((m+n).\log{n})$ +\:$m \approx n \rightarrow \O((m+n)\log{n})$ \:$m \approx n^2 \rightarrow \O(m)$ \:$m \approx n^{1+\epsilon} \rightarrow \O(m) \dots (k=$~${m}\over{n}$~$= n^\epsilon)$ \endlist \noindent -Pøi pou¾ití Fibonaciho haldy je pak celková èasová slo¾itost rovna $\O(n.\log{n}+m)$. +Pøi pou¾ití Fibonaciho haldy je pak celková èasová slo¾itost rovna $\O(n\log{n}+m)$. \medskip @@ -197,21 +197,21 @@ ke grafu $G = (V, E)$: $ A_{ij} = 1 \Leftrightarrow (v_i, v_j) \in E $. Potom $A^2_{ij} = \sum_{k=1}^n A_{ik}A_{kj} $. Tento souèet je nenulový právì tehdy, kdy¾ vrcholy $i$,$k$,$j$ tvoøí sled délky 2. Jinými slovy $A_{ij}$ se rovná poètu sledù délky 2 v $G$ z $i$ do $j$. Obdobnì $A^k_{ij}$ = poèet sledù délky $k$. Pokud -k matici $A$ pøièteme jednotkovou matici $E$ (èím¾ si pøimyslíme smyèky), +k matici $A$ pøièteme jednotkovou matici ${\bb E}_n$ (èím¾ si pøimyslíme smyèky), dostaneme po umocnìní: -$ (A+E)^k_{ij} \neq 0 \Leftrightarrow \exists$ $i,j$-sled délky maximálnì $k$ +$ (A+{\bb E}_n)^k_{ij} \neq 0 \Leftrightarrow \exists$ $i,j$-sled délky maximálnì $k$. -Výstupem algoritmu tedy bude matice $(A + E)^n$. Mù¾eme si také v¹imnout, ¾e -pokud matici $(A + E)$ umocníme na èíslo vìt¹í ne¾ $n$, tak výsledek bude poøád +Výstupem algoritmu tedy bude matice $(A + {\bb E}_n)^n$. Mù¾eme si také v¹imnout, ¾e +pokud matici $A + {\bb E}_n$ umocníme na èíslo vìt¹í ne¾ $n$, tak výsledek bude poøád správný, jen bude výpoèet trvat déle. Tak¾e algoritmus mù¾e pracovat -v iteracích umocòováním matice na druhou: $M_0 = A + E$, $M_1 = M^2_0$, $M_{i+1} = M^2_i$, +v iteracích umocòováním matice na druhou: $M_0 = A + {\bb E}_n$, $M_1 = M^2_0$, $M_{i+1} = M^2_i$, tak¾e výstupní matice bude: $ M_{\lceil \log{n} \rceil (ij)} \neq 0 \Leftrightarrow \exists$ cesta z $i$ do $j$ Pokud pou¾ijeme Strassenùv vzorec na násobení matic, dostaneme ve výsledku algoritmus na dosa¾itelnost v grafu se slo¾itostí -$\O(n^{\log_2{7}}.\log{n})$. +$\O(n^{\log_2{7}}\log{n})$. \bye -- 2.39.2