Minimales Versorgungsnetz
Algorithmen, bei denen keine Entscheidung rückgängig gemacht werden muss
Wir kennen (neben dem Algorithmus von Dijkstra) bereits einen greedy (gierigen) Algorithmus
von der ersten fuelle-Funktion. Die Idee ist, immer den besten aktuellen Wert weiter zu verfolgen
Leider hat unsere erste fuelle-Funktion den Nachteil, dass sie nicht alle Lösungen findet.
Es gibt aber Algorithmen, die ebenfalls während des Suchprozesses keine Entscheidungen
rückgängig machen und trotzdem sicher eine beste Lösung finden. Ob das geht, hängt vom
Problem ab und das hier betrachtete Problem des minimal spanning tree ist ein solches Problem.
Die beiden hier betrachteten Algorithmen sind der Algorithmus von Prim und der
Algorithmus von Kruskal.
Siehe aber auch die Abschnitte zum Algorithmus von Dijkstra und A-Stern.
Präsentationen
- P04-1 Algorithmus von Kruskal.pdf
- P04 Von Dijkstra zu Prim.pdf
- P04-2 Algorithmus von Prim.pdf
- P04 Prim Daten & Programm.pdf
- P04-a Prim Funktionen.pdf
Projekte
Animationen
- Animation-Prim-Algorithmus.zip kleiner Graph
- Animation-Kruskal-Algorithmus.zip kleiner Graph
- Animation-Kruskal-Algorithmus kommentiert.zip kleiner Graph
- P04-b-1 Kruskal-Gallenbachergraph.pdf Gallenbachergraph
- P04-b-1 Reihenfolge der Kanten.txt Daten zu Kruskal beim Gallenbachergraphen
- P04-b1 Prim-Gallenbachergraph.pdf Gallenbachergraph
Texte
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 minimales Versorgungsnetz
Software
Die mit Python entwickelte Software zum Erstellen von Graphen finden Sie im Abschnitt zur Software.
Programmierumgebung: Racket