Optimierungsprobleme (1) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 18:37 Mi 08.02.2006 | | Autor: | mathiash |
| Aufgabe | Die Entscheidungsversion von TSP ist wie folgt definiert:
Gegeben eine endliche Menge V, Distanzfunktion [mm] c\colon V\times V\to\IQ_{\geq 0}, [/mm] eine Zahl [mm] L\in\IQ, [/mm] gibt es eine Tour [mm] \pi [/mm] für V der Länge höchstens L ?
Dabei gelte oE [mm] V=\{0,\ldots , n-1\}, [/mm] dann können wir sagen, eine Tour [mm] \pi [/mm] ist nichts anderes
als eine Permutation [mm] \pi\in S_n [/mm] (also der Zahlen [mm] 0,\ldots [/mm] n-1),
und die Länge von [mm] \pi [/mm] ist dann definiert als
[mm] c(\pi) \: :=\: \sum_{i=0}^{n-1} c(\pi(i),\pi((i+1)\mod\: [/mm] n))
Eine Distanzfunktion sei dabei eien Abb. [mm] c\colon V\times V\to\IQ, [/mm] die symmetrisch, nicht negativ ist und c(x,y)=0 gdw x=y erfüllt, aber nicht notwendig die Dreiecksungleichung.
Die Optimierungsversion ist wie folgt definiert:
Gegeben V,c wie oben, konstruiere eine Tour [mm] \pi [/mm] minimaler Länge.
(1) Zeige: Es gibt einen polynomiellen Algorithmus für die Entscheidungsversion (also einen, der immer die richtige Antwort liefert) genau dann, wenn es einen polynomiellen Algorithmus für die Optimierungsversion gibt (d.h. einen, der immer eine Tour minimaler Länge konstruiert).
(2) Gib einen 2-approximativen polynomiellen Algorithmus für die Optimierungsversion an, d.h. einen, der immer eine Tour konstruiert, die höchstens doppelt so lang wie eine optimale Tour ist.
(3) Gib einen 1.5- approximativen pol. Algorithmus für die Optimierungsversion an.
|
Hallo zusammen,
viel Spass beim ''Lösen''.
Viele Grüße,
Mathias
|
|
|
