巡回セールスマン問題の最適解について

最適解は、交わる線がない、とは限らないのですよね？

下のデモ等を見ると、最適解まで求まると、交わった線がなくなっているのですが、これはたまたまそうなった、ということでしょうか？

http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/de …

No.2 ベストアンサー 回答者： momordica 回答日時： 2010/11/24 22:34

都市間を直線で結んで、その直線距離の合計が最小になるようにしているせいでしょう。

このルールだと、図のように交わるルートがある場合、その部分を交わらないように
つなぎかえれば（赤線）もっと短いルートができますから、最短ルートは必然的に
交わりのないものになります。

No.3 回答者： Tacosan 回答日時： 2010/11/24 23:40

一般的な TSP では問題がグラフで与えられるため「線が交わる」かどうかは関係ありません. ただ, このデモで扱っているのはユークリッドTSP だったはずで, その場合には (#2 で書かれているように) 当然交わらない方が短かくなります.

つまり, 問題のクラスによって話が異なります.
ちなみにユークリッドTSP の方が (近似可能性の意味で) 簡単.

No.1 回答者： nag0720 回答日時： 2010/11/24 22:25

巡回セールスマン問題のようなグラフ理論は、点と点との関係性の理論だから、線が交わるとか交わらないとかは関係ないのでは？

2次元の平面上で考えているわけではないのだから。