Variation von TSP, die mehrere Städte besucht

Question

Ich bin auf der Suche Branch and Bound Lösung für TSP mit mehr Besuchen zu diskutieren. (Dh jede Stadt mindestens einmal besucht zu werden braucht, statt nur einmal)

Edit:

Entfernt die Zweifel, da es nicht relevant war, wie durch Jitse hingewiesen. Die Frage ist nun klarer.

Answer 1

einfach das Diagramm erweitert durch Hinzufügen, für jedes Paar von Knoten A und B, eine Kante des kürzesten Weg von A nach B. Der repräsentierte Floyd-Warshall-Algorithmus dies in O erlaubt, zu tun (n ^ 3), die viel schneller als jeder TSP-Algorithmus ist. Sobald Sie dies getan haben, verwenden Sie einen Standard TSP Zweig und gebundene Technik. Diese Seite einige Informationen von Applegate Buch , die Verzweigung und Schranke für TSP diskutiert nach dem Wikipedia TSP Eintrag .

Answer 2

Ich würde lieber das auf Martin Hock Antwort als Kommentar abgeben, da ich eine mögliche Aufsicht bin Adressierung, die leicht sein würde, seinen Vorschlag zu machen umzusetzen.

Der Branch and Bound Algorithmus benötigt für die Rekonstruktion geringsten Kosten Pfade die Ausgabe des Floyd-Warshall-Algorithmus gegeben mit einem Algorithmus kombiniert werden. Der Branch and Bound Algorithmus ist die äußeren Schleife, und es wählt unvisited Knoten. Dann nutzen Sie das geringste Rekonstruktionsalgorithmus Kosten Weg, um tatsächlich Kanten und Knoten zu Ihrem Zyklus hinzuzufügen. Knoten als besucht werden sollten durch den geringsten Kosten Weg Rekonstruktionsalgorithmus markiert, nicht nur durch den Zweig und gebundenen Teil.