Greedy Algorithmen
Algorithmen, bei denen keine Entscheidung rückgängig gemacht werden muss
Wir kennen 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.
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
- Greedy Algorithmen
- Probleme
- A-Stern
- Genetische Algorithmen
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
Texte
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
Ein minimales Versorgungsnetz
Software
Die mit Python entwickelte Software zum Erstellen von Graphen finden Sie im Abschnitt zur Software.
Programmierumgebung: Racket