From 89b62c69fcce434894745e3ef5b327d912ad27ea Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 30 Jan 2011 23:35:42 +0100 Subject: [PATCH] APSP: Kapitola prejmenovana na "Transitivni uzavery", prepsan uvod --- 14-floyd/14-floyd.tex | 36 +++++++++++++++++++++--------------- 1 file changed, 21 insertions(+), 15 deletions(-) diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex index 8703134..31809d2 100644 --- a/14-floyd/14-floyd.tex +++ b/14-floyd/14-floyd.tex @@ -1,21 +1,27 @@ \input ../sgr.tex -\prednaska{13}{Nejkrat¹í cesty: Maticové metody}{} +\prednaska{14}{Transitivní uzávìry}{} V~pøedchozí kapitole jsme se zabývali algoritmy pro hledání nejkrat¹ích -cest z~daného poèáteèního vrcholu. Nyní se zamìøíme na výpoèet celé -metriky grafu, tedy matice vzdáleností, která pro ka¾dou dvojici vrcholù -obsahuje délku nejkrat¹í cesty mezi nimi. - -Jeden zpùsob se ihned nabízí: postupnì spustit Dijkstrùv algoritmus pro v¹echny -mo¾né volby poèáteèního vrcholu, pøípadnì se pøed tím je¹tì zbavit záporných -hran pomocí potenciálù. Tak dosáhneme èasové slo¾itosti $\O(mn + n^2\log n)$. -To je pro øídké grafy nejlep¹í známý výsledek -- jen $\O(\log n)$-krát -pomalej¹í, ne¾ je velikost výstupu. - -Je-li graf hustý pracují obvykle rychleji algoritmy zalo¾ené na maticích, zejména +cest z~daného poèáteèního vrcholu. Nyní se zamìøíme na pøípady, kdy nás +zajímají vzdálenosti, pøípadnì pouhá dosa¾itelnost, mezi v¹emi dvojicemi +vrcholù. + +Výstupem takového algoritmu bude {\I matice vzdáleností} (pøípadnì +{\I matice dosa¾itelnosti}). Na ni se také mu¾eme dívat jako na {\I transitivní +uzávìr} zadaného grafu -- to je graf na~té¾e mno¾inì vrcholù, jeho¾ hrany +odpovídají nejkrat¹ím cestám v~grafu pùvodním. + +Jeden zpùsob, jak transitivní uzávìr spoèítat, se ihned nabízí: postupnì +spustit Dijkstrùv algoritmus pro v¹echny mo¾né volby poèáteèního vrcholu, +pøípadnì se pøed tím je¹tì zbavit záporných hran pomocí potenciálù. Tak +dosáhneme èasové slo¾itosti $\O(mn + n^2\log n)$. To je pro øídké grafy +nejlep¹í známý výsledek -- jen $\O(\log n)$-krát pomalej¹í, ne¾ je velikost +výstupu. + +Je-li graf hustý, pracují obvykle rychleji algoritmy zalo¾ené na maticích, zejména na jejich násobení. Nìkolik algoritmù tohoto druhu si nyní pøedvedeme, -a to jak pro výpoèet vzdáleností, tak pro dosa¾itelnost (transitivní uzávìr). +a to jak pro výpoèet vzdáleností, tak pro dosa¾itelnost. Graf na vstupu bude v¾dy zadán maticí délek hran -- to je matice $n\times n$, její¾ øádky i sloupce jsou indexované vrcholy a na pozici $(i,j)$ se nachází @@ -241,7 +247,7 @@ celou Pøedchozí pøevod je ov¹em trochu marnotratný. ©ikovným pou¾itím metody Rozdìl a panuj mù¾eme èasovou slo¾itost je¹tì sní¾it. Postup pøedvedeme pro dosa¾itelnost: na vstupu -tedy dostaneme matici sousednosti~$A$, výstupem má být její transitivní uzávìr~$A^*$ +tedy dostaneme matici sousednosti~$A$, výstupem má být její transitivní uzávìr~$A^*$. (matice dosa¾itelnosti). V¹echny souèiny matic v~tomto oddílu budou typu $(\lor,\land)$. Vrcholy grafu rozdìlíme na dvì mno¾iny $X$ a~$Y$ pøibli¾nì stejné velikosti, @@ -289,7 +295,7 @@ kde $\mu(k)$ zna matic $k\times k$. Jeliko¾ jistì platí $\mu(n/2)=\Omega(n^2)$, má tato rekurence podle kuchaøkové vìty øe¹ení $t(n) = \mu(n)$. -Ukázali jsme tedy, ¾e výpoèet transitivního uzávìru je nejvý¹e stejnì +Ukázali jsme tedy, ¾e výpoèet matice dosa¾itelnosti je nejvý¹e stejnì nároèný jako $(\lor,\land)$-násobení matic -- mù¾eme ho proto provést v~èase $\O(n^\omega)$. Dokonce existuje pøímoèarý pøevod v~opaèném smìru, tak¾e oba problémy jsou asymptoticky stejnì tì¾ké. -- 2.39.2