aboutsummaryrefslogtreecommitdiffstats
path: root/buch
diff options
context:
space:
mode:
authorPascal Schmid <81317360+paschost@users.noreply.github.com>2021-07-27 15:48:46 +0200
committerGitHub <noreply@github.com>2021-07-27 15:48:46 +0200
commit45e525ce336712b0b75d2431b130d09835857382 (patch)
tree755bdc8a3b573ce91bf03dc579fa279e8432835c /buch
parentAnpassungen Abschnitt Versuchsreihe (diff)
downloadSeminarMatrizen-45e525ce336712b0b75d2431b130d09835857382.tar.gz
SeminarMatrizen-45e525ce336712b0b75d2431b130d09835857382.zip
Anpassungen Abschnitt Ausblick
Diffstat (limited to '')
-rw-r--r--buch/papers/verkehr/section3.tex7
1 files changed, 4 insertions, 3 deletions
diff --git a/buch/papers/verkehr/section3.tex b/buch/papers/verkehr/section3.tex
index 99a0d92..9aa8ae4 100644
--- a/buch/papers/verkehr/section3.tex
+++ b/buch/papers/verkehr/section3.tex
@@ -1,8 +1,9 @@
\section{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 Grafen 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 \emph{Dijkstra}, oder dem \emph{A*}-Algorithmus anstelle der Graph-Matrix (mit Kantengewichten als Einträgen) die Adjazenz-Matrix als Argument übergeben wird. Der gefundene kürzeste Pfad enstpricht der Anzahl benutzter Kanten, bzw. der Anzahl besuchter Knoten.
+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 \emph{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. Anonsten ist der Ablauf bei der Ausführung des Algorithmus allerdings identisch.\\
+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. Anonsten 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.