人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

座標データが200個、全ての座標を通って、移動距離が最小になるような経路(座標順番)を求めたいです。
巡回セールスマン問題だと思います。

業務で必要になり、今日一日考えて結果を出せませんでした。不勉強が身にしみます。。

座標入力したら答え(厳密解)が出るようなアプリ、もしくはソースコード(厳密解)ありませんでしょうか。
VBAかCくらいなら調べなから理解できます。
いま総当りのプログラムをエクセルで考えている途中ですが、座標が200個あると計算終わらないですよねきっと。

ああ、情けない。。

●質問者: ffooqq
●カテゴリ:コンピュータ
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● oil999
●167ポイント

遺伝子アルゴリズムを用いた解法が、サンプルプログラムとともに以下に掲載されています。
http://msdn.microsoft.com/ja-jp/academic/cc998607.aspx


ffooqqさんのコメント
これは見ましたが、厳密解ではないですね

oil999さんのコメント
巡回セールスマン問題は計算コストに見合う最適解を求める手法です。 コストを度外視して厳密解を求めるには、総当たりするしかありません。

2 ● fiwa
●167ポイント

iOSの無料アプリにこんなのがあるそうですよ。
iTunes Preview: Concorde TSP

同じくConcordeを用いたオンラインソルバー
NEOS Server: concorde

Concordeソースコード、Windows用プログラム他のダウンロードページ
Concorde Downloads


ffooqqさんのコメント
これはっ!! 英文の理解が十分ではないのでわからないですが、 もしかして200都市くらいなら厳密解が得られるかも!? 座標に依るのかなぁ このiOSアプリの挙動はみていて楽しいです。

3 ● mododemonandato
●166ポイント

それはちょっと無理ですね。
「巡回セールスマン問題」 が難問である理由は、その膨大な計算量にあります。

http://www.infonet.co.jp/ueyama/ip/software/tsp.html


いまここに、32 軒の巡回経路の長さを 1秒間に1兆回 計算できるスーパーコンピュータ があるとします 。

1秒間に 1兆回 (10の12乗回) の計算ができます。
このスーパーコンピュータを使って 4.11 ×10の33乗 回の計算をするには 4.11 ×10の21乗秒が必要です。

1年は、約 60×60×24×365=31536000≒ 3.15 ×10の7乗秒ですから、 4.11 ×10の21乗秒を 1年≒ 3.15 ×10の7乗 秒で割ると、 答は 1.3 ×10の14乗年です。 すなわち、130 兆年 かかることになります。

たった32軒でもスパコンで130兆年かかるのに200軒ではとても無理でしょう。
どのような仕事に使うのか知りませんが、もっと問題を分割するとか、近似値を求めるというような方法を取るしかないと思われます。


JULYさんのコメント
1秒間に1兆回、というのは、今となってはちょっと保守的な数字だと思います。 理化学研究所のスパコン「京」の理論演算性能が 11.28FLOPS なので、単純に考えれば、1秒間に1京回の演算ができます。もちろん、巡回経路の距離を求めるのステップ数を考えないと、1秒間に何経路の計算が出来るか、という数字はもっと小さくなりますが、2ケタ下に見積もっても、100 兆回になります。 ただ、仮に1京経路を1秒間に計算できたとして、そんなスパコンを1万台用意して並列計算しても 130 万年かかるので、厳密解を求めるのは無理、という本質は変わりません。

ffooqqさんのコメント
巡回セールスマン問題のWikipedia内にあるこの記述、 「よく誤解されているが、NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているのであって、巡回セールスマン問題の場合、約2000都市以内の比較的小さい問題例に対して、あるいは問題例によっては解が得られないことがあってもよいのであれば、(線形計画法と論理木を組み合わせた)分枝限定法や、(線形計画法と巡回群を組み合わせた)切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い。」 これを信じて探しまわっているんですが、、やっぱりないんですかねぇ。

JULYさんのコメント
実は、私もちょっと調べた中で、整数計画問題として解く、という物を見つけていました。 http://www.geocities.jp/longest_route/index.html ただ、自分で試していないので、回答としては書きませんでした。それに、整数計画問題として解けるための条件とかを理解していないんで。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ