Min-Plus-Matrixmultiplikations-Algorithmus - Versionsgeschichte

Wdvorak: /* Matrizenoperation ⊕ */

2017-01-20T12:02:01Z

Matrizenoperation ⊕

← Nächstältere Version		Version vom 20. Januar 2017, 14:02 Uhr
Zeile 23:		Zeile 23:

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

	== Zusammenhang mit Kürzesten Pfaden ==		== Zusammenhang mit Kürzesten Pfaden ==

Wdvorak: Die letzte Textänderung von 131.220.71.201 wurde verworfen und die Version 151086847 von HRoestTypo wiederhergestellt.

2017-01-20T12:01:33Z

Die letzte Textänderung von 131.220.71.201 wurde verworfen und die Version 151086847 von HRoestTypo wiederhergestellt.

← Nächstältere Version		Version vom 20. Januar 2017, 14:01 Uhr
Zeile 36:		Zeile 36:
	''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 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~~^{\lceil\log_2p\rceil}~~]} = K^{[p]}</math>.		''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.		Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert.
	=== Laufzeit ===		=== Laufzeit ===

131.220.71.201: /* Algorithmus */ Cormen, Leiserson, Rivest; mathematische Grundkenntnisse

2017-01-20T08:46:56Z

Algorithmus: Cormen, Leiserson, Rivest; mathematische Grundkenntnisse

← Nächstältere Version		Version vom 20. Januar 2017, 10:46 Uhr
Zeile 36:		Zeile 36:
	''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 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>.		''Variante 2'': Berechnet <math>K^{[2]}, K^{[4]}, K^{[8]}, ...</math> bis <math>K^{[2^{\lceil\log_2p\rceil}]} = K^{[p]}</math>.
	Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert.		Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert.
	=== Laufzeit ===		=== Laufzeit ===

HRoestTypo: Tippfehler entfernt: Implementiertungen -> Implementierungen

2016-02-05T01:49:48Z

Tippfehler entfernt: Implementiertungen -> Implementierungen

← Nächstältere Version		Version vom 5. Februar 2016, 03:49 Uhr
Zeile 44:		Zeile 44:
	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.		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 ~~Implementiertungen~~ der Min-Plus-Matrixmultiplikation verbessert werden.		Die Laufzeit kann jedoch durch kompliziertere Implementierungen der Min-Plus-Matrixmultiplikation verbessert werden.

	== Siehe auch ==		== Siehe auch ==

188.118.174.195: /* Laufzeit */ Tippfehler korrigiert

2015-12-06T11:20:58Z

Laufzeit: Tippfehler korrigiert

← Nächstältere Version		Version vom 6. Dezember 2015, 13:20 Uhr
Zeile 41:		Zeile 41:
	Im Folgenden verwenden wir die [[Landau-Notation]], um das asymptotische Verhalten der Laufzeit anzugeben.		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.		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 ~~Implementiertung~~ 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.		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.		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.

Leyo: Bis-Strich ≠ Minuszeichen

2015-11-25T01:34:56Z

Bis-Strich ≠ Minuszeichen

← Nächstältere Version		Version vom 25. November 2015, 03:34 Uhr
Zeile 50:		Zeile 50:

	== Quellen ==		== 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~~		* 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)]]		[[Kategorie:Algorithmus (Graphentheorie)]]

Aka: Tippfehler entfernt

2013-11-20T14:55:42Z

Tippfehler entfernt

← Nächstältere Version		Version vom 20. November 2013, 16:55 Uhr
Zeile 42:		Zeile 42:
	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.		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 Implementiertung 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.		Die Laufzeit mit der naiven Implementiertung 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 ~~vergleichabre~~ [[Algorithmus von Floyd und Warshall]] dessen Laufzeit in <math> \mathcal{O}(n^3) </math> ist.		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 Implementiertungen der Min-Plus-Matrixmultiplikation verbessert werden.		Die Laufzeit kann jedoch durch kompliziertere Implementiertungen der Min-Plus-Matrixmultiplikation verbessert werden.

Quartl: /* Einleitung */ link

2013-08-21T20:18:16Z

Einleitung: link

← Nächstältere Version		Version vom 21. August 2013, 22:18 Uhr
Zeile 1:		Zeile 1:
	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 ~~Matrizenoperation~~ 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.		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 ==		== Definitionen ==

Wdvorak: /* Zusammenhang mit Kürzesten Pfaden */ vereinfacht

2013-08-06T18:52:33Z

Zusammenhang mit Kürzesten Pfaden: vereinfacht

← Nächstältere Version		Version vom 6. August 2013, 20:52 Uhr
Zeile 28:		Zeile 28:
	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:		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.		* 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 ~~gibt~~ <math>K^{[~~n-1~~]} =~~(k^{[n-1]}_{i,j})~~</math> ~~die~~ ~~Länge der kürzesten Pfade an. Der Eintrag~~ <math>~~k^{[~~n-1~~]}_{i,j}~~</math> ~~gibt dabei die Länges des kürzesten Pfad 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>n</math> die Anzahl der Knoten ist dann gilt~~ <math>K^{[n-1]} = K^{[m]}</math> ~~für~~ ~~alle~~ <math>~~m\geq~~ n</math>.		* Wenn <math>K^{[p+1]} = K^{[p]}</math> dann auch <math>K^{[p]} = D</math>.
	* Wenn <math>K^{[p+1]} = K^{[p]}</math> dann auch <math>K^{[p]} = K^{[n-1]}</math>.

	== Algorithmus ==		== Algorithmus ==

Wdvorak: /* Algorithmus */ + Laufzeit

2013-08-06T18:49:35Z

Algorithmus: + Laufzeit

← Nächstältere Version		Version vom 6. August 2013, 20:49 Uhr
Zeile 33:		Zeile 33:

	== Algorithmus ==		== 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>.
	1. <math>K</math> sei die Kostenmatrix des Netzwerkes N

	2. ~~Berechne~~ <math>K^{[2]}, K^{[3]}, K^{[4]}, ...</math> ~~gilt~~ ~~irgendwann~~ <math>K^{[p+1]} = K^{[p]}</math>, so ~~ist~~ <math>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>.
	oder
			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 Implementiertung 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 vergleichabre [[Algorithmus von Floyd und Warshall]] dessen Laufzeit in <math> \mathcal{O}(n^3) </math> ist.

			Die Laufzeit kann jedoch durch kompliziertere Implementiertungen der Min-Plus-Matrixmultiplikation verbessert werden.
⚫	2. ~~Berechne~~ <math>K^{[2]}, K^{[4]}, K^{[8]}, ...</math> ~~gilt irgendwann~~ <math>K^{[2*p]} = K^{[p]}</math>~~, so ist <math>K^{[p]}=D</math>~~

	== Siehe auch ==		== Siehe auch ==