Min-plus maticové násobení

Technology

12 hours ago

Author

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. +more 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 \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. +more 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 Váhová funkce se nazývá konzervativní, jestliže pro každý orientovaný cyklus C grafu G platí \sum_{e \in C} l(e) \geq 0 . platí:

* Prvek w^{[k] }_{i,j} 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}. +more * 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. +more 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.