From 45d314f08914f3a507e989df1eb1b0f75d9e1e33 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Sun, 18 Jul 2021 21:28:19 +0200 Subject: =?UTF-8?q?Erg=C3=A4nzunugen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Erläuterungen zu Dijkstra- und A*-Algorithmus angebracht. --- buch/papers/verkehr/section1.tex | 72 +++++++++++++++++++++++++++++++++------- 1 file changed, 60 insertions(+), 12 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6a5dc28..d96d450 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -2,35 +2,83 @@ \label{section:verkehr/einfuehrung} \subsection{Verkehrsnetze} -Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, auf denen eine räumliche Fortbewegung von Personen oder auch Gütern stattfindet. Verkehrsnetze sind ein Bestandteil der Verkehrsinfrastruktur, die auf topografischen Karten festgehalten werden. Sie umfassen den Schienenverkehr, alle Strassen und Wege, wie auch Flugplätze und alle dazugehörigen Bauwerke. +Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, auf denen eine räumliche Fortbewegung von Personen oder auch Gütern stattfindet. Verkehrsnetze sind ein Bestandteil der Verkehrsinfrastruktur, die auf topografischen Karten festgehalten werden. Sie umfassen den Schienenverkehr, alle Strassen und Wege, wie auch Flugplätze und alle dazugehörigen Bauwerke. Aus verkehrsgeografischer Sicht besteht das Verkehrsnetz aus Kanten, Knotenpunkten und dem Hinterland. Die Knotenpunkte werden auch hier durch die Kanten verbunden, die den Verkehrsstrom aufnehmen, wobei das Hinterland durch einzelne Knoten versorgt wird. Die Aufteilung in Kanten und Knotenpunkte ermöglicht eine Vereinfachung komplexer Verkehrsnetze, damit sie mittels der Graphentheorie untersucht werden können. -Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim -Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes. +Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes. Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. \subsection{Suchalgorithmen} \subsubsection{Dijkstra-Algorithmus} Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Infomratikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. -Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. +Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. Trotz der Schnelligkeit der Greedy-Algorithmen, können viele Probleme nicht optimal gelöst werden. Vereinfacht wird beim Dijkstra-Algorithmus, ausgehend von einem Startknoten so lange dem kürzesten Pfad gefolgt, bis der Zielknoten erreicht wird. Dabei muss für jeden besuchten Knoten die Kostenfunktion als auch der Pfad dahin (vorheriger Knoten) gespeichert werden. Dadurch wird hingegen garantiert, dass, wenn der Zielknoten erreicht wird, auch der kürzeste Pfad gefunden wurde. Grundlegende Voraussetzung für den Dijkstra-Algorithmus ist die strikte Positivität der Kantengewichte. Andernfalls würde ein wiederholtes Ablaufen einer Kante mit negativem Gewicht zu einer stetigen Reduktion der Kostenfunktion führen, was zu einer unendlichen Schlaufe führen würde. +Gegeben sei ein Netzwerk mit $n$ Knoten und dem Startknoten $a$. +Alle Kanten sind mit $k(i, j)$ bewertet. +Gesucht wird der kürzeste Pfad zwischen dem Startknoten und allen übrigen Knoten im Netz. +$D(i)$ ist die kürzeste Distanz vom Startknoten $a$ zum Knoten $i, V(i)$ ist der unmittelbare Vorgängerknoten vom Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Konten $i$ und die Menge $M$ ist die Menge einer bestimmten Auswahl an Knoten. + +Dabei gilt +\begin{equation}M={a}\end{equation} +\begin{equation}D(a)=0\end{equation} wobei +\begin{equation}D(i)=\infty\end{equation} und +\begin{equation}i \neq a \end{equation} +Ausserdem gilt \begin{equation}V(i)=(-) \text{für alle Knoten $i$}\end{equation}\\ + +%THEORIE... +Iteration + +1. Auswahl eines Knotens \begin{equation} K\in M \text{mit} D(K)=D(i);i\in M\end{equation} + +2. Für alle Nachfolger $N(j)$ vom Knoten $K$ gilt: +\begin{equation}D(K) + k_Kj < D(j)\end{equation} dann wird \begin{equation}D(j) = D(K) + k_Kj, V(j) = K\end{equation} gesetzt und somit wird der Knoten $j$ in die Menge $M$ aufgenommen. + +3. Der ausgewählte Knoten \begin{equation}K\in M\text{wird aus der Menge herausgelöscht}\end{equation}\\ +Diese drei Schritte werden so lange wiederholt bis gilt +\begin{equation}M=\{\}\end{equation} + \subsubsection{A*-Algorithmus} Suchalgorithmen werden nach einfachen (uninformierte) und heuristischen (informierten) Algorithmen unterschieden. Während einfache Algorithmen den Suchraum intuitiv durchsuchen, beziehen heuristische Algorithmen Wissen über den Suchraum mit ein. Der A*-Algorithmus geht auf seine Erfinder Peter Hart, Nils Nilsson und Bertram Raphael zurück, die den Algorithmus erstmals im Jahr 1968 beschrieben. Der A*-Algorithmus ist ein heuristischer Suchalgorithmus, der den kürzesten Pfad zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten berechnet. -Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätzfunktion, die sogenannte Heuristik, verwendet. Dies ermöglicht ein zielgerichtetes Suchen und gleichzeitig wird die Laufzeit verringert. +Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätzfunktion, die sogenannte Heuristik, verwendet. Dies ermöglicht ein zielgerichtetes Suchen und gleichzeitig wird die Laufzeit verringert. Ausserdem findet der A*-Algorithmus immer eine optimale Lösung, sofern eine vorhanden ist. -Der A*-Algorithmus wird als Verallgemeinerung gehandhabt und gilt als Erweiterung des Dijkstra-Algorithmus. -======= +Der A*-Algorithmus wird als Verallgemeinerung gehandhabt und gilt als Erweiterung des Dijkstra-Algorithmus. + +\subsubsection{Anwendung A*-Algorithmus} +Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch die optimalste Lösung darstellt.\\ + +Die Kantengewichte werden für jeden Knoten in Form einer Funktion dargestellt +\begin{equation}f(n)=g(n)\end{equation} mit +\begin{equation}g(n)=\text{Summe aller Kantengewichte vom Startknoten bis n}\end{equation}\\ +Der A*-Algorithmus erweitert die Vorgehensweise des Algorithmus von Dijkstra um die Heuristik $h(n)$, die für jeden Knoten $n$ die geschätzte Entfernung zum Zielknoten beschreibt. +Somit gilt: +\begin{equation}f(n)=g(n)+h(n)\end{equation}\\ +Wie auch der Algorithmus von Dijkstra findet der A*-Algorithmus die optimalste Lösung. \subsubsection{Floyd-Warshall-Algorithmus} -Der Floyd-Warshall-Algorithmus wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. -Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die kürzesten , beziehungsweise die optimalsten Wege zwischen allen Paaren von Knoten berechnet, sofern der Graph keinen negativen Kreis (Zyklus) aufweist. -Ein Kreis in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird. +Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. +Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die kürzesten , beziehungsweise die optimalsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. +Ein Kreis (Zyklus) in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird.\\ +Der Floyd-Warshall-Algorithmus besteht grundsätzlich aus Floyd's Berechnung der kürzesten Distanzen zwischen zwei Knoten und Warshall's Konstruktion der kürzesten Wege. Werden diese beiden Teilgebiete zusammengefügt, ergibt sich der Floyd-Warshall-Algorithmus. + +\subsubsection{Anwendung Floyd-Warshall-Algorithmus} + +Wie oben erwähnt, besteht der Floyd-Warshall-Algorithmus aus dem Teil von Floyd zur Berechnung der kürzesten Pfade und dem Teil von Warshall zur Konstruktion der kürzesten Pfade. + +%THEORIE... +Als erstes wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W[i, j]$ erstellt. +Der Algorithmus berechnet danach in einer Hauptschleife alle Knoten $k$ von 1 bis $n$. +Dabei versucht er in jeder Iteration alle Wege von $i$ nach $j$ durch die Wege $(i, k)$ und $(k, j)$ zu verbessern. +Falls dieser mögliche Umweg zu einer Verbesserung führt, wird der Algorithmus aktualisiert. + +Die aktuelle Gewichtung der Pfade wird mit +\begin{equation}d[i, j]=min[d[i,j], d[i,k] + d[k,i]]\end{equation} +ermittelt. \subsubsection{Euklidische Heuristik} Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. @@ -40,7 +88,7 @@ Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc.. Beim PageRank-Algorithmus handelt es sich um den Algorithmus von Google, aus dem die Google-Matrix abgeleitet wird. Die Google-Matrix ist eine immens grosse Matrix mit Millionen Zeilen und Spalten, die für die schnelle und vor allem exakte Bestimmung der PageRanks (Gewichtung) eine grosse Bedeutung hat. -Der PageRank-Algorithmus analysiert und gewichtet beispielsweise die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur. +Der PageRank-Algorithmus analysiert und gewichtet beispielsweise die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.\\ Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche gilt. @@ -49,7 +97,7 @@ Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseina \begin{equation} A_{i,j}=\left\{ \begin{matrix} -1 & \text{Kante von $j$ nach $i$} \\ 0 & \text{keine Kante von $j$ nach $i$} +1 & \text{Kante von $j$ nach $i$} \\ 0 & \text{keine Kante von $j$ nach $i$} \end{matrix} \right. \label{verkehr:Adja} -- cgit v1.2.1 From adb7f34e662733e831d1caa86eacb9fdf13b3eed Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 08:45:43 +0200 Subject: =?UTF-8?q?Titel=20hinzugef=C3=BCgt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/main.tex | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/main.tex b/buch/papers/verkehr/main.tex index 6348993..98d0581 100644 --- a/buch/papers/verkehr/main.tex +++ b/buch/papers/verkehr/main.tex @@ -3,8 +3,7 @@ % % (c) 2020 Hochschule Rapperswil % -\chapter{Thema\label{chapter:verkehr}} -\lhead{Verkehrsfluss und Verkehrsnetze} +\chapter{Verkehrsfluss und Verkehrsnetze\label{chapter:verkehr}} \begin{refsection} \chapterauthor{Pascal Andreas Schmid und Robine Luchsinger} -- cgit v1.2.1 From 08ab4d022e3ec5aa8c598deedca5af8448bf7b1e Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 08:52:01 +0200 Subject: =?UTF-8?q?Strukturierung=20der=20Einf=C3=BChrung=20angepasst?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 2 -- 1 file changed, 2 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index d96d450..d793e4e 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -1,7 +1,5 @@ -\section{Einführung} \label{section:verkehr/einfuehrung} -\subsection{Verkehrsnetze} Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, auf denen eine räumliche Fortbewegung von Personen oder auch Gütern stattfindet. Verkehrsnetze sind ein Bestandteil der Verkehrsinfrastruktur, die auf topografischen Karten festgehalten werden. Sie umfassen den Schienenverkehr, alle Strassen und Wege, wie auch Flugplätze und alle dazugehörigen Bauwerke. Aus verkehrsgeografischer Sicht besteht das Verkehrsnetz aus Kanten, Knotenpunkten und dem Hinterland. Die Knotenpunkte werden auch hier durch die Kanten verbunden, die den Verkehrsstrom aufnehmen, wobei das Hinterland durch einzelne Knoten versorgt wird. Die Aufteilung in Kanten und Knotenpunkte ermöglicht eine Vereinfachung komplexer Verkehrsnetze, damit sie mittels der Graphentheorie untersucht werden können. Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes. -- cgit v1.2.1 From 6f673d1626cf26d479f22499eaa578a300637a8d Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 08:54:49 +0200 Subject: =?UTF-8?q?Sections=20eine=20Stufe=20einger=C3=BCckt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index d793e4e..ae13ac5 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -5,9 +5,9 @@ Aus verkehrsgeografischer Sicht besteht das Verkehrsnetz aus Kanten, Knotenpunkt Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes. Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. -\subsection{Suchalgorithmen} +\section{Suchalgorithmen} -\subsubsection{Dijkstra-Algorithmus} +\subsection{Dijkstra-Algorithmus} Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Infomratikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. Trotz der Schnelligkeit der Greedy-Algorithmen, können viele Probleme nicht optimal gelöst werden. @@ -39,7 +39,7 @@ Iteration Diese drei Schritte werden so lange wiederholt bis gilt \begin{equation}M=\{\}\end{equation} -\subsubsection{A*-Algorithmus} +\subsection{A*-Algorithmus} Suchalgorithmen werden nach einfachen (uninformierte) und heuristischen (informierten) Algorithmen unterschieden. Während einfache Algorithmen den Suchraum intuitiv durchsuchen, beziehen heuristische Algorithmen Wissen über den Suchraum mit ein. Der A*-Algorithmus geht auf seine Erfinder Peter Hart, Nils Nilsson und Bertram Raphael zurück, die den Algorithmus erstmals im Jahr 1968 beschrieben. Der A*-Algorithmus ist ein heuristischer Suchalgorithmus, der den kürzesten Pfad zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten berechnet. @@ -47,7 +47,7 @@ Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätz Ausserdem findet der A*-Algorithmus immer eine optimale Lösung, sofern eine vorhanden ist. Der A*-Algorithmus wird als Verallgemeinerung gehandhabt und gilt als Erweiterung des Dijkstra-Algorithmus. -\subsubsection{Anwendung A*-Algorithmus} +\subsection{Anwendung A*-Algorithmus} Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch die optimalste Lösung darstellt.\\ Die Kantengewichte werden für jeden Knoten in Form einer Funktion dargestellt @@ -58,13 +58,13 @@ Somit gilt: \begin{equation}f(n)=g(n)+h(n)\end{equation}\\ Wie auch der Algorithmus von Dijkstra findet der A*-Algorithmus die optimalste Lösung. -\subsubsection{Floyd-Warshall-Algorithmus} +\subsection{Floyd-Warshall-Algorithmus} Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die kürzesten , beziehungsweise die optimalsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. Ein Kreis (Zyklus) in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird.\\ Der Floyd-Warshall-Algorithmus besteht grundsätzlich aus Floyd's Berechnung der kürzesten Distanzen zwischen zwei Knoten und Warshall's Konstruktion der kürzesten Wege. Werden diese beiden Teilgebiete zusammengefügt, ergibt sich der Floyd-Warshall-Algorithmus. -\subsubsection{Anwendung Floyd-Warshall-Algorithmus} +\subsection{Anwendung Floyd-Warshall-Algorithmus} Wie oben erwähnt, besteht der Floyd-Warshall-Algorithmus aus dem Teil von Floyd zur Berechnung der kürzesten Pfade und dem Teil von Warshall zur Konstruktion der kürzesten Pfade. @@ -78,11 +78,11 @@ Die aktuelle Gewichtung der Pfade wird mit \begin{equation}d[i, j]=min[d[i,j], d[i,k] + d[k,i]]\end{equation} ermittelt. -\subsubsection{Euklidische Heuristik} +\subsection{Euklidische Heuristik} Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten von Verkehrsnetzen zur Berechnung der Distanz verwendet werden können, ist bei virtuellen Netzwerken (z.B. Servernetzen) entweder nicht möglich, oder nicht relevant. -\subsection{PageRank-Algorithmus} +\section{PageRank-Algorithmus} Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc.. Beim PageRank-Algorithmus handelt es sich um den Algorithmus von Google, aus dem die Google-Matrix abgeleitet wird. Die Google-Matrix ist eine immens grosse Matrix mit Millionen Zeilen und Spalten, die für die schnelle und vor allem exakte Bestimmung der PageRanks (Gewichtung) eine grosse Bedeutung hat. -- cgit v1.2.1 From cf0c08db837b718b2e6844f39886c065e923d2fb Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 09:04:15 +0200 Subject: Typo --- buch/papers/verkehr/section1.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index ae13ac5..40c8edf 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -8,7 +8,7 @@ Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. \section{Suchalgorithmen} \subsection{Dijkstra-Algorithmus} -Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Infomratikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. +Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. Trotz der Schnelligkeit der Greedy-Algorithmen, können viele Probleme nicht optimal gelöst werden. Vereinfacht wird beim Dijkstra-Algorithmus, ausgehend von einem Startknoten so lange dem kürzesten Pfad gefolgt, bis der Zielknoten erreicht wird. Dabei muss für jeden besuchten Knoten die Kostenfunktion als auch der Pfad dahin (vorheriger Knoten) gespeichert werden. -- cgit v1.2.1 From f102e60cf34adc068ccdc717b9c27d4179d208f8 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 09:15:21 +0200 Subject: =?UTF-8?q?Erl=C3=A4uterung=20zu=20A*?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 40c8edf..05c53c5 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -45,7 +45,7 @@ Der A*-Algorithmus geht auf seine Erfinder Peter Hart, Nils Nilsson und Bertram Der A*-Algorithmus ist ein heuristischer Suchalgorithmus, der den kürzesten Pfad zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten berechnet. Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätzfunktion, die sogenannte Heuristik, verwendet. Dies ermöglicht ein zielgerichtetes Suchen und gleichzeitig wird die Laufzeit verringert. Ausserdem findet der A*-Algorithmus immer eine optimale Lösung, sofern eine vorhanden ist. -Der A*-Algorithmus wird als Verallgemeinerung gehandhabt und gilt als Erweiterung des Dijkstra-Algorithmus. +Der A*-Algorithmus gilt als Erweiterung des Dijkstra-Algorithmus. \subsection{Anwendung A*-Algorithmus} Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch die optimalste Lösung darstellt.\\ -- cgit v1.2.1 From 2bd577326030c895a37d9bacaec84d7d62e6fe8b Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 09:16:20 +0200 Subject: Grammatik --- buch/papers/verkehr/section1.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 05c53c5..d18089d 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -48,7 +48,7 @@ Ausserdem findet der A*-Algorithmus immer eine optimale Lösung, sofern eine vor Der A*-Algorithmus gilt als Erweiterung des Dijkstra-Algorithmus. \subsection{Anwendung A*-Algorithmus} -Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch die optimalste Lösung darstellt.\\ +Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch eine optimale Lösung darstellt.\\ Die Kantengewichte werden für jeden Knoten in Form einer Funktion dargestellt \begin{equation}f(n)=g(n)\end{equation} mit -- cgit v1.2.1 From 3aafc071d7126b38c672047b95c1d584d52a3849 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 09:17:32 +0200 Subject: =?UTF-8?q?Erl=C3=A4uterung=20Floyd-Warshall?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index d18089d..f66896e 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -60,7 +60,7 @@ Wie auch der Algorithmus von Dijkstra findet der A*-Algorithmus die optimalste L \subsection{Floyd-Warshall-Algorithmus} Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. -Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die kürzesten , beziehungsweise die optimalsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. +Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die günstigsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. Ein Kreis (Zyklus) in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird.\\ Der Floyd-Warshall-Algorithmus besteht grundsätzlich aus Floyd's Berechnung der kürzesten Distanzen zwischen zwei Knoten und Warshall's Konstruktion der kürzesten Wege. Werden diese beiden Teilgebiete zusammengefügt, ergibt sich der Floyd-Warshall-Algorithmus. -- cgit v1.2.1 From fc8e18376f9db8e43a81006a3c7bd00e167d08b5 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 09:34:00 +0200 Subject: =?UTF-8?q?Widerspruch=20aufgel=C3=B6st?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index f66896e..389c78c 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -10,14 +10,13 @@ Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. \subsection{Dijkstra-Algorithmus} Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. -Trotz der Schnelligkeit der Greedy-Algorithmen, können viele Probleme nicht optimal gelöst werden. Vereinfacht wird beim Dijkstra-Algorithmus, ausgehend von einem Startknoten so lange dem kürzesten Pfad gefolgt, bis der Zielknoten erreicht wird. Dabei muss für jeden besuchten Knoten die Kostenfunktion als auch der Pfad dahin (vorheriger Knoten) gespeichert werden. Dadurch wird hingegen garantiert, dass, wenn der Zielknoten erreicht wird, auch der kürzeste Pfad gefunden wurde. Grundlegende Voraussetzung für den Dijkstra-Algorithmus ist die strikte Positivität der Kantengewichte. Andernfalls würde ein wiederholtes Ablaufen einer Kante mit negativem Gewicht zu einer stetigen Reduktion der Kostenfunktion führen, was zu einer unendlichen Schlaufe führen würde. Gegeben sei ein Netzwerk mit $n$ Knoten und dem Startknoten $a$. Alle Kanten sind mit $k(i, j)$ bewertet. -Gesucht wird der kürzeste Pfad zwischen dem Startknoten und allen übrigen Knoten im Netz. +Gesucht wird der kürzeste Pfad zwischen dem Startknoten und dem Knoten im Netz. $D(i)$ ist die kürzeste Distanz vom Startknoten $a$ zum Knoten $i, V(i)$ ist der unmittelbare Vorgängerknoten vom Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Konten $i$ und die Menge $M$ ist die Menge einer bestimmten Auswahl an Knoten. Dabei gilt -- cgit v1.2.1 From 46eee95c5d39e99535f3790e40994d0eb1167ffe Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 13:56:38 +0200 Subject: =?UTF-8?q?Erl=C3=A4uterung=20zu=20Suchalgorithmen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 389c78c..756f6e1 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -6,6 +6,13 @@ Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufba Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. \section{Suchalgorithmen} +Inbesondere bei Graphen in Form von Verkehrsnetzen ist das Finden eines kürzesten Weges von Interesse. Mathematisch betrachtet handelt es sich hierbei um ein Optimierungsproblem, bei dem die Summe der Kantengewichte zwischen zwei Knoten minimiert werden soll. Zu diesem Zweck existieren verschiedene Suchalgorithmen. In den folgenden Abschnitten wird auf eines Auswahl davon eingegangen. Zuvor ist es jedoch notwendig, einige Begriffe und Eigenschaften von Suchalgorithmen zu definieren. + +Einerseits wird zwischen optimalen und nicht-optimalen Algorithmen unterschieden. Ein Suchalgorithmus gilt als optimal, falls er einen günstigsten Pfad zwischen zwei Knoten findet. Es gilt zu beachten, dass im Falle des Vorhandenseins von mehrerern Pfaden mit identischer, minimaler Summe der Kantengewichte zwischen zwei Knoten, mindestens einer dieser Pfade gefunden wird. + +Weiter wird zwischen informierten und uninformierten Algorithmen differenziert. Während uninformierte Suchalgorithmen den Suchraum schematisch auf Basis der Eigenschaften des Graphen absuchen, bis eine günstigste Lösung gefunden wurde, verwenden informierte Suchalgorithmen eine Heuristik zur Abschätzung der Suchrichtung. Oftmals wird bei informierten Algorithmen ein Verlust der Optimalität zugunsten einer verbesserten Rechenzeit in Kauf genommen. Es exisitieren jedoch auch Heurstiken, die eine optimale Lösung gewährleisten. + +Eine besondere Art von Suchalgorithmen stellen die sogenannten Greedy-Algorithmen, zu deutsch gierige Algorithmen, dar. Sie zeichnen sich dadurch aus, dass stets der günstigste Weg verfolgt wird und davon ausgehend der darauffolgende, günstigste Folgezustand ausgewählt wird. Am Beispiel eines Verkehrsnetzes ist somit gewährleistet, dass beim Antreffen des Zielknotens auch der günstigste Pfad gefunden wurde. \subsection{Dijkstra-Algorithmus} Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. -- cgit v1.2.1 From dc45d7a57dfcc3ca4b9a97be4a51216c1a6ce4bc Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 15:00:00 +0200 Subject: =?UTF-8?q?Erl=C3=A4uterungen=20zu=20Dijkstra?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 34 ++++++---------------------------- 1 file changed, 6 insertions(+), 28 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 756f6e1..4a27737 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -15,35 +15,13 @@ Weiter wird zwischen informierten und uninformierten Algorithmen differenziert. Eine besondere Art von Suchalgorithmen stellen die sogenannten Greedy-Algorithmen, zu deutsch gierige Algorithmen, dar. Sie zeichnen sich dadurch aus, dass stets der günstigste Weg verfolgt wird und davon ausgehend der darauffolgende, günstigste Folgezustand ausgewählt wird. Am Beispiel eines Verkehrsnetzes ist somit gewährleistet, dass beim Antreffen des Zielknotens auch der günstigste Pfad gefunden wurde. \subsection{Dijkstra-Algorithmus} -Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. -Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. -Vereinfacht wird beim Dijkstra-Algorithmus, ausgehend von einem Startknoten so lange dem kürzesten Pfad gefolgt, bis der Zielknoten erreicht wird. Dabei muss für jeden besuchten Knoten die Kostenfunktion als auch der Pfad dahin (vorheriger Knoten) gespeichert werden. -Dadurch wird hingegen garantiert, dass, wenn der Zielknoten erreicht wird, auch der kürzeste Pfad gefunden wurde. -Grundlegende Voraussetzung für den Dijkstra-Algorithmus ist die strikte Positivität der Kantengewichte. Andernfalls würde ein wiederholtes Ablaufen einer Kante mit negativem Gewicht zu einer stetigen Reduktion der Kostenfunktion führen, was zu einer unendlichen Schlaufe führen würde. - -Gegeben sei ein Netzwerk mit $n$ Knoten und dem Startknoten $a$. -Alle Kanten sind mit $k(i, j)$ bewertet. -Gesucht wird der kürzeste Pfad zwischen dem Startknoten und dem Knoten im Netz. -$D(i)$ ist die kürzeste Distanz vom Startknoten $a$ zum Knoten $i, V(i)$ ist der unmittelbare Vorgängerknoten vom Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Konten $i$ und die Menge $M$ ist die Menge einer bestimmten Auswahl an Knoten. - -Dabei gilt -\begin{equation}M={a}\end{equation} -\begin{equation}D(a)=0\end{equation} wobei -\begin{equation}D(i)=\infty\end{equation} und -\begin{equation}i \neq a \end{equation} -Ausserdem gilt \begin{equation}V(i)=(-) \text{für alle Knoten $i$}\end{equation}\\ +Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Er gehört zur Klasse der uninformierten Greedy-Algorithmen. Zudem ist die Optimalität bei strikter Positivität des Graphen gewährleistet. +Vorteilhaft ist die einfache Implementierung. Abhängig von der Programmiersprache sind zwischen 30 und 40 Zeilen an Code ausreichend, damit er den kürzesten Pfad zwischen einem Startknoten $a$ und Zielknoten $b$ finden kann. Die für dieses Paper verwendete Funktion verwendet eine abgewandelte Form der gewichteten Adjazenz-Matrix $A$, für welche gilt: +Der Matrix-Eintrag $A_{i,j}$ weist das Kantengewicht der Kante von Knoten $j$ nach $i$ auf. Falls keine Kante zwischen $j$ und $i$ vorhanden ist, beträgt der Eintrag $\infty$. Dies vereinfacht die Implementierung zur Bestimmung des nächst-günstigsten Pfades. +Zudem werden zwei Hilfs-Vektoren $\vec{d}$ und $\vec{b}$ der Länge $n$ eingeführt, wobei $n$ die Anzahl Knoten des Graphen ist. Im Vektoreintrag $\vec{d}(i)$ wird das kummulierte Kantengewicht zur Erreichung von Knoten $i$ vom Startknoten $a$ gespeichert. Der Eintrag $\vec{d}(a)$ beträgt somit $0$. Im Vektor $\vec{b}$ wird zudem vermerkt, falls ein Knoten bereits als Ziel eines kürzesten Pfads gefunden wurde und somit für die weitere Suche nicht mehr berücksichtigt werden muss ($\vec{b}(i)=1$, sonst $\vec{b}(i)=0$). -%THEORIE... -Iteration - -1. Auswahl eines Knotens \begin{equation} K\in M \text{mit} D(K)=D(i);i\in M\end{equation} - -2. Für alle Nachfolger $N(j)$ vom Knoten $K$ gilt: -\begin{equation}D(K) + k_Kj < D(j)\end{equation} dann wird \begin{equation}D(j) = D(K) + k_Kj, V(j) = K\end{equation} gesetzt und somit wird der Knoten $j$ in die Menge $M$ aufgenommen. - -3. Der ausgewählte Knoten \begin{equation}K\in M\text{wird aus der Menge herausgelöscht}\end{equation}\\ -Diese drei Schritte werden so lange wiederholt bis gilt -\begin{equation}M=\{\}\end{equation} +Ausgehend vom Startknoten $a$ wird nun anhand der Matrix $A$ in der Spalte $a$ nach dem kleinsten Eintrag gesucht. Somit wird der Folgeknoten $c$ gefunden. Dieser Vorgang wird nun wiederholt, wobei jedoch sämtliche von Knoten $a$ und $c$ erreichbaren Knoten berücksichtigt werden, die noch nicht besucht wurden. In anderen Worten alle nicht verschwindenden Einträge $i$ der Spalten $a$ und $c$ der Matrix $A$, für welche gilt $\vec{b}(i)=0$. +Diese Iteration wird solang durchgeführt, bis der Folgeknoten dem Zielknoten entspricht. \subsection{A*-Algorithmus} Suchalgorithmen werden nach einfachen (uninformierte) und heuristischen (informierten) Algorithmen unterschieden. Während einfache Algorithmen den Suchraum intuitiv durchsuchen, beziehen heuristische Algorithmen Wissen über den Suchraum mit ein. -- cgit v1.2.1 From 4f04bd2ec5008a375c6d77ec6d01c3bc68a0b976 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 15:20:52 +0200 Subject: =?UTF-8?q?Erl=C3=A4uterungen=20zu=20A*?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 20 ++++++-------------- 1 file changed, 6 insertions(+), 14 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 4a27737..6f8f2b7 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -20,27 +20,19 @@ Vorteilhaft ist die einfache Implementierung. Abhängig von der Programmiersprac Der Matrix-Eintrag $A_{i,j}$ weist das Kantengewicht der Kante von Knoten $j$ nach $i$ auf. Falls keine Kante zwischen $j$ und $i$ vorhanden ist, beträgt der Eintrag $\infty$. Dies vereinfacht die Implementierung zur Bestimmung des nächst-günstigsten Pfades. Zudem werden zwei Hilfs-Vektoren $\vec{d}$ und $\vec{b}$ der Länge $n$ eingeführt, wobei $n$ die Anzahl Knoten des Graphen ist. Im Vektoreintrag $\vec{d}(i)$ wird das kummulierte Kantengewicht zur Erreichung von Knoten $i$ vom Startknoten $a$ gespeichert. Der Eintrag $\vec{d}(a)$ beträgt somit $0$. Im Vektor $\vec{b}$ wird zudem vermerkt, falls ein Knoten bereits als Ziel eines kürzesten Pfads gefunden wurde und somit für die weitere Suche nicht mehr berücksichtigt werden muss ($\vec{b}(i)=1$, sonst $\vec{b}(i)=0$). -Ausgehend vom Startknoten $a$ wird nun anhand der Matrix $A$ in der Spalte $a$ nach dem kleinsten Eintrag gesucht. Somit wird der Folgeknoten $c$ gefunden. Dieser Vorgang wird nun wiederholt, wobei jedoch sämtliche von Knoten $a$ und $c$ erreichbaren Knoten berücksichtigt werden, die noch nicht besucht wurden. In anderen Worten alle nicht verschwindenden Einträge $i$ der Spalten $a$ und $c$ der Matrix $A$, für welche gilt $\vec{b}(i)=0$. +Ausgehend vom Startknoten $a$ wird nun anhand der Matrix $A$ in der Spalte $a$ nach dem kleinsten Eintrag gesucht. Somit wird der Folgeknoten $c$ gefunden. Dieser Vorgang wird nun wiederholt, wobei jedoch sämtliche von Knoten $a$ und $c$ erreichbaren Knoten berücksichtigt werden, die noch nicht besucht wurden. In anderen Worten alle nicht verschwindenden Einträge $i$ der Spalten $a$ und $c$ der Matrix $A$, für welche gilt $\vec{b}(i)=0$. Ausschlaggebend für die folgende Auswahl ist die Summe der kummulierten Kantengewichte und des Kantengewichts des nächsten Knotens. Als Beispiel zur Erreichung von Knoten $k$ über Knoten $j$: +\begin{equation} +\vec{d}(k)=\vec{d}(j)+A(k,j) +\end{equation} Diese Iteration wird solang durchgeführt, bis der Folgeknoten dem Zielknoten entspricht. \subsection{A*-Algorithmus} -Suchalgorithmen werden nach einfachen (uninformierte) und heuristischen (informierten) Algorithmen unterschieden. Während einfache Algorithmen den Suchraum intuitiv durchsuchen, beziehen heuristische Algorithmen Wissen über den Suchraum mit ein. -Der A*-Algorithmus geht auf seine Erfinder Peter Hart, Nils Nilsson und Bertram Raphael zurück, die den Algorithmus erstmals im Jahr 1968 beschrieben. -Der A*-Algorithmus ist ein heuristischer Suchalgorithmus, der den kürzesten Pfad zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten berechnet. -Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätzfunktion, die sogenannte Heuristik, verwendet. Dies ermöglicht ein zielgerichtetes Suchen und gleichzeitig wird die Laufzeit verringert. -Ausserdem findet der A*-Algorithmus immer eine optimale Lösung, sofern eine vorhanden ist. -Der A*-Algorithmus gilt als Erweiterung des Dijkstra-Algorithmus. +Der A*-Algorithmus basiert auf dem Dijkstra-Algorithmus, verwendet jedoch eine Heuristik zur Abschätzung der günstigsten Suchrichtung. Somit handelt es sich um einen informierten Greedy-Algorithmus, der abhängig von der verwendeten Heuristik auch optimal sein kann. Er wurde von Peter Hart, Nils Nilsson und Bertram Raphael entwickelt. \subsection{Anwendung A*-Algorithmus} Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch eine optimale Lösung darstellt.\\ -Die Kantengewichte werden für jeden Knoten in Form einer Funktion dargestellt -\begin{equation}f(n)=g(n)\end{equation} mit -\begin{equation}g(n)=\text{Summe aller Kantengewichte vom Startknoten bis n}\end{equation}\\ -Der A*-Algorithmus erweitert die Vorgehensweise des Algorithmus von Dijkstra um die Heuristik $h(n)$, die für jeden Knoten $n$ die geschätzte Entfernung zum Zielknoten beschreibt. -Somit gilt: -\begin{equation}f(n)=g(n)+h(n)\end{equation}\\ -Wie auch der Algorithmus von Dijkstra findet der A*-Algorithmus die optimalste Lösung. +Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht. \subsection{Floyd-Warshall-Algorithmus} Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. -- cgit v1.2.1 From 0d84587614eb3a91f0a63e0d2ab2eb3926b2f95c Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 15:21:30 +0200 Subject: subsection "Euklidische Heurstik" verschoben --- buch/papers/verkehr/section1.tex | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6f8f2b7..1a4ecbb 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -34,6 +34,10 @@ Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus v Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht. +\subsection{Euklidische Heuristik} +Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. +Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten von Verkehrsnetzen zur Berechnung der Distanz verwendet werden können, ist bei virtuellen Netzwerken (z.B. Servernetzen) entweder nicht möglich, oder nicht relevant. + \subsection{Floyd-Warshall-Algorithmus} Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die günstigsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. @@ -54,9 +58,7 @@ Die aktuelle Gewichtung der Pfade wird mit \begin{equation}d[i, j]=min[d[i,j], d[i,k] + d[k,i]]\end{equation} ermittelt. -\subsection{Euklidische Heuristik} -Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. -Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten von Verkehrsnetzen zur Berechnung der Distanz verwendet werden können, ist bei virtuellen Netzwerken (z.B. Servernetzen) entweder nicht möglich, oder nicht relevant. + \section{PageRank-Algorithmus} Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc.. -- cgit v1.2.1 From 6437ce5c4a0b281fbd116bc42dbcdc3dce908aaf Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 15:35:28 +0200 Subject: Anpassungen Folyd-Warshall-Algorithmus --- buch/papers/verkehr/section1.tex | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 1a4ecbb..d34d31e 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -35,24 +35,22 @@ Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus v Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht. \subsection{Euklidische Heuristik} -Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. -Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten von Verkehrsnetzen zur Berechnung der Distanz verwendet werden können, ist bei virtuellen Netzwerken (z.B. Servernetzen) entweder nicht möglich, oder nicht relevant. +Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. Unter Verwendung dieser Heuristik gilt der A*-Algorithmus als optimal. + +Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten von Verkehrsnetzen zur Berechnung der Distanz verwendet werden können, ist bei virtuellen Netzwerken (z.B. Servernetzen) entweder nicht möglich, oder nicht relevant. Hier können hingegen andere Eigenschaften des Netzwerks verwendet werden, auf welche in diesem Paper nicht weiter eingegangen wird. \subsection{Floyd-Warshall-Algorithmus} Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die günstigsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. Ein Kreis (Zyklus) in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird.\\ -Der Floyd-Warshall-Algorithmus besteht grundsätzlich aus Floyd's Berechnung der kürzesten Distanzen zwischen zwei Knoten und Warshall's Konstruktion der kürzesten Wege. Werden diese beiden Teilgebiete zusammengefügt, ergibt sich der Floyd-Warshall-Algorithmus. \subsection{Anwendung Floyd-Warshall-Algorithmus} -Wie oben erwähnt, besteht der Floyd-Warshall-Algorithmus aus dem Teil von Floyd zur Berechnung der kürzesten Pfade und dem Teil von Warshall zur Konstruktion der kürzesten Pfade. - %THEORIE... -Als erstes wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W[i, j]$ erstellt. +In einem ersten Schritt wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W[i, j]$ erstellt. Der Algorithmus berechnet danach in einer Hauptschleife alle Knoten $k$ von 1 bis $n$. Dabei versucht er in jeder Iteration alle Wege von $i$ nach $j$ durch die Wege $(i, k)$ und $(k, j)$ zu verbessern. -Falls dieser mögliche Umweg zu einer Verbesserung führt, wird der Algorithmus aktualisiert. +Falls dieser mögliche Umweg zu einer Verbesserung führt, wird der entsprechende Eintrag aktualisiert. Die aktuelle Gewichtung der Pfade wird mit \begin{equation}d[i, j]=min[d[i,j], d[i,k] + d[k,i]]\end{equation} -- cgit v1.2.1 From 04e2c97e5885542ee0beda05da749964a44cf1e1 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 15:39:06 +0200 Subject: Anpassungen PageRank-Algorithmus --- buch/papers/verkehr/section1.tex | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index d34d31e..5abd107 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -59,11 +59,9 @@ ermittelt. \section{PageRank-Algorithmus} -Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc.. -Beim PageRank-Algorithmus handelt es sich um den Algorithmus von Google, aus dem die Google-Matrix abgeleitet wird. -Die Google-Matrix ist eine immens grosse Matrix mit Millionen Zeilen und Spalten, die für die schnelle und vor allem exakte Bestimmung der PageRanks (Gewichtung) eine grosse Bedeutung hat. -Der PageRank-Algorithmus analysiert und gewichtet beispielsweise die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur. -Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.\\ +Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc. +Beim PageRank-Algorithmus handelt es sich nicht um einen Suchalgorithmus, stattdessen werden Knoten aufgrund der Vernetzung des vorliegenden Graphen bewertet. +Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur zu bewerten und relevante Suchergebnisse zu ermittteln. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.\\ Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche gilt. %THEORIE... -- cgit v1.2.1 From 226acbde873393484d3abf3db1160672826d5241 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 15:45:31 +0200 Subject: Anpassungen Abschnitt Versuchsreihe --- buch/papers/verkehr/section2.tex | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex index 638d9dd..4de0b24 100644 --- a/buch/papers/verkehr/section2.tex +++ b/buch/papers/verkehr/section2.tex @@ -1,12 +1,12 @@ \section{Versuchsreihe} \label{section:verkehr/versuchsreihe} -Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der \emph{Dijkstra}-, sowie der \emph{$A^*$}-Algorithmus auf das Netzwerk angewandt. -Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal repetiert. -Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Anzahl Kanten (engl. \emph{edges}) und $V$ die Anzahl Knoten (engl. \emph{vertices}) darstellt. -Für den \emph{A*}-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zu $\mathcal{O}$ machen. +Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der Dijkstra- und der A*-Algorithmus auf das Netzwerk angewandt. +Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal wiederholt. +Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Menge der Kanten (engl. \emph{edges}) und $V$ die Menge der Knoten (engl. \emph{vertices}) des Graphen $G$ darstellt. +Für den A*-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zur Zeitkomplexität machen. -Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. +Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. \subsection{Einfluss der Knotenzahl auf die Rechenzeit} \label{verkehr:Knotenzahl} @@ -19,9 +19,9 @@ Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- \label{verkehr:Vr1} \end{figure} -In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. +In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen Dijkstra und A* erst ab einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. -Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. +Abbildung \ref{verkehr:pathDifference} illustriert dies, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. \begin{figure} \centering @@ -36,13 +36,13 @@ Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei di \begin{figure} \centering -\includegraphics[width=12cm]{papers/verkehr/figures/chart_Vr2.png}\\ +\includegraphics[width=12cm]{papers/verkehr/figures/chart_Vr2.png} \caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr2} \end{figure} -Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ -Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. +Zum Vergleich der Resultate in Abschnitt \ref{verkehr:Knotenzahl} zeigt Abbildung \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen. +Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen Dijkstra und A* deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des A*-Algorithmus erklären. \begin{figure} \centering @@ -52,4 +52,4 @@ Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwis \label{verkehr:Comparison} \end{figure} -In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. +In Abbildung \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. -- cgit v1.2.1 From 45e525ce336712b0b75d2431b130d09835857382 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 15:48:46 +0200 Subject: Anpassungen Abschnitt Ausblick --- buch/papers/verkehr/section3.tex | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'buch/papers/verkehr') 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. -- cgit v1.2.1 From a23ef813e263ac2d0f06d734c711517806fa1437 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 20:48:34 +0200 Subject: diverse Anpassungen --- buch/papers/verkehr/section1.tex | 40 ++++++++++++++++++++++++---------------- 1 file changed, 24 insertions(+), 16 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 5abd107..6d05dc0 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -6,25 +6,27 @@ Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufba Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. \section{Suchalgorithmen} -Inbesondere bei Graphen in Form von Verkehrsnetzen ist das Finden eines kürzesten Weges von Interesse. Mathematisch betrachtet handelt es sich hierbei um ein Optimierungsproblem, bei dem die Summe der Kantengewichte zwischen zwei Knoten minimiert werden soll. Zu diesem Zweck existieren verschiedene Suchalgorithmen. In den folgenden Abschnitten wird auf eines Auswahl davon eingegangen. Zuvor ist es jedoch notwendig, einige Begriffe und Eigenschaften von Suchalgorithmen zu definieren. +Inbesondere bei Graphen in Form von Verkehrsnetzen ist das Finden eines kürzesten Weges von Interesse. Mathematisch betrachtet handelt es sich hierbei um ein Optimierungsproblem, bei dem die Summe der Kantengewichte zwischen zwei Knoten minimiert werden soll. Zu diesem Zweck existieren verschiedene Suchalgorithmen. In den folgenden Abschnitten wird auf eine Auswahl davon eingegangen. Zuvor ist es jedoch notwendig, einige Begriffe und Eigenschaften von Suchalgorithmen zu definieren. Einerseits wird zwischen optimalen und nicht-optimalen Algorithmen unterschieden. Ein Suchalgorithmus gilt als optimal, falls er einen günstigsten Pfad zwischen zwei Knoten findet. Es gilt zu beachten, dass im Falle des Vorhandenseins von mehrerern Pfaden mit identischer, minimaler Summe der Kantengewichte zwischen zwei Knoten, mindestens einer dieser Pfade gefunden wird. Weiter wird zwischen informierten und uninformierten Algorithmen differenziert. Während uninformierte Suchalgorithmen den Suchraum schematisch auf Basis der Eigenschaften des Graphen absuchen, bis eine günstigste Lösung gefunden wurde, verwenden informierte Suchalgorithmen eine Heuristik zur Abschätzung der Suchrichtung. Oftmals wird bei informierten Algorithmen ein Verlust der Optimalität zugunsten einer verbesserten Rechenzeit in Kauf genommen. Es exisitieren jedoch auch Heurstiken, die eine optimale Lösung gewährleisten. -Eine besondere Art von Suchalgorithmen stellen die sogenannten Greedy-Algorithmen, zu deutsch gierige Algorithmen, dar. Sie zeichnen sich dadurch aus, dass stets der günstigste Weg verfolgt wird und davon ausgehend der darauffolgende, günstigste Folgezustand ausgewählt wird. Am Beispiel eines Verkehrsnetzes ist somit gewährleistet, dass beim Antreffen des Zielknotens auch der günstigste Pfad gefunden wurde. +Eine besondere Art von Suchalgorithmen stellen die sogenannten Greedy-Algorithmen, zu deutsch gierige Algorithmen, dar. Sie zeichnen sich dadurch aus, dass sie stets den zurzeit günstigsten Folgezustand auswählen. Dadurch sind sie in der Regel äusserst effizient, garantieren bei vielen Problemstellungen jedoch keine optimale Lösung. \subsection{Dijkstra-Algorithmus} -Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Er gehört zur Klasse der uninformierten Greedy-Algorithmen. Zudem ist die Optimalität bei strikter Positivität des Graphen gewährleistet. -Vorteilhaft ist die einfache Implementierung. Abhängig von der Programmiersprache sind zwischen 30 und 40 Zeilen an Code ausreichend, damit er den kürzesten Pfad zwischen einem Startknoten $a$ und Zielknoten $b$ finden kann. Die für dieses Paper verwendete Funktion verwendet eine abgewandelte Form der gewichteten Adjazenz-Matrix $A$, für welche gilt: -Der Matrix-Eintrag $A_{i,j}$ weist das Kantengewicht der Kante von Knoten $j$ nach $i$ auf. Falls keine Kante zwischen $j$ und $i$ vorhanden ist, beträgt der Eintrag $\infty$. Dies vereinfacht die Implementierung zur Bestimmung des nächst-günstigsten Pfades. +Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Er gehört zur Klasse der uninformierten Greedy-Algorithmen. Zudem ist die Optimalität bei strikt positiven Kantengewichten gewährleistet. +Vorteilhaft ist die einfache Implementierung. Abhängig von der Programmiersprache sind zwischen 30 und 40 Zeilen an Code ausreichend, damit er den kürzesten Pfad zwischen einem Startknoten $a$ und Zielknoten $b$ finden kann. + +Die für dieses Paper verwendete programmierte Funktion (MATLAB) verwendet eine abgewandelte Form der gewichteten Adjazenz-Matrix $A$, für welche gilt: +Der Matrix-Eintrag $A_{i,j}$ enthält das Kantengewicht der Kante von Knoten $j$ nach $i$ auf. Falls keine Kante zwischen $j$ und $i$ vorhanden ist, beträgt der Eintrag $\infty$. Dies vereinfacht die Implementierung zur Bestimmung des nächst-günstigsten Pfades. Zudem werden zwei Hilfs-Vektoren $\vec{d}$ und $\vec{b}$ der Länge $n$ eingeführt, wobei $n$ die Anzahl Knoten des Graphen ist. Im Vektoreintrag $\vec{d}(i)$ wird das kummulierte Kantengewicht zur Erreichung von Knoten $i$ vom Startknoten $a$ gespeichert. Der Eintrag $\vec{d}(a)$ beträgt somit $0$. Im Vektor $\vec{b}$ wird zudem vermerkt, falls ein Knoten bereits als Ziel eines kürzesten Pfads gefunden wurde und somit für die weitere Suche nicht mehr berücksichtigt werden muss ($\vec{b}(i)=1$, sonst $\vec{b}(i)=0$). Ausgehend vom Startknoten $a$ wird nun anhand der Matrix $A$ in der Spalte $a$ nach dem kleinsten Eintrag gesucht. Somit wird der Folgeknoten $c$ gefunden. Dieser Vorgang wird nun wiederholt, wobei jedoch sämtliche von Knoten $a$ und $c$ erreichbaren Knoten berücksichtigt werden, die noch nicht besucht wurden. In anderen Worten alle nicht verschwindenden Einträge $i$ der Spalten $a$ und $c$ der Matrix $A$, für welche gilt $\vec{b}(i)=0$. Ausschlaggebend für die folgende Auswahl ist die Summe der kummulierten Kantengewichte und des Kantengewichts des nächsten Knotens. Als Beispiel zur Erreichung von Knoten $k$ über Knoten $j$: \begin{equation} \vec{d}(k)=\vec{d}(j)+A(k,j) \end{equation} -Diese Iteration wird solang durchgeführt, bis der Folgeknoten dem Zielknoten entspricht. +Diese Iteration wird solange durchgeführt, bis der Folgeknoten dem Zielknoten entspricht. \subsection{A*-Algorithmus} Der A*-Algorithmus basiert auf dem Dijkstra-Algorithmus, verwendet jedoch eine Heuristik zur Abschätzung der günstigsten Suchrichtung. Somit handelt es sich um einen informierten Greedy-Algorithmus, der abhängig von der verwendeten Heuristik auch optimal sein kann. Er wurde von Peter Hart, Nils Nilsson und Bertram Raphael entwickelt. @@ -32,17 +34,22 @@ Der A*-Algorithmus basiert auf dem Dijkstra-Algorithmus, verwendet jedoch eine H \subsection{Anwendung A*-Algorithmus} Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch eine optimale Lösung darstellt.\\ -Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht. +Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht. Ein Beispiel dafür, wie eine Abschätzfunktion gebildet werden kann findet sich in Abschnitt \ref{sec:verkehr/euklidische} \subsection{Euklidische Heuristik} +\label{sec:verkehr/euklidische} Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. Unter Verwendung dieser Heuristik gilt der A*-Algorithmus als optimal. +Bei der euklidischen Heuristik wird die Abschätzfunktion $f(k)$ für jeden Knoten $k$ durch euklidische Distanz zum Zielknoten $b$ gebildet. +\begin{equation} +f(k)=\sqrt{(x_k-x_b)^2+(y_k-y_b)^2} +\end{equation} + Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten von Verkehrsnetzen zur Berechnung der Distanz verwendet werden können, ist bei virtuellen Netzwerken (z.B. Servernetzen) entweder nicht möglich, oder nicht relevant. Hier können hingegen andere Eigenschaften des Netzwerks verwendet werden, auf welche in diesem Paper nicht weiter eingegangen wird. \subsection{Floyd-Warshall-Algorithmus} Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. -Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die günstigsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. -Ein Kreis (Zyklus) in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird.\\ +Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die günstigsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph keinen negativen Kreis (Zyklus) aufweist. Ein Kreis, sprich ein Weg mit identischem Start- und Zielknoten, ist negativ, falls die Summe der Kantengewichte des Weges kleiner als null ist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. \subsection{Anwendung Floyd-Warshall-Algorithmus} @@ -53,7 +60,7 @@ Dabei versucht er in jeder Iteration alle Wege von $i$ nach $j$ durch die Wege $ Falls dieser mögliche Umweg zu einer Verbesserung führt, wird der entsprechende Eintrag aktualisiert. Die aktuelle Gewichtung der Pfade wird mit -\begin{equation}d[i, j]=min[d[i,j], d[i,k] + d[k,i]]\end{equation} +\begin{equation}d[i, j]=\min[d[i,j], d[i,k] + d[k,i]]\end{equation} ermittelt. @@ -62,10 +69,7 @@ ermittelt. Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc. Beim PageRank-Algorithmus handelt es sich nicht um einen Suchalgorithmus, stattdessen werden Knoten aufgrund der Vernetzung des vorliegenden Graphen bewertet. Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur zu bewerten und relevante Suchergebnisse zu ermittteln. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.\\ -Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche gilt. - -%THEORIE... -Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseinander, wie eine Suchmaschine wie Google Suchresultate bewertet und somit sortieren soll. Öfters aufgerufene Resultate sollen schliesslich höher gewichtet werden. Dabei wird angenommen, dass eine Website populärer ist, je mehr andere Websites darauf verweisen. +Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche folgendes gilt: \begin{equation} A_{i,j}=\left\{ \begin{matrix} @@ -75,13 +79,17 @@ A_{i,j}=\left\{ \begin{matrix} \label{verkehr:Adja} \end{equation} +%THEORIE... +Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseinander, wie eine Suchmaschine wie Google Suchresultate bewertet und somit sortieren soll. Öfters aufgerufene Resultate sollen schliesslich höher gewichtet werden. Dabei wird angenommen, dass eine Website populärer ist, je mehr andere Websites darauf verweisen. + + -Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1...n\right\}\end{equation} +Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1\dot n\right\}\end{equation} Beim PageRank-Algorithmus wird eine abgewandelte Form der Adjazenz-Matrix verwendet. Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt. \begin{equation} P_{i,j}=\frac{A_{i,j}}{\sum_{i=1}^{n}A_{i,j}} \end{equation} Anschliessend multipliziert man diese Matrix $P$ mit einem Spaltenvektor $\Vec{r_0}$ mit $n$ Einträgen, für welchen gilt: -\begin{equation} \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1...n\right\} \end{equation} +\begin{equation} \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dot n\right\} \end{equation} Dieser Vektor stellt ein neutrales Ranking dar. Alle Knoten werden gleich gewichtet. Dadurch erhält man wiederum einen $n$-zeiligen Spaltenvektor $\Vec{r_1}$, der das "erste" Ranking darstellt. Durch Multiplikation der ursprünglichen Matrix $P$ mit dem 1. Ranking-Vektor $\Vec{r_1}$ wird auf Basis des ersten Rankings ein zweites erstellt. \begin{equation} \Vec{r_2} = P\cdot\Vec{r_1} = P\cdot(P\cdot\Vec{r_0}) = P^2\cdot\Vec{r_0}\end{equation} -- cgit v1.2.1 From c1d43d16b948505cc25d8eb740a393170a28a7f9 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 20:51:44 +0200 Subject: diverse Anpassungen --- buch/papers/verkehr/section1.tex | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6d05dc0..416e311 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -87,12 +87,12 @@ Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseina Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1\dot n\right\}\end{equation} Beim PageRank-Algorithmus wird eine abgewandelte Form der Adjazenz-Matrix verwendet. Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt. -\begin{equation} P_{i,j}=\frac{A_{i,j}}{\sum_{i=1}^{n}A_{i,j}} \end{equation} +\[ P_{i,j}=\frac{A_{i,j}}{\sum_{i=1}^{n}A_{i,j}} \] Anschliessend multipliziert man diese Matrix $P$ mit einem Spaltenvektor $\Vec{r_0}$ mit $n$ Einträgen, für welchen gilt: -\begin{equation} \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dot n\right\} \end{equation} +\[ \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dot n\right\} \] Dieser Vektor stellt ein neutrales Ranking dar. Alle Knoten werden gleich gewichtet. -Dadurch erhält man wiederum einen $n$-zeiligen Spaltenvektor $\Vec{r_1}$, der das "erste" Ranking darstellt. Durch Multiplikation der ursprünglichen Matrix $P$ mit dem 1. Ranking-Vektor $\Vec{r_1}$ wird auf Basis des ersten Rankings ein zweites erstellt. -\begin{equation} \Vec{r_2} = P\cdot\Vec{r_1} = P\cdot(P\cdot\Vec{r_0}) = P^2\cdot\Vec{r_0}\end{equation} +Dadurch erhält man wiederum einen $n$-zeiligen Spaltenvektor $\Vec{r_1}$, der das ``erste" Ranking darstellt. Durch Multiplikation der ursprünglichen Matrix $P$ mit dem 1. Ranking-Vektor $\Vec{r_1}$ wird auf Basis des ersten Rankings ein zweites erstellt. +\[ \Vec{r_2} = P\cdot\Vec{r_1} = P\cdot(P\cdot\Vec{r_0}) = P^2\cdot\Vec{r_0}\] somit \begin{equation} \Vec{r_i} = P^i\cdot\Vec{r_0}\end{equation} -Der Vektor $\Vec{r_i}$ konvergiert zu einem Eigenvektor von $P$ und stellt das abschliessende Ranking dar. +Der Vektor $\Vec{r_i}$ konvergiert zu einem Eigenvektor von $P$ der das abschliessende Ranking darstellt. -- cgit v1.2.1 From 16084eb844ae3595fc1799feab78b96d0c977306 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Tue, 27 Jul 2021 20:52:46 +0200 Subject: diverse Anpassungen --- buch/papers/verkehr/section2.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex index 4de0b24..527885e 100644 --- a/buch/papers/verkehr/section2.tex +++ b/buch/papers/verkehr/section2.tex @@ -3,8 +3,8 @@ Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der Dijkstra- und der A*-Algorithmus auf das Netzwerk angewandt. Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal wiederholt. -Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Menge der Kanten (engl. \emph{edges}) und $V$ die Menge der Knoten (engl. \emph{vertices}) des Graphen $G$ darstellt. -Für den A*-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zur Zeitkomplexität machen. +Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(|E|\log{}|V|)$ auf, wobei $E$ die Menge der Kanten (engl. \emph{edges}) und $V$ die Menge der Knoten (engl. \emph{vertices}) des Graphen $G$ darstellt. +Für den A*-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine definitive Angabe zur Zeitkomplexität machen. Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. -- cgit v1.2.1 From 5c9bc9221d54daecf885b8e66286a5f13406e47b Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Wed, 28 Jul 2021 20:27:50 +0200 Subject: Diverse Anpassungen MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit - Typos - Integration von Formeln in Sätze - \dot zu \dots --- buch/papers/verkehr/section1.tex | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'buch/papers/verkehr') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 416e311..6ac86ad 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -84,15 +84,15 @@ Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseina -Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1\dot n\right\}\end{equation} +Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1\dots n\right\}\end{equation} Beim PageRank-Algorithmus wird eine abgewandelte Form der Adjazenz-Matrix verwendet. -Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt. -\[ P_{i,j}=\frac{A_{i,j}}{\sum_{i=1}^{n}A_{i,j}} \] +Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt: +\( P_{i,j}=\frac{A_{i,j}}{\sum_{i=1}^{n}A_{i,j}} \) Anschliessend multipliziert man diese Matrix $P$ mit einem Spaltenvektor $\Vec{r_0}$ mit $n$ Einträgen, für welchen gilt: -\[ \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dot n\right\} \] +\( \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dots n\right\} \) Dieser Vektor stellt ein neutrales Ranking dar. Alle Knoten werden gleich gewichtet. -Dadurch erhält man wiederum einen $n$-zeiligen Spaltenvektor $\Vec{r_1}$, der das ``erste" Ranking darstellt. Durch Multiplikation der ursprünglichen Matrix $P$ mit dem 1. Ranking-Vektor $\Vec{r_1}$ wird auf Basis des ersten Rankings ein zweites erstellt. -\[ \Vec{r_2} = P\cdot\Vec{r_1} = P\cdot(P\cdot\Vec{r_0}) = P^2\cdot\Vec{r_0}\] -somit -\begin{equation} \Vec{r_i} = P^i\cdot\Vec{r_0}\end{equation} +Dadurch erhält man wiederum einen $n$-zeiligen Spaltenvektor $\Vec{r_1}$, der das ``erste'' Ranking darstellt. Durch Multiplikation der ursprünglichen Matrix $P$ mit dem 1. Ranking-Vektor $\Vec{r_1}$ wird auf Basis des ersten Rankings ein zweites erstellt: +\( \Vec{r_2} = P\cdot\Vec{r_1} = P\cdot(P\cdot\Vec{r_0}) = P^2\cdot\Vec{r_0}\) +und somit allgemein: +\( \Vec{r_i} = P^i\cdot\Vec{r_0}\) Der Vektor $\Vec{r_i}$ konvergiert zu einem Eigenvektor von $P$ der das abschliessende Ranking darstellt. -- cgit v1.2.1