Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:start [06.12.2022 13:19] – [Zwei Algorithmen] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:start [07.12.2022 13:39] (aktuell) – [Näherungslösung für das TSP mit MST Algorithmen] Frank Schiebel
@@ Zeile 52: / Zeile 52: @@
 === (A3) ===
-Wende einen Algorithmus zur Bestimmung des minimalen Spannbaums im Graphentester auf die Karte der größten Städte in Deutschland an (02_deutschlandkarte.csv). Beachte, dass nur markierte Kanten sichtbar sind, da es zu viele Kanten gibt, um sie alle übersichtlich darzustellen. Vergleiche mit dem Autobahnnetz in Deutschland. Nenne Ursachen für Unterschiede.
+Wende den Algorithmus "MST (Prim)" zur Bestimmung des minimalen Spannbaums im Graphentester auf die Karte der größten Städte in Deutschland an (''02_deutschlandkarte.csv'' im Ordner ''08_minimalspanningtree''). Beachte, dass nur markierte Kanten sichtbar sind, da es zu viele Kanten gibt, um sie alle übersichtlich darzustellen. Vergleiche mit dem Autobahnnetz in Deutschland. Nenne Ursachen für Unterschiede.
 ----
@@ Zeile 58: / Zeile 58: @@
 === (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 praktische Aufgabenstellung für diese Graphen an, bei denen ein minimaler Spannbaum die beste Lösung ist.
+Ö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 |
@@ Zeile 68: / Zeile 68: @@
 Wir betrachten zwei Algorithmen zur Lösung des Problems des minimal spannenden Baums:
-  * Algorithmus von Kruskal((https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal))
+  * [[.kruskal:Start|Algorithmus von Kruskal]]((https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal))
-  * Algorithmus von Prim((https://de.wikipedia.org/wiki/Algorithmus_von_Prim))
+  * [[.prim:start|Algorithmus von Prim]]((https://de.wikipedia.org/wiki/Algorithmus_von_Prim))
+===== Weitere Fragen und Aufgaben =====
+{{:aufgabe.png?nolink  |}}
+=== (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.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (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, da in jedem Schritt die günstigste Kanten ausgewählt wird, die nicht zu einem Zyklus führt.
+Prim ist ein Greedy-Algorithmus, da immer die kürzeste Kante gewählt wird, um den Baum zu erweitern.
+++++
+===== Näherungslösung für das TSP mit MST Algorithmen =====
+{{:aufgabe.png?nolink  |}}
+=== (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)'' und ''TSP (Greedy: kürzeste Kante)'' zu Hilfe nehmen.
+++++ Erläuterung zur Lösung |
+Der Prim-Algorithmus vereinfacht sich, da die kürzeste Kante von einem markierten zu einem unmarkierten Knoten für das TSP nicht im ganzen bisherigen Baum gesucht werden muss, sondern am Ende der Route liegen muss. Man muss also nur die ausgehenden Kanten des Routenendes zu allen noch nicht markierten Knoten betrachten (vgl. TSP-Greedy im Graphentester). Am Ende wird die Rundreise durch eine Kanten zwischen den beiden Blättern des Baums geschlossen.
+Der Kruskal-Algorithmus wird etwas komplizierter, da man beim Zusammenführen zweier Teilbäume oder Vergrößern eines Teilbaums darauf achten muss, dass keine innere Knoten sondern nur Blätter verwendet werden dürfen. Außerdem muss zum Schließen der Rundreise am Ende einmal erlaubt werden, einen Zyklus zu bilden.
+++++