Intelligente Suchverfahren mit Python

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 und einfach 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.

Präsentationen

P04 Minimal.pdf zum minmal spanning tree
P04-1 Algorithmus von Kruskal.pdf
P04-b-1 Kruskal-Gallenbachergraph.pdf
P04-2 Von Dijkstra zu Prim.pdf
P04-b-2 Prim-Gallenbachergraph.pdf

Projekte

Algorithmus-von-Prim.zip
zum Problem des minimalen Versorgungsbetzes
(minimal spanning tree)
Algorithmus-von-Kruskal.zip
Dazu zwei Demoversionen zum Algorithmus von Prim
Graphen Demoversion mit Schrittfunktion Prim.zip
und zum Algorithmus von Kruskal
Graphen Demoversion mit Schrittfunktion Kruskal.zip
jeweils mit dem Einsatz einer Schrittfunktion
und eine interaktive Version
Graphen interaktive Version.zip mit dem Original-Algorithmus von Prim