Können wir das Problem des reisenden Verkäufers lösen, indem wir den minimalen Spannbaum für den gerichteten Graphen finden, dessen Knoten die zu besuchenden Städte sind und die Gewichte die Entfernungen zwischen den Städten sind? Gezielte Grafik, um ein Szenario zu betrachten, in dem Entfernung (Stadt-A, Stadt-B)! = Entfernung (Stadt-B, Stadt-A).
Das Minimum Spanning Tree-Problem fordert Sie auf, einen Baum zu erstellen, der alle Städte verbindet und ein minimales Gesamtgewicht hat, während das Travelling Salesman Problem Sie auffordert, eine Reise zu finden, die alle Städte mit minimalem Gesamtgewicht besucht (und möglicherweise zurückkommt) Startpunkt).
Wenn Sie den Unterschied nicht sehen können, müssen Sie in MST eine Struktur mit minimalem Gewicht in einem gewichteten Diagramm finden, während Sie in TSP einen Pfad mit minimalem Gewicht finden müssen (oder Zyklus / Schaltkreis ). Hilft das?
Es ist der Unterschied zwischen "Finden eines azyklischen verbundenen Teilgraphen T von G mit V (T) = V (G) und Gewicht (T) ist minimal" und "Finden eines Zyklus C in G, so dass V (C) = V (G) und Gewicht (C) ist minimal "wo Gewicht (X) = Summe der Kanten von X.
Tags und Links algorithm