巡回セールスマン問題だと思います。
業務で必要になり、今日一日考えて結果を出せませんでした。不勉強が身にしみます。。
座標入力したら答え（厳密解）が出るようなアプリ、もしくはソースコード（厳密解）ありませんでしょうか。
VBAかCくらいなら調べなから理解できます。
いま総当りのプログラムをエクセルで考えている途中ですが、座標が200個あると計算終わらないですよねきっと。
ああ、情けない。。
No.1
1728
320
167pt
遺伝子アルゴリズムを用いた解法が、サンプルプログラムとともに以下に掲載されています。
http://msdn.microsoft.com/ja-jp/academic/cc998607.aspx
No.2
1200253
167pt
iOSの無料アプリにこんなのがあるそうですよ。
iTunes Preview: Concorde TSP
同じくConcordeを用いたオンラインソルバー
NEOS Server: concorde
Concordeソースコード、Windows用プログラム他のダウンロードページ
Concorde Downloads
これはっ！！
英文の理解が十分ではないのでわからないですが、
もしかして200都市くらいなら厳密解が得られるかも！？
座標に依るのかなぁ
このiOSアプリの挙動はみていて楽しいです。
No.3
76077
166pt
それはちょっと無理ですね。
「巡回セールスマン問題」 が難問である理由は、その膨大な計算量にあります。
http://www.infonet.co.jp/ueyama/ip/software/tsp.html
いまここに、32 軒の巡回経路の長さを １秒間に１兆回 計算できるスーパーコンピュータ があるとします 。
１秒間に １兆回 （１０の12乗回） の計算ができます。
このスーパーコンピュータを使って 4.11 ×１０の33乗 回の計算をするには 4.11 ×１０の21乗秒が必要です。
１年は、約 ６０×６０×２４×３６５＝３１５３６０００≒ 3.15 ×１０の7乗秒ですから、 4.11 ×１０の21乗秒を １年≒ 3.15 ×１０の7乗 秒で割ると、 答は 1.3 ×１０の14乗年です。 すなわち、130 兆年 かかることになります。
たった32軒でもスパコンで130兆年かかるのに200軒ではとても無理でしょう。
どのような仕事に使うのか知りませんが、もっと問題を分割するとか、近似値を求めるというような方法を取るしかないと思われます。
巡回セールスマン問題のWikipedia内にあるこの記述、
「よく誤解されているが、NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているのであって、巡回セールスマン問題の場合、約2000都市以内の比較的小さい問題例に対して、あるいは問題例によっては解が得られないことがあってもよいのであれば、（線形計画法と論理木を組み合わせた）分枝限定法や、（線形計画法と巡回群を組み合わせた）切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い。」
これを信じて探しまわっているんですが、、やっぱりないんですかねぇ。
実は、私もちょっと調べた中で、整数計画問題として解く、という物を見つけていました。
http://www.geocities.jp/longest_route/index.html
ただ、自分で試していないので、回答としては書きませんでした。それに、整数計画問題として解けるための条件とかを理解していないんで。
5
4
2
2
1
これは見ましたが、厳密解ではないですね
2012/02/21 01:40:28巡回セールスマン問題は計算コストに見合う最適解を求める手法です。
2012/02/21 08:39:18コストを度外視して厳密解を求めるには、総当たりするしかありません。