Přeskočit na obsah

Min-plus maticové násobení

Z Wikipedie, otevřené encyklopedie

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ý.

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

[editovat | editovat zdroj]

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

[editovat | editovat zdroj]

Pro orientovaný graf s nezápornými váhami hran nebo s konzervativní váhovou funkcí [pozn. 1] 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

[editovat | editovat zdroj]

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

[editovat | editovat zdroj]

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.

  1. Váhová funkce se nazývá konzervativní, jestliže pro každý orientovaný cyklus grafu platí .

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

[editovat | editovat zdroj]
  • 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

[editovat | editovat zdroj]