Das Kefk Network Wiki befindet sich im Testbetrieb.

Berge-Hasse-Algorithmus

Aus Kefk.

Wechseln zu: Navigation, Suche

Der Berge-Hasse-Algorithmus ist ein Algorithmus der Graphentheorie, der die Distanzmatrix eines 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.

Inhaltsverzeichnis

Definitionen

Bewertungsmatrix

Gegeben sei ein Netzwerk K_{i,k}=\begin{cases} 0~\mathrm{falls}~i=j \\ c~\mathrm{falls}~j \in i \\ \infty~\mathrm{sonst}\end{cases}

heißt Kostenmatrix oder Bewertungsmatrix von N .

Entfernungsmatrix

Gegeben sei ein Netzwerk N. Die (n,n) - Matrix D mit d_{i,k}=\begin{cases} 0~\mathrm{falls}~i=j \\ \mathrm{Weg~von}~i~\mathrm{nach}~j~\mathrm{(falls}~j \in R(i)) \\ \infty~\mathrm{sonst}~\end{cases}

heißt Entfernungsmatrix von N.

F,G seien (n,n) – Matrizen. Es sei H := F ⊕ G mit h_{i,j} = min \lbrace f_{i,l}+g_{l,j} \vert \lbrace 1,.... \rbrace \rbrace~\mathrm{fuer}~i,j \in \lbrace 1,....,\rbrace

wobei gelten soll; a + ∞ = ∞ + a = ∞ .

Algorithmus

1. K sei die Kostenmatrix des Netzwerkes N

2. Berechne K[2],K[3],K[4],... gilt irgendwann K[p + 1] = K[p], so ist K[p] = D

oder

2. Berechne K[2],K[4],K[8],... gilt irgendwann K[2 * p] = K[p], so ist K[p] = D


Siehe auch: Pathfinding

Quellen

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Berge-Hasse-Algorithmus, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Berge-Hasse-Algorithmus“
Persönliche Werkzeuge