Reduzierbarkeit Hamiltonkreis und TSP

Neue Frage »

bussarde2000 Auf diesen Beitrag antworten »
Reduzierbarkeit Hamiltonkreis und TSP
Hallo zusammen,

meine Frage:

Thema NP-Vollständigkeit

Das Hamiltonkreis-Problem und das TSP-Problem gelten beide als
NP-vollständig.

Das heißt doch, daß beide Probleme polynomial reduzierbar sein müssen auf das jeweils andere.

Wenn jemand TSP polynomial lösen kann, dann kann er auch Hamilton polynomial traurig lösen. Das leuchtet ein, da er die Gewichte einfach auf 0 und 1 reduzieren kann.

Meine Frage ist der umgekehrte Weg.

Wie kann man, wenn man Hamilton lösen kann, damit auch TSP lösen ?

Wie läßt sich das Hamiltonkreisproblem auf TSP reduzieren ?

Das einzige, was ich fand, war, daß man ja fragen könne, ob es in TSP eine Route gebe, die kleiner K ist.

Damit konnte ich aber nix anfangen.

Bin für jeden Hinweis dankbar.
JochenX Auf diesen Beitrag antworten »

hmm, ich krame da etwas in meinem info1/info2 gedächtnis....
ausgang: knotenmenge mit ungerichteten pfaden dazwischen (mehr nötig für TSP: Gewichtung?!)
also hamiltonkreis ist ein pfad, der alle knoten eines diagrammes genau einmal besucht und dann wieder am ausgangsknoten ankommt, oder?
aber was ist TSP? könntest du das kurz erläutern? danke.

mfg jochen
bussarde2000 Auf diesen Beitrag antworten »

Zitat:
Original von LOED
hmm, ich krame da etwas in meinem info1/info2 gedächtnis....
ausgang: knotenmenge mit ungerichteten pfaden dazwischen (mehr nötig für TSP: Gewichtung?!)
also hamiltonkreis ist ein pfad, der alle knoten eines diagrammes genau einmal besucht und dann wieder am ausgangsknoten ankommt, oder?
aber was ist TSP? könntest du das kurz erläutern? danke.

mfg jochen


TSP steht für Traveling Salesman Problem, also die Suche nach der
kürzesten Route, bei der ebenfalls alle Knoten je einmal durchlaufen werden müssen. Die Kanten sind hier gewichtet, während bei Hamilton nur interessiert, on eine Kante da ist, oder eben nicht.
JochenX Auf diesen Beitrag antworten »

falls in einem graphen mehr als 1 hamiltonkreis existieren kann, dann halte ich die obige aussage für falsch.
ich muss allerdings auch zugeben, das ich von der aufwandsklassifizierung nicht so viel verstehe.
dann kann ich dir leider nicht helfen, nur meine (vermutlich) falsche meinung sagen...

mfg jochen
Tobias Auf diesen Beitrag antworten »

Nun, wenn man einen Hamiltonkreis in einem Graphen polynomial berechnen kann, dann kann man bestimmt auch die Menge aller Hamiltonkreise in einem Graphen polynomial berechnen.

Aus dieser Menge sucht man sich dann in Linearzeit den besten Hamiltonkreis und hat TSP gelöst.

Soweit mein naiver Vorschlag. Schwachstelle: Ist die Menge aller Hamiltonkreise wirklich polynomial berechenbar?

Ein anderer Ansatz wäre einer mit dynamischer Programmierung. Man nehme am Anfang zwei Knoten und berechne den besten Hamiltonkreis. Dann nehme man einen weiteren Knoten dazu und berechne wieder den besten Hamiltonkreis etc. Sowas führt meist zu einer Polynomialzeitreduktion.

Ich hoffe die Anregungen halfen.

MfG
bussarde2000 Auf diesen Beitrag antworten »

Zitat:
Original von Tobias
Nun, wenn man einen Hamiltonkreis in einem Graphen polynomial berechnen kann, dann kann man bestimmt auch die Menge aller Hamiltonkreise in einem Graphen polynomial berechnen.

Aus dieser Menge sucht man sich dann in Linearzeit den besten Hamiltonkreis und hat TSP gelöst.

Soweit mein naiver Vorschlag. Schwachstelle: Ist die Menge aller Hamiltonkreise wirklich polynomial berechenbar?

Ein anderer Ansatz wäre einer mit dynamischer Programmierung. Man nehme am Anfang zwei Knoten und berechne den besten Hamiltonkreis. Dann nehme man einen weiteren Knoten dazu und berechne wieder den besten Hamiltonkreis etc. Sowas führt meist zu einer Polynomialzeitreduktion.

Ich hoffe die Anregungen halfen.

MfG


Hamilton und TSP sind momentan nicht polynomial lösbar !
(Der erste, der das schafft kriegt ne Million Dollar)

Hamilton ist gelöst, wenn ich bei vorgegebenen Kanten in polynomialzeit beweisen kann, ob es einen Hamiltonkreis gibt, oder eben nicht.

Wie kann ich daraus ein TSP-Problem machen ?
Bei TSP ist die zahl der möglichen routen ja gigantisch. Alle Kanten ziwschen je 2 Punkten sind gegeben mit gewichten.

Das durchprobieren aller Routen bringt da nix.

Man muß das TSP- Problem, so umformen, daß es zu einem Hamiltonkreis-Problem wird.

Nur wie ?
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »