Zusammenfassung

In dieser Lektion wurde die Netzwerkanalyse behandelt. Die Netzwerkanalyse befasst sich in erster Linie mit den Beziehungen zwischen Objekten. Um diese (Distanz-) Beziehungen zu untersuchen, braucht es genaue Kenntnisse der vorhandenen Grundelemente (vgl. Primitives of a Network), desweiteren Masse, mit Hilfe derer eine Beschreibung der Struktur von Netzwerken möglich ist (vgl. Structural Properties of a Network).

Die Berechnung von kürzesten Wegen ist ein häufiger Anwendungsfall der Netzwerkanalyse bzw. der Graphentheorie. In diesem Zusammenhang ist der Dijkstra Algorithmus vorgestellt worden, der am häufigsten verwendete Algorithmus zur Berechnung kürzester Wege in kantengewichteten Graphen. Der Pseudocode des Algorithmus wurde vorgestellt, sowie mittels einer Animation die Funktionsweise des Algorithmus Schritt für Schritt erläutert. Es wurde darüber hinaus betont, dass für spezielle Anwendungsgebiete und spezielle Arten von Graphen (Gewichtung von Knoten, negative Kantengewichtungen) es einer Modifikation bzw. alternativer Algorithmen bedarf um eine Distanzberechnung durchzuführen.

Desweiteren wurde das Travelling Salesman Problem (TSP) vorgestellt, welches die Frage behandelt, auf welche Weise eine Routenberechnung so optimiert werden kann, dass nach Besuch mehrerer Orte und Rückkehr zum Anfangsort eine möglichst geringe Distanz zurückgelegt wurde. In diesem Zusammenhang wurde das Vehicle Routing Problem vorgestellt, welches das TSP dahingehend erweitert, dass hier etwa auch Minimierung der Transportkosten oder die Minimierung der Anzahl der benutzten Fahrzeuge berücksichtigt wird. Als Lösungsansätze in diesem Bereich bieten sich exakte und heuristische, ferner interaktive und kombinierte Lösungsverfahren. Es wurde ausgeführt, dass aufgrund häufig grosser Datenmengen heuristische Ansätze in der Praxis meist den Vorzug erhalten, da exakte Lösungsansätze zu rechenaufwendig sind.