www.wikidata.de-de.nina.az

Min Plus Matrixmultiplikations Algorithmus Der ist ein Algorithmus der Graphentheorie der die kürzesten Pfade eines Grap

Min-Plus-Matrixmultiplikations-Algorithmus

Der Min-Plus-Matrixmultiplikations-Algorithmus ist ein Algorithmus der Graphentheorie, der die kürzesten Pfade eines 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 Bearbeiten

Gegeben seien ein gerichteter Graph und eine Matrix mit Gewichten , wobei die Indizes und über die Menge laufen.

Bewertungsmatrix Bearbeiten

Die Kostenmatrix oder Bewertungsmatrix ist dann wie folgt definiert:

Entfernungsmatrix Bearbeiten

Die Entfernungsmatrix ist wie folgt definiert

Matrizenoperation ⊕ Bearbeiten

seien zwei -Matrizen. Die Matrix berechnet sich wie folgt:

wobei gelten soll .

ist also die Multiplikation von Matrizen über einem Halbring mit .

Statt schreiben wir kurz .

Zusammenhang mit Kürzesten Pfaden Bearbeiten

Für einen gerichteten Graph mit positiven Kantengewichten (oder mit konservativer Gewichtsfunktion) gilt:

  • Die Matrix gibt die Länge der kürzesten Pfade mit maximal Kanten an. Der Eintrag gibt dabei die Länges des kürzesten Pfad (mit maximal Kanten) von Knoten zu Knoten an.
  • Wenn die Anzahl der Knoten ist dann gilt für alle .
  • Wenn dann auch .

Algorithmus Bearbeiten

Der Min-Plus-Matrixmultiplikations-Algorithmus berechnet nun ausgehend von der Kostenmatrix des Graph sodass .

Variante 1: Berechnet bis . Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes mit der Matrix multipliziert.

Variante 2: Berechnet bis . Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert.

Laufzeit Bearbeiten

Im Folgenden verwenden wir die Landau-Notation, um das asymptotische Verhalten der Laufzeit anzugeben. Im worst case benötigt Variante 1 Matrixmultiplikationen während Variante 2 nur Matrixmultiplikationen benötigt. Die Laufzeit mit der naiven Implementierung der Min-Plus-Matrixmultiplikation ist dann in für Variante 1 und in für Variante 2. Damit hat der Algorithmus eine schlechtere Laufzeit als der vergleichbare Algorithmus von Floyd und Warshall dessen Laufzeit in ist.

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

Siehe auch Bearbeiten

Quellen Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Min Plus Matrixmultiplikations Algorithmus ist ein Algorithmus der Graphentheorie der die kurzesten Pfade eines Graphen berechnet Er lauft mit einer speziellen Matrizenmultiplikation und hat zudem den Vorteil dass bei jedem Berechnungsschritt automatisch alle Informationen uber erreichbare Wege innerhalb der bisher angegebenen Anzahl der Berechnungsschritte verfugbar sind Er ist allerdings sehr rechenintensiv und daher langsam Inhaltsverzeichnis 1 Definitionen 1 1 Bewertungsmatrix 1 2 Entfernungsmatrix 1 3 Matrizenoperation 2 Zusammenhang mit Kurzesten Pfaden 3 Algorithmus 3 1 Laufzeit 4 Siehe auch 5 QuellenDefinitionen BearbeitenGegeben seien ein gerichteter Graph G V E displaystyle G V E nbsp und eine Matrix mit Gewichten c i j displaystyle c i j nbsp wobei die Indizes i displaystyle i nbsp und j displaystyle j nbsp uber die Menge V displaystyle V nbsp laufen Bewertungsmatrix Bearbeiten Die Kostenmatrix oder Bewertungsmatrix K displaystyle K nbsp ist dann wie folgt definiert k i j 0 f a l l s i j c i j f a l l s i j E s o n s t displaystyle k i j begin cases 0 mathrm falls i j c i j mathrm falls i j in E infty mathrm sonst end cases nbsp Entfernungsmatrix Bearbeiten Die Entfernungsmatrix D displaystyle D nbsp ist wie folgt definiert d i j 0 f a l l s i j L a n g e d e s k u r z e s t e n W e g e s v o n i n a c h j f a l l s e s k e i n e n W e g g i b t displaystyle d i j begin cases 0 mathrm falls i j mathrm L ddot a nge des k ddot u rzesten Weges von i mathrm nach j infty mathrm falls es keinen Weg gibt end cases nbsp Matrizenoperation Bearbeiten F G displaystyle F G nbsp seien zwei n n displaystyle n times n nbsp Matrizen Die Matrix H F G displaystyle H F oplus G nbsp berechnet sich wie folgt h i j min f i l g l j l 1 n displaystyle h i j min f i l g l j mid l in 1 dots n nbsp wobei gelten soll a a displaystyle a infty infty a infty nbsp displaystyle oplus nbsp ist also die Multiplikation von Matrizen uber einem Halbring mit 0 1 0 min displaystyle 0 1 cdot infty 0 operatorname min nbsp Statt K K displaystyle K oplus K nbsp schreiben wir kurz K 2 displaystyle K 2 nbsp K i 1 K i K displaystyle K i 1 K i oplus K nbsp Zusammenhang mit Kurzesten Pfaden BearbeitenFur einen gerichteten Graph G V E displaystyle G V E nbsp mit positiven Kantengewichten c i j displaystyle c i j nbsp oder mit konservativer Gewichtsfunktion gilt Die Matrix K p k i j p displaystyle K p k i j p nbsp gibt die Lange der kurzesten Pfade mit maximal p displaystyle p nbsp Kanten an Der Eintrag k i j p displaystyle k i j p nbsp gibt dabei die Langes des kurzesten Pfad mit maximal p displaystyle p nbsp Kanten von Knoten i displaystyle i nbsp zu Knoten j displaystyle j nbsp an Wenn n displaystyle n nbsp die Anzahl der Knoten ist dann gilt K p D displaystyle K p D nbsp fur alle p n 1 displaystyle p geq n 1 nbsp Wenn K p 1 K p displaystyle K p 1 K p nbsp dann auch K p D displaystyle K p D nbsp Algorithmus BearbeitenDer Min Plus Matrixmultiplikations Algorithmus berechnet nun ausgehend von der Kostenmatrix K displaystyle K nbsp des Graph K p displaystyle K p nbsp sodass K p 1 K p D displaystyle K p 1 K p D nbsp Variante 1 Berechnet K 2 K 3 K 4 displaystyle K 2 K 3 K 4 nbsp bis K p 1 K p displaystyle K p 1 K p nbsp Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes mit der Matrix K displaystyle K nbsp multipliziert Variante 2 Berechnet K 2 K 4 K 8 displaystyle K 2 K 4 K 8 nbsp bis K 2 p K p displaystyle K 2 p K p nbsp Dabei wird in jedem Schritt das Ergebnis des letzten Schrittes quadriert Laufzeit Bearbeiten Im Folgenden verwenden wir die Landau Notation um das asymptotische Verhalten der Laufzeit anzugeben Im worst case benotigt Variante 1 8 n displaystyle Theta left n right nbsp Matrixmultiplikationen wahrend Variante 2 nur 8 log n displaystyle Theta left log n right nbsp Matrixmultiplikationen benotigt Die Laufzeit mit der naiven Implementierung der Min Plus Matrixmultiplikation ist dann in 8 n 4 displaystyle Theta left n 4 right nbsp fur Variante 1 und in 8 n 3 log n displaystyle Theta left n 3 cdot log n right nbsp fur Variante 2 Damit hat der Algorithmus eine schlechtere Laufzeit als der vergleichbare Algorithmus von Floyd und Warshall dessen Laufzeit in O n 3 displaystyle mathcal O n 3 nbsp ist Die Laufzeit kann jedoch durch kompliziertere Implementierungen der Min Plus Matrixmultiplikation verbessert werden Siehe auch BearbeitenPathfindingQuellen BearbeitenThomas 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 Abgerufen von https de wikipedia org w index php title Min Plus Matrixmultiplikations Algorithmus amp oldid 161816249