座標データが200個、全ての座標を通って、移動距離が最小になるような経路(座標順番)を求めたいです。

巡回セールスマン問題だと思います。

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

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

ああ、情けない。。

回答の条件
  • 1人2回まで
  • 13歳以上
  • 登録:2012/02/20 19:27:59
  • 終了:2012/02/27 19:30:12

回答(3件)

id:oil999 No.1

oil999回答回数1728ベストアンサー獲得回数3202012/02/20 20:55:42

ポイント167pt

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

id:ffooqq

これは見ましたが、厳密解ではないですね

2012/02/21 01:40:28
id:oil999

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

2012/02/21 08:39:18
id:fiwa No.2

fiwa回答回数1200ベストアンサー獲得回数2532012/02/20 23:49:31

ポイント167pt

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

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

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

id:ffooqq

これはっ!!

英文の理解が十分ではないのでわからないですが、
もしかして200都市くらいなら厳密解が得られるかも!?
座標に依るのかなぁ

このiOSアプリの挙動はみていて楽しいです。

2012/02/21 22:53:34
id:mododemonandato No.3

mododemonandato回答回数759ベストアンサー獲得回数772012/02/21 10:31:20

ポイント166pt

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

 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軒ではとても無理でしょう。
どのような仕事に使うのか知りませんが、もっと問題を分割するとか、近似値を求めるというような方法を取るしかないと思われます。

他1件のコメントを見る
id:ffooqq

巡回セールスマン問題のWikipedia内にあるこの記述、

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

これを信じて探しまわっているんですが、、やっぱりないんですかねぇ。

2012/02/21 22:53:40
id:JULY

実は、私もちょっと調べた中で、整数計画問題として解く、という物を見つけていました。

http://www.geocities.jp/longest_route/index.html

ただ、自分で試していないので、回答としては書きませんでした。それに、整数計画問題として解けるための条件とかを理解していないんで。

2012/02/22 09:08:40

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません