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 obsahující délky hran grafu, pak její mocnina vzhledem ke vzdálenostnímu součinu udává vzdálenosti mezi vrcholy při použití cest s nejvýše hranami. Matice vzdáleností grafu je pak .
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 orientovaný graf na vrcholech a je váhová funkce odpovídající délkám hran, potom váhová matice je čtvercová matice řádu definovaná vztahem:
Matice vzdáleností je čtvercová matice řádu a má na pozici délku nejkratší orientované cesty z do . Pokud žádná taková cesta neexistuje, je . Matice má na diagonále samé 0.
Vzdálenostní součin Jsou-li dány dvě čtvercové matice a řádu , potom jejich vzdálenostní součin je definován jako čtvercová matice řádu taková, že:
,
přičemž součty, v nichž se vyskytuje nekonečno jsou definovány .
Součin je tedy maticový součin přes polookruh s .
Namísto píšeme stručně a podobně .
Souvislost s nejkratšími cestami Pro orientovaný graf s nezápornými váhami hran nebo s konzervativní váhovou funkcí Váhová funkce se nazývá konzervativní, jestliže pro každý orientovaný cyklus grafu platí . platí:
Prvek matice je délka nejkratší cesty s nejvýše hranami z vrcholu do vrcholu . Je-li počet vrcholů, pak pro všechna platí . Jestliže , pak také .
Algoritmus Algoritmus využívající vzdálenostní součin počítá stále vyšší mocniny váhové matice tak dlouho, než platí .
Varianta 1 algoritmu počítá posloupnost mocnin až platí . V každé iteraci se výsledek předchozího kroku vynásobí maticí .
Varianta 2 algoritmu počítá až platí . 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 maticových součinů, zatímco varianta 2 jich vyžaduje nejvýše . Časová složitost algoritmu s naivní implementací součinu je pro první variantu v Landauově notaci a pro druhou variantu. Obě varianty algoritmu mají horší dobu běhu než Floydův–Warshallův algoritmus se složitostí .
Dobu běhu lze urychlit složitějšími implementacemi vzdálenostního součinu matic.
Odkazy Poznámky
Reference
Literatura
Související články Floydův–Warshallův algoritmus Tropická geometrie Hledání cest
Kategorie:Grafové algoritmy Kategorie:Teorie matic Kategorie:Vzdálenosti v grafu