Optimierungsprobleme (2) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 18:44 Mi 08.02.2006 | | Autor: | mathiash |
| Aufgabe | Betrachte TSP, wobei [mm]V\subseteq \{1,\dotsc,n\}\times \{1,\dotsc,k\}[/mm] für konstantes [mm]k[/mm] mit der [mm]L_1\texttt{--Metrik}[/mm] als Distanzfunktion.
Konstruiere einen polynomiellen Algorithmus [mm]A_k[/mm], der dieses Problem optimal löst.
Wie hängt die Laufzeit von [mm]k[/mm] ab ? |
Hallo zusammen,
denkt mal an Dynamische Programmierung !
Gruss,
Mathias
|
|
|
