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
- P03 Wegeprobleme.pdf
- P03-a Graphen Modell und Datenstruktur.pdf
- P03-b Datenstrukturen zu Graphen Beispiel.pdf
- P03-c1 Dijksta Funktionale Analyse_Knoten.pdf
- P03-c2 Dijksta Funktionale Analyse_Kanten.pdf
- P03-d1 Dijksta Programm Modularisierung-Kanten.pdf
- P03-d2 Dijksta Programm Modularisierung-Knoten.pdf
- P03-e Gallenbacher-Graph-Entwicklung.pdf
- P03-e1 Gallenbacher_Kuerzester_Weg_Kanten.pdf
- P03-e2 Gallenbacher_Kuerzester_Weg_Knoten.pdf
- P03-e3 Dijkstra-Schritte kleiner-Graph.pdf
- P03-f Prioritaetswarteschlange.pdf
- P03-g Dijkstra Typisierung.pdf
Projekte
- Graph-mit-Zugriffsfunktionen.zip
- kleiner Graph-mit-Zugriffsfunktionen.zip
- Dijkstra-Kanten-Gallenbacher.zip neu überarbeitet (2022-02-11)
- Programme zur Erarbeitung-Dijkstra.zip zu der o.a. Version
- P03-Aufgaben zur Erarbeitung-Dijkstra.zip die Aufgaben-Präsentationen zu der o.a. Version
- gallenbacher-graph-knoten.scm Datenstruktur mit Zugriffsfunktion für die Knotenliste
- Dijkstra-Gallenbacher-mit-Knotenliste.zip komplett mit Knotenliste
Texte
- KI-03 Kurztext zu Gallenbacher mit Algorithmus.pdf
- KI-03-a Algorithmus von Dijkstra Gallenbacher.pdf
- KI-03-b Gallenbacher-Graph-Daten.pdf
- KI-03-c Orte-Reihenfolge-Bewertung.pdf
Literaturbeispiele speziell zu diesem Thema
- Gritzmann, Brandenberg: Das Geheimnis des kürzesten Weges
- Gallenbacher: Abenteuer Informatik ISBN 978-3-662-63738-8
Material zum Kurs
Das Material zum Kurs ist abschnittsweise, auf mehrere Seiten verteilt abgelegt.
- Startseite "Intelligente Suchverfahren"
- Material zu Scheme
- Einstieg in den Kurs
- Tiefensuche
- Breitensuche
- Kürzester Weg
- Minimales Versorgungsnetz
- Probleme
- A-Stern
- Genetische Algorithmen
Ein Graph
Software
Die mit Python entwickelte Software zum Erstellen von Graphen finden Sie im Abschnitt zur Software.
Programmierumgebung: Racket