Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:start [06.12.2022 13:11] – [Das Minimaler Spannbaum Problem (Minimal spanning tree)] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:start [07.12.2022 13:38] – [Näherungslösung für das TSP mit MST Algorithmen] Frank Schiebel | ||
---|---|---|---|
Zeile 38: | Zeile 38: | ||
===== Das Minimaler Spannbaum Problem (Minimal spanning tree) ===== | ===== Das Minimaler Spannbaum Problem (Minimal spanning tree) ===== | ||
- | <WRAP center round info 60%> | + | <WRAP center round info 95%> |
Gegeben ist ein zusammenhängender, | Gegeben ist ein zusammenhängender, | ||
Zeile 44: | Zeile 44: | ||
</ | </ | ||
+ | |||
+ | |||
+ | |||
+ | ===== Vertiefung: Fragen & Aufgaben ===== | ||
+ | |||
+ | {{: | ||
+ | === (A3) === | ||
+ | |||
+ | Wende den Algorithmus "MST (Prim)" | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
+ | |||
+ | Öffne den Stadtplan von Baden-Baden (03_badenbaden.csv) und die Karte mit den Fährstrecken (04_inseln.csv) jeweils im Graphentester. Gib je eine realitätsnahe Problemstellung für diese Graphen an, bei denen ein minimaler Spannbaum die beste Lösung ist. | ||
+ | |||
+ | ++++ Lösungsvorschläge | | ||
+ | * Stadtplan: z.B. Wasserrohre, | ||
+ | * Inselkarte: Beschränkung auf Fährverbindungen mit einer möglichst kurzen Gesamtstrecke, | ||
+ | ++++ | ||
+ | |||
+ | ===== Zwei Algorithmen ===== | ||
+ | |||
+ | Wir betrachten zwei Algorithmen zur Lösung des Problems des minimal spannenden Baums: | ||
+ | * [[.kruskal: | ||
+ | * [[.prim: | ||
+ | |||
+ | ===== Weitere Fragen und Aufgaben ===== | ||
+ | |||
+ | {{: | ||
+ | === (A5) === | ||
+ | |||
+ | Untersuche, ob die Algorithmen zur Bestimmung des minimalen Spannbaums auch mit negativen Kantengewichten zurechtkommt. | ||
+ | |||
+ | ++++ Lösung | | ||
+ | Negative Kantengewichte stellen kein Problem dar, da es beim Algorithmus nur auf die Sortierreihenfolge der Kanten ankommt und nicht auf den Wert des Gewichts. Diese Sortierung funktioniert auch bei negativen Kantengewichten. | ||
+ | ++++ | ||
+ | ---- | ||
+ | {{: | ||
+ | === (A6) === | ||
+ | |||
+ | Begründe, warum es sich bei den Algorithmen zur Bestimmung des minimalen Spannbaums um Greedy-Algorithmen handelt. | ||
+ | ++++ Lösung | | ||
+ | Kruskal ist ein Greedy-Algorithmus, | ||
+ | |||
+ | Prim ist ein Greedy-Algorithmus, | ||
+ | ++++ | ||
+ | |||
+ | |||
+ | ===== Näherungslösung für das TSP mit MST Algorithmen ===== | ||
+ | |||
+ | |||
+ | {{: | ||
+ | === (A7) === | ||
+ | |||
+ | Beim Traveling Salesman Problem (TSP) sucht man nach der kürzesten Route durch eine gegebene Liste von Städten, die ein Handlungsreisender besuchen muss. Am Ende soll er wieder zu Hause ankommen. | ||
+ | |||
+ | Für dieses Problem kennt man keinen effizienten Algorithmus. Man kann aber die Algorithmen zur Bestimmung eines MST abändern, so dass sie eine Näherungslösung für das TSP darstellen. | ||
+ | |||
+ | Beschreibe die Veränderungen die am Algorithmus für den MST notwendig sind, um das TSP zu lösen. Du kannst dazu im Graphentester die Algorithmen "TSP (Greedy: Knoten)" |