Ich kenne TSP als "nur" NP-hart, erst die Fragestellung "Gibt es eine Route, die kürzer ist als x?" ist -vollständig.
Und TSP wird normalerweise greedy implementiert, also mit einem Algorithmus, der in jedem Schritt das Optimum wählt, in der Annahme, dass das globale Optimum in der Nähe der Folge aller lokalen Optima liegt. Selbst wenn man das Lokalitätsprinzip etwas aufbohrt, in dem man das Optimum innerhalb eines Fensters der letzten x Kanten sucht - was die Komplexität direkt beeinflusst - bleibt es ein Greedy-Algorithmus.
Erst wenn das Fenster so groß ist wie der kürzeste Weg ist das lokale Optimum innerhalb des Fensters gleich dem globalen Optimum. Die dadurch gegebene Komplexität will man aber sicher nicht in Kauf nehmen.
Deshalb kann man nicht einfach TSP laufen lassen und am Ende die Rückreise zum Ausgangspunkt streichen. Denn dieser letzte Weg geht in den zu findenden kürzesten Pfad mit ein. Streicht man ihn einfach raus, ist der verbliebene Weg nicht mehr notwendigerweise der kürzeste.
Vielleicht wirds anhand eines Beispiels verständlicher:
Seien A, B, C, D Knoten mit folgenden Entfernungen:
A -> B = 1
A -> C = 2
A -> D = 3
B -> C = 4
B -> D = 3
C -> D = 6
Wir starten in A.
Die möglichen Rundreisen und ihre Längen sind:
A-B-C-D-A = 1-4-6-3 = 14
A-B-D-C-A = 1-3-6-2 = 12
A-C-B-D-A = 2-4-3-3 = 12
A-C-D-B-A = 2-6-3-1 = 12
A-D-B-C-A = 3-3-4-2 = 12
A-D-C-B-A = 3-6-4-1 = 14
Ein greedy TSP-Algorthmus hätte A-B-D-C-A als Lösung angegeben, was sogar tatsächlich eine der optimalen Lösungen ist. Aber läßt man von dieser Lösung den Rückweg C-A einfach untern Tisch fallen, bleibt A-B-D-C übrig. Das ist allerdings keine optimale Lösung mehr! Denn A-C-B-D und auch A-D-B-C wären kürzer (9).
Das war sicher mühselig zu lesen, aber hoffentlich leicht zu verstehen. Man kann nicht einfach eine TSP-Lösung ändern und behaupten, es wäre immernoch eine Lösung!
Das läßt sich auf die Unzulänglichkeit von Greedy für TSP reduzieren und beweist, dass Greedy für o.g. Problem nicht garantiert optimale Lösungen liefert. Wer hätte das gedacht...
@TO: Google mal nach AHOP, vielleicht hilfts weiter.