Min-plus maticové násobení

Min-plus násobení matic, známé také jako vzdálenostní součin, je maticová operace. Jde o standardní maticový součin v polookruhu tropické geometrie.

Vzdálenostní součin souvisí s problémem nejkratší cesty v teorii grafů. Je-li ${\boldsymbol {W}}$ čtvercová matice řádu $n$ obsahující délky hran grafu, pak její mocnina ${\boldsymbol {W}}^{[k]}$ vzhledem ke vzdálenostnímu součinu udává vzdálenosti mezi vrcholy při použití cest s nejvýše $k$ hranami. Matice vzdáleností grafu je pak ${\boldsymbol {W}}^{[n]}$.

Odpovídající algoritmus má pro každý krok výpočtu automaticky k dispozici všechny informace o dostupných cestách v rámci předem určeného počtu kroků výpočtu. Je však výpočetně náročný a pomalý.

Definice

Je-li $G=(V,E)$ orientovaný graf na vrcholech $V=\{v_{1},\dots ,v_{n}\}$ a $l:E\to \mathbb {R} ^{+}$je váhová funkce odpovídající délkám hran, potom váhová matice ${\boldsymbol {W}}$ je čtvercová matice řádu $n$ definovaná vztahem:

$w_{i,j}={\begin{cases}0&{\text{pro }}i=j\\l(v_{i},v_{j})&{\text{pokud }}(v_{i},v_{j})\in E\\\infty &{\text{jinak}}\end{cases}}$

Matice vzdáleností ${\boldsymbol {D}}$ je čtvercová matice řádu $n$ a má na pozici $d_{i,j}$ délku nejkratší orientované cesty z $v_{i}$ do $v_{j}$. Pokud žádná taková cesta neexistuje, je $d_{i,j}=\infty$. Matice má na diagonále samé 0.

Vzdálenostní součin

Jsou-li dány dvě čtvercové matice ${\boldsymbol {A}}$ a ${\boldsymbol {B}}$ řádu $n$, potom jejich vzdálenostní součin ${\boldsymbol {A}}\star {\boldsymbol {B}}$ je definován jako čtvercová matice ${\boldsymbol {C}}$ řádu $n$ taková, že:

$c_{ij}=\min\{a_{ik}+b_{kj}\,\colon \,k\in \{1,\dots n\}\}$,

přičemž součty, v nichž se vyskytuje nekonečno jsou definovány $a+\infty =\infty +a=\infty$ .

Součin $\star$ je tedy maticový součin přes polookruh s $(0,1,+,\cdot ):=(\infty ,0,\operatorname {min} ,+)$ .

Namísto ${\boldsymbol {W}}\star {\boldsymbol {W}}$ píšeme stručně ${\boldsymbol {W}}^{[2]}$ a podobně ${\boldsymbol {W}}^{[k+1]}={\boldsymbol {W}}^{[k]}\star {\boldsymbol {W}}$.

Souvislost s nejkratšími cestami

Pro orientovaný graf $G=(V,E)$ s nezápornými váhami hran $w_{i,j}$ nebo s konzervativní váhovou funkcí $l$ platí:

• Prvek $w_{i,j}^{[k]}$ matice ${\boldsymbol {W}}^{[k]}$ je délka nejkratší cesty s nejvýše $k$ hranami z vrcholu $v_{i}$ do vrcholu $v_{j}$.
• Je-li $n$ počet vrcholů, pak pro všechna $k\geq n-1$ platí ${\boldsymbol {W}}^{[k]}={\boldsymbol {D}}$.
• Jestliže ${\boldsymbol {W}}^{[k+1]}={\boldsymbol {W}}^{[k]}$, pak také ${\boldsymbol {W}}^{[k]}={\boldsymbol {D}}$.

Algoritmus

Algoritmus využívající vzdálenostní součin počítá stále vyšší mocniny ${\boldsymbol {W}}^{[k]}$ váhové matice ${\boldsymbol {W}}$ tak dlouho, než platí ${\boldsymbol {W}}^{[k+1]}={\boldsymbol {W}}^{[k]}={\boldsymbol {D}}$.

Varianta 1 algoritmu počítá posloupnost mocnin ${\boldsymbol {W}}^{[2]},{\boldsymbol {W}}^{[3]},{\boldsymbol {W}}^{[4]},\dots$ až platí ${\boldsymbol {W}}^{[k+1]}={\boldsymbol {W}}^{[k]}$. V každé iteraci se výsledek předchozího kroku vynásobí maticí ${\boldsymbol {W}}$.

Varianta 2 algoritmu počítá ${\boldsymbol {W}}^{[2]},{\boldsymbol {W}}^{[4]},{\boldsymbol {W}}^{[8]},\dots$ až platí ${\boldsymbol {W}}^{[2k]}={\boldsymbol {W}}^{[k]}$. Výsledek předchozího kroku se v každé iteraci umocní.

Časová složitost

Varianta 1 vyžaduje v nejhorším případě výpočet $n-2$ maticových součinů, zatímco varianta 2 jich vyžaduje nejvýše $\lceil \log _{2}(n-1)\rceil$. Časová složitost algoritmu s naivní implementací součinu je pro první variantu $O\left(n^{4}\right)$ v Landauově notaci a $O(n^{3}\log n)$ pro druhou variantu. Obě varianty algoritmu mají horší dobu běhu než Floydův–Warshallův algoritmus se složitostí ${\mathcal {O}}(n^{3})$.

Dobu běhu lze urychlit složitějšími implementacemi vzdálenostního součinu matic.

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Min-plus matrix multiplication na anglické Wikipedii a Min-Plus-Matrixmultiplikations-Algorithmus na německé Wikipedii.

Literatura

• CORMEN, Thomas H.; LEISERSON, Charles; RIVEST, Ronald L.; STEIN, Clifford. Introduction to algorithms. 2nd. ed., 10th pr. vyd. Cambridge, Mass.: MIT Press 1180 s. ISBN 978-0-262-53196-2, ISBN 978-0-262-03293-3. S. 622–627. 
• ZWICK, Uri, 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of ACM. Roč. 49, čís. 3 (květen 2002), s. 289–317. Dostupné online. 
• RODITTY, Liam; SHAPIRA, Asaf, 2008. All-Pairs Shortest Paths with a Sublinear Additive Error. In: ICALP '08, Part I, LNCS 5125. [s.l.]: [s.n.]. Dostupné online. S. 622–633.

Související články

• Floydův–Warshallův algoritmus
• Tropická geometrie
• Hledání cest

Portály: Matematika