Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:start [07.12.2022 13:36] – [Weitere Fragen und Aufgaben] 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 73: | Zeile 73: | ||
===== Weitere Fragen und Aufgaben ===== | ===== Weitere Fragen und Aufgaben ===== | ||
- | ---- | ||
{{: | {{: | ||
=== (A5) === | === (A5) === | ||
Zeile 94: | Zeile 93: | ||
+ | ===== 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 '' | ||
+ | |||
+ | ++++ 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, | ||
+ | ++++ |