imported>Wdvorak: /* Matrizenoperation ⊕ */

2017-01-20T12:02:01Z

Matrizenoperation ⊕

Neue Seite

Der '''Min-Plus-Matrixmultiplikations-Algorithmus''' ist ein [[Algorithmus]] der [[Graphentheorie]], der die [[Kürzester Pfad|kürzesten Pfade]] eines [[Graph (Graphentheorie)|Graphen]] berechnet. Er läuft mit einer speziellen [[Matrizenmultiplikation]] und hat zudem den Vorteil, dass bei jedem Berechnungsschritt automatisch alle Informationen über erreichbare Wege innerhalb der bisher angegebenen Anzahl der Berechnungsschritte verfügbar sind. Er ist allerdings sehr rechenintensiv und daher langsam.

== Definitionen ==
Gegeben seien ein gerichteter Graph <math>G = (V,E)</math> und eine Matrix mit Gewichten <math>c_{i,j}</math>, wobei die Indizes <math>i</math> und <math>j</math> über die Menge <math>V</math> laufen.

=== Bewertungsmatrix ===
Die ''Kostenmatrix'' oder ''Bewertungsmatrix'' <math>K</math> ist dann wie folgt definiert:
:<math>k_{i,j}=\begin{cases} 0~\mathrm{falls}~i=j \\ c_{i,j}~\mathrm{falls}~ (i,j) \in E \\ \infty~\mathrm{sonst}\end{cases}</math>

=== Entfernungsmatrix ===
Die ''Entfernungsmatrix'' <math>D</math> ist wie folgt definiert
:<math>d_{i,j}=\begin{cases} 0,~\mathrm{falls}~i=j \\
\mathrm{L\ddot ange~des~k\ddot urzesten~Weges~von~} i \mathrm{~nach~} j\\
\infty,~\mathrm{falls~es~keinen~Weg~gibt}~\end{cases}</math>

=== Matrizenoperation ⊕ ===
<math>F,G</math> seien zwei <math>n\times n</math>-Matrizen.
Die Matrix <math>H = F \oplus G</math> berechnet sich wie folgt:
:<math>h_{i,j} = \min \{ f_{i,l}+g_{l,j} \mid l \in \{ 1,\dots,n \}\}</math>
wobei gelten soll <math>a + \infty = \infty + a = \infty</math>.

<math>\oplus</math> ist also die Multiplikation von Matrizen über einem [[Halbring (Algebraische Struktur)|Halbring]] mit <math>(0,1,+,\cdot) := (\infty, 0, \operatorname{min}, +)</math>.

Statt <math>K \oplus K</math> schreiben wir kurz <math>K^{[2]}</math>.
:<math>K^{[i+1]}=K^{[i]} \oplus K</math>

== Zusammenhang mit Kürzesten Pfaden ==
Für einen gerichteten Graph <math>G = (V,E)</math> mit positiven Kantengewichten <math>c_{i,j}</math> (oder mit [[Kürzester Pfad#Komplexität|konservativer Gewichtsfunktion]]) gilt:
* Die Matrix <math>K^{[p]} =(k^{[p]}_{i,j})</math> gibt die Länge der kürzesten Pfade mit maximal <math>p</math> Kanten an. Der Eintrag <math>k^{[p]}_{i,j}</math> gibt dabei die Länges des kürzesten Pfad (mit maximal <math>p</math> Kanten) von Knoten <math>i</math> zu Knoten <math>j</math> an.
* Wenn <math>n</math> die Anzahl der Knoten ist dann gilt <math>K^{[p]} = D</math> für alle <math>p\geq n-1</math>.
* Wenn <math>K^{[p+1]} = K^{[p]}</math> dann auch <math>K^{[p]} = D</math>.

== Algorithmus ==
Der Min-Plus-Matrixmultiplikations-Algorithmus berechnet nun ausgehend von der Kostenmatrix <math>K</math> des Graph <math>K^{[p]}</math> sodass <math>K^{[p+1]} = K^{[p]}=D</math>.

''Variante 1'': Berechnet <math>K^{[2]}, K^{[3]}, K^{[4]}, ...</math> bis <math>K^{[p+1]} = K^{[p]}</math>. Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes mit der Matrix <math>K</math> multipliziert.

''Variante 2'': Berechnet <math>K^{[2]}, K^{[4]}, K^{[8]}, ...</math> bis <math>K^{[2*p]} = K^{[p]}</math>.
Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert.
=== Laufzeit ===
Im Folgenden verwenden wir die [[Landau-Notation]], um das asymptotische Verhalten der Laufzeit anzugeben.
Im ''worst case'' benötigt Variante 1 <math>\Theta\left(n\right)</math> Matrixmultiplikationen während Variante 2 nur <math>\Theta\left( \log n\right)</math> Matrixmultiplikationen benötigt.
Die Laufzeit mit der naiven Implementierung der Min-Plus-Matrixmultiplikation ist dann in <math>\Theta\left( n^4 \right)</math> für Variante 1 und in <math>\Theta\left( n^3 \cdot \log n \right)</math> für Variante 2.
Damit hat der Algorithmus eine schlechtere Laufzeit als der vergleichbare [[Algorithmus von Floyd und Warshall]] dessen Laufzeit in <math> \mathcal{O}(n^3) </math> ist.

Die Laufzeit kann jedoch durch kompliziertere Implementierungen der Min-Plus-Matrixmultiplikation verbessert werden.

== Siehe auch ==
* [[Pathfinding]]

== Quellen ==
* Thomas H. Cormen, [[Charles Leiserson]], [[Ronald L. Rivest]], Clifford Stein: ''Introduction to Algorithms.'' 2. Auflage. MIT Press, 2001, ISBN 0-262-53196-8, S. 622–627

[[Kategorie:Algorithmus (Graphentheorie)]]

Min-Plus-Matrixmultiplikations-Algorithmus - Versionsgeschichte

imported>Wdvorak: /* Matrizenoperation ⊕ */