Asymetrisches TSP umwandeln < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:34 Do 16.08.2012 | | Autor: | Joshkar |
Hallo zusammen,
ich habe ein Reihenfolgeproblem als asymmetrisches Travelling Salesman Problem modelliert und auch schon eine Lösung erhalten. Allerdings existieren für ATSP weitaus weniger Algorithmen zur Lösungsfindung, sodass ein symetrisches TSP wünschenswert ist. Ich habe von der Möglichkeit gelesen, eine asymmetrische Kostenmatrix in eine symmetrische umzuformen. Leider habe ich keine Ahnung wie genau dies von statten geht. Kann mir jemand helfen folgende einfache Matrix in eine symetrische umzuwandeln ?
[mm] \begin{bmatrix}
- & 2 & 5 & 4 \\
4 & - & 3& 3 \\
7 & 4 & - & 4 \\
1 & 6 & 3 & -
\end{bmatrix}
[/mm]
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Viele Grüße
joshkar
|
|
| |
|
Hi,
man fügt weitere Städte ein, die nicht erreichbar sind. Ich finde leider nicht den Artikel mehr.
![[]](/images/popup.gif) Aber hier steht etwas ähnliches
(findet man im übrigen auch mittels ("atsp symmetric")
gruß
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:22 Di 21.08.2012 | | Autor: | wieschoo |
Ich habs doch noch gefunden:
Roy Jonker, Ton Volgenant, Transforming asymmetric into symmetric traveling salesman problems, Operations Research Letters, Volume 2, Issue 4, November 1983, Pages 161-163, ISSN 0167-6377, 10.1016/0167-6377(83)90048-2.
(http://www.sciencedirect.com/science/article/pii/0167637783900482)
Keywords: Traveling salesman problem
Falls du keinen Zugriff darauf hast, kann ich es dir senden.
|
|
|
|
