TIM Labs

最短距離ではない巡回セールスマン問題

| コメント(0) | トラックバック(0)

巡回セールス問題というと、与えられた点の全てを通る巡回路で一番距離が短いものということであり、下図のようなものを思い浮かべるであろう。

100-Normal.png

今回は、こういう普通のまっとうな巡回セールス問題ではなく、次図のような巡回セールス問題を考えてみよう。

100-Angle2.png

この結果も、巡回セールスマン問題を解くプログラムで巡回路を最適化したものである。
正確に言うと、ほんのちょっとだけプログラムを変更した。

与えられた全ての町(点)を一度だけ通過しているので、巡回しているが、どうみても、距離が最短ではない。最短距離なら、巡回路が重なる場合には、さらに短い巡回路を簡単に作れる。

何だが、ぐるぐる回る巡回路になっているようだが、何を最適化したのだろうか?

殆どの巡回セールスマン問題を取り扱っている本では、巡回セールスマン問題を深く説明することがあっても、巡回セールスマン問題を多様に拡張する、あるいは抽象化することで、非常に多様な問題を解く基本的なアルゴリズムとして使えることの説明がほとんど皆無であり、とても残念である。

...ということで、ぐるぐる回る巡回路について、何を最適化しようとしたか、考えてみよう。

説明は、次回に行う。

(つづく)

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/746

コメントする

このブログ記事について

このページは、fujiが2018年11月15日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「Ethereum, Hyperledger Fabric, Cordaの処理性能ベンチマーク情報まとめ」です。

次のブログ記事は「Azure VM Scale Setsの営業時間外自動シャットダウン」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ