Approximierbarkeit TSP < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi!
Mit folgendem Theorem habe ich meine Schwierigkeiten:
"Für TSP (in allgemeiner Form) existiert kein polynomieller r-Approximationsalgorithmus (r [mm] \in \IR, [/mm] r > 1), es sei denn es gilt P = NP"
Bei "mir" wird der allg. TSP so definiert:
* vollständiger, ungerichteter Graph G=(V,E) mit Kantengewicht [mm] w:E\to \IN \cup \{\infty\}
[/mm]
* Gesucht ist Hamiltonkreis C [mm] \subseteq [/mm] E mit min [mm] \summe_{e\in C}^{} [/mm] w(e)
Die Grundidee des Beweises ist dann ja so, dass man das HC-Problem ("Enthält ein Graph G' einen Hamiltonkreis?") auf TSP reduziert: Kanten die es in G' gibt werden mit Gewicht 1 in G eingefügt. Kanten die es in G' nicht gibt werden mit einem sehr großen Gewicht in G eingefügt (z.B. r*5).
Daraus kann man dann ableiten ob G hamiltonisch ist und hat einen r-Approximationsalgorithmus [mm] A_r:
[/mm]
G ist hamiltonisch [mm] \Rightarrow A_r [/mm] findet Tour mit Kosten < r*n
G ist nicht hamiltonisch [mm] \Rightarrow A_r [/mm] findet keine Tour mit Kosten < r*n (weil man eben min eine Kante mit großem Gewicht nehmen muss)
Also kann man so das Hamiltonkreisproblem entscheiden.
(soweit verstanden)
Nun zum Widerspruch:
" [mm] A_r [/mm] ist ein Polynomialzeitalgorithmus, aber HC ist NP-hart."
Meiner Meinung kann das nun bedeuten, dass NP = P gilt ODER dass es diesen Algorithmus [mm] A_r [/mm] nicht gibt bzw. er nicht polynomiell ist.
Per Voraussetzung war P [mm] \not= [/mm] NP gesetzt, also verstehe ich rein formal, dass hier ein Widerspruch ist.
Aber wieso ist dann [mm] A_r [/mm] nicht polynomiell bzw. wieso kann man daraus nicht P=NP ableiten?
Wieso kann man sagen, dass der reine TSP nicht approximierbar ist, aber dennoch die Frage P=NP ungelöst ist?
Ich hoffe Ihr könnt das ein wenig aufklären
VG
Pille
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 16.09.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
