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 $𝑾$ čtvercová matice řádu $n$ obsahující délky hran grafu, pak její mocnina ${𝑾}^{[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 ${𝑾}^{[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 {ℝ}^{+}$je váhová funkce odpovídající délkám hran, potom váhová matice $𝑾$ je čtvercová matice řádu $n$ definovaná vztahem:

$w_{i,j}=\{\begin{array}{cc}0& \text{pro }i=j\\ l(v_i,v_j)& \text{pokud }(v_i,v_j)\in E\\ \mathrm{\infty }& \text{jinak}\end{array}$

Matice vzdáleností $𝑫$ 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}=\mathrm{\infty }$. Matice má na diagonále samé 0.

Vzdálenostní součin

Jsou-li dány dvě čtvercové matice $𝑨$ a $𝑩$ řádu $n$, potom jejich vzdálenostní součin $𝑨\star 𝑩$ je definován jako čtvercová matice $𝑪$ řádu $n$ taková, že:

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

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

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

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

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 ${𝑾}^{[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\ge n-1$ platí ${𝑾}^{[k]}=𝑫$.
• Jestliže ${𝑾}^{[k+1]}={𝑾}^{[k]}$, pak také ${𝑾}^{[k]}=𝑫$.

Algoritmus

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

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

Varianta 2 algoritmu počítá ${𝑾}^{[2]},{𝑾}^{[4]},{𝑾}^{[8]},\dots$ až platí ${𝑾}^{[2k]}={𝑾}^{[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í $𝒪(n^3)$.

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

Odkazy

Literatura

• Šablona:Citace monografie
• Šablona:Citace periodika
• Šablona:Citace sborníku

Související články

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