blob: 76fb3b064dfea8b526a00a11d85b40a5113e5ebb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
\section{Ausblick}
\rhead{Ausblick}
\subsection{Optimierungsprobleme bei Graphen}
Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Graphen aufstellen lassen.
Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen.
Im Bereich vom Computernetzwerken könnte zum Beispiel die Minimierung der Knotenzahl zur Datenübbertragung von Interesse sein.
Dabei lässt sich dieses Problem einfach dadurch lösen, dass dem Dijkstra- oder dem A*-Algorithmus anstelle der gewichteten Adjazenz-Matrix (mit Kantengewichten als Einträgen) die ungewichtet Adjazenz-Matrix als Argument übergeben wird.
Der gefundene kürzeste Pfad enstpricht der Anzahl benutzter Kanten, bzw. der Anzahl besuchter Knoten.
\subsection{Wahl der Heuristik}
Ein grundlegendes Problem bei der Anwendung des A* oder ähnlicher informierter Suchalgorithmen ist die Wahl der Heurstik.
Bei einem physischen Verkehrsnetz kann bspw.~die euklidische Distanz problems ermittelt werde.
Bei einem regionalen Netzwerk ist die Annahme eines orthogonalen X-Y-Koordinatenetzes absolut ausreichend.
Dies gilt z.~B.~auch für das Vernessungsnetz der Schweiz\footnote{Die aktuelle Schweizer Referenzsystem LV95 benutzt ein E/N-Koordinatennetz, wobei aufgrund zunehmender Abweichung vom Referenzellipsoid bei grosser Entfernung vom Nullpunkt ein Korrekturfaktor für die Höhe angebracht werden muss.}.
Bei überregionalen Netzwerken (Beispiel: Flugverbindungen) ist hingegen eine Berechnung im dreidimensionalen Raum, oder vereinfacht als Projektion auf das Geoid notwendig.
Ansonsten ist der Ablauf bei der Ausführung des Algorithmus allerdings identisch.
In nicht-physischen Netzwerken stellt sich jedoch eine zweite Problematik.
Da eine physische Distanz entweder nicht ermittelt werden kann, oder aber nicht ausschlaggebend ist, sind andere Netzwerk-Eigenschaften zur Beurteilung beizuziehen.
Die Zuverlässigkeit ist dabei aber in den meisten Fällen nicht vergleichbar hoch, wie bei der euklidischen Heuristik.
Oftmals werden deshalb bei derartigen Problem auch Algorithmen angewendet, die eine deutlich optimierte Zeitkomplexität aufweisen, dafür aber nicht mit Sicherheit den effizienstesten Pfad finden.
|
