Das Travelling Salesman Problem |
| 16.10.2015, 22:49 | Auf diesen Beitrag antworten » |
| kim | Das Travelling Salesman Problem Meine Frage: Hallöle Leute, Ich habe da mal eine Frage. Ich hoffe ihr könnt mir helfen! Auf der folgenden Seite ist das Problem eines Handlungsreisenden aufgeführt http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php und es wird zunächst die Holkzhammer-Methode erklärt. Dort ist eine Tabelle abgebildet bei der steht, dass man für 4 städte 3 Mögliche Rundreisen hat, aber in der Abbildung davor stehen die 6!! Möglichen Rundreisen für 4 Städte. Daher verstehe ich die zwei unterschiedlichen Aussagen nicht. Und die Aussage " Bei den unteren drei Touren handelt es sich, wie man leicht sieht, um Umkehrungen der oberen drei Touren, so dass man eigentlich nur für die Hälfte der Rundreisen die Gesamtlängen ausrechnen muss." ist für mich nicht verständlich, da ich zwwischen den letzen 3 Zeilen und ersten 3 Zeilen keine Gemeinsamkeit erkenne Meine Ideen: Ich selber finde leider seit zwei Stunden keine Lösung für mein Problem. Ich hoffe ihr könnt mir helfen 
VIELE DANK!! |
|
|
|
| 17.10.2015, 07:25 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Vergleiche in Abb. 1 mal zwei untereinander liegende Graphen. Das ist die selbe Route, nur einmal im und einmal gegen den Uhrzeigersinn. Daher kommt der Faktor 1/2. |
|
|