Kürzester Weg
Wie findet man den kürzesten Weg zu einem Ziel
Wie alle Probleme kann man auch die Suche nach einem kürzesten Weg mit Tiefensuche oder Breitensuche bearbeiten, also mit einer "brute force" - Strategie. Bei großen Suchräumen, die bei realen Problemen oft auftreten, ist das aber nicht erfolgreich. Hier geht es also um intelligentere Strategien. Der hier beschriebene Kurs orientiert sich an dem Vorgehen im empfehlenswerten Buch von Gallenbacher.
Präsentationen
- Allgemein: Wegeprobleme P03 Wegeprobleme.pdf
- P03-1 Graphen-Knoten-Kanten.pdf
- P03-a Graphen Modell und Datenstruktur.pdf
- P03-c1 Dijkstra Funktionale Analyse_Knotenliste.pdf
- P03-d1 Dijkstra Programm Modularisierung-Knoten.pdf
- P03-c2 Dijkstra Funktionale Analyse_Kantenliste.pdf
- P03-d2 Dijkstra Programm Modularisierung-Kanten.pdf
- P03-e Gallenbacher_Kuerzester_Weg.pdf zur Version von Gallenbacher
- P03-e Gallenbacher-Graph-Entwicklung.pdf
- P03-e3 Dijkstra-Schritte kleiner-Graph-Py.pdf
- P03-f Prioritaetswarteschlange.pdf
Schrittweise Erarbeitung einer funktionalen Pythonversion der Datenstruktur Prioritätswarteschlange sowie Angabe einer iterativen Version - P03-g Dijkstra Typisierung.pdf
- ADTs aus objektorientierter Sicht:
ADT Stack.pdf
ADT Warteschlange.pdf
ADT Prioritaetswarteschlange.pdf
Projekte
- Dijkstra mit Gallenbacher-Graph
- Variante iterativ, OO und rekursiv
Dijkstra-Gallenbacher-Python - rekursive Variante
Dijksta-Gallenbacher-rekursives-Py-Projekt - iterative Variante der Prioritätswarteschlange
prioritaetswarteschlange-iterativ.py - Eine Demoversion zur schrittweisen Ausführung
Graphen Demoversion mit Schrittfunktion Dijkstra.zip - objektorientierte Variante
Dijkstra-Gallenbacher-objektorientiert - Variante mit Kantenliste
Dijstra-Gallenbacher-Kanten - Kleiner Graph, Variante mit Kantenliste
Dijkstra-kleiner-Graph-Kanten
Material zum Python-Kurs
Das Material zum Kurs ist abschnittsweise, auf mehrere Seiten verteilt abgelegt.
- Material zu Python
- Einstieg in den Kurs
- Tiefensuche und Breitensuche
- Kürzester Weg
- Minimales Versorgungsnetz
- Probleme
- A-Stern
- Genetische Algorithmen
Ein Graph
Texte
- KI-03 Kurztext zu Gallenbacher mit Algorithmus.pdf
- KI-03-c Orte-Reihenfolge-Bewertung.pdf zum Gallenbacher-Graphen
Literaturbeispiele speziell zu diesem Thema
- Gritzmann, Brandenberg: Das Geheimnis des kürzesten Weges
- Gallenbacher: Abenteuer Informatik ISBN 978-3-662-63738-8