複数の点を最短距離で全て繋ぐアルゴリズム

C++で以下のようなプログラムを書こうと思うのですが、
効率的なアルゴリズムが思い浮かびません。
よい方法をご存知の方がおりましたら教えてください。

------------------------
xy平面上に複数の点があります。
それぞれの点の座標は全て分かっています。
今、原点から出発して全ての点を直線で結んでいくのですが
このとき引く直線の長さの総計が最小になるような
結び方を見つけたいのです。

全ての結び方をしらみつぶしに調べると
(点の数)!　通りの総直線距離を計算しなければならず
点が増えるとかなり苦しいことになります・・・

No.3 ベストアンサー 回答者： neKo_deux 回答日時： 2005/10/29 15:01

> 具体的に細かなアルゴリズムの組み方まで示したページは

> なかなか見つからないですね・・・

こちら、GAの本なんかに載っているような標準的な方法ですが、図表なんかが多くて解説がわかりやすいです。
参考文献・資料も一緒に見ると良いとおもいます。

アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Art …


＃MSのサイト内ってのが灯台下暗しというか…。

参考URL：http://www.microsoft.com/japan/msdn/academic/Art …

No.4 回答者： goma_2000 回答日時： 2005/10/29 18:29

GA等のヒューリスティクスを使うにしろ、全ての点の距離は計算しなくてはなりません。

これらのヒューリスティクスな手法は、点の組み合わせを求める時に使用するものです。点の数が多い場合には距離を求めるのが難しい場合もありますからね。

今回は２次元であると条件が決まってますので、高速に解くには２次元をメッシュに切って解くのが良いでしょう。これは、メッシュ内の点同士の連結とメッシュ間の連結を分けて考える方法になります。当然、距離の計算は劇的に少なくなります。

例えば、ｘ、ｙ座標、それぞれに対して、１０区間に分けるとすると、１００個のメッシュが出来ます。このメッシュ間の距離を求めて、どのメッシュを繋いでいけばよいかを求めます。また、これとは独立に、メッシュ内に複数の点が含まれる場合には、メッシュ内での点の結び方を求めます。これらを総合すれば解が得られます。


どうでしょうか。

No.2 回答者： 2531kbps 回答日時： 2005/10/29 14:43

点の数や、制限時間でアルゴリズムは決まってくるんじゃないかなあ？

GA（遺伝的アルゴリズム）は、大学時代隣の研究チームがやってましたが、処理中の経過を見るだけでも楽しかったです。

コストをかけられるなら、ここからここまでの処理をお前がやれと別PCに仕事を投げても良いし。このシステムを作るのも大変だ・・・。
コンピューター群が多ければ、仕事を投げる仕事も別PCに任せた方がよいです(笑)。場合によっては仕事の振り分けが間に合わず、ひまなPCが出てきます。

参考URL：http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E% …

No.1 回答者： neKo_deux 回答日時： 2005/10/29 14:24

こちらは「巡回セールスマン問題」と呼ばれる、アルゴリズムの計算速度などの比較にも使われるようなモデル問題です。

逆に「巡回セールスマン問題」の解法などとして情報収集すると、過去に先人達が築き上げた色んなアルゴリズムが見つかると思います。

割と新しい方法で、最適解の保障が無い方法ですと、遺伝的アルゴリズムとか。

--
> 全ての結び方をしらみつぶしに調べると
> (点の数)!　通りの総直線距離を計算しなければならず
> 点が増えるとかなり苦しいことになります・・・

この方法は基準になりますから、一度組んでみてどれくらい遅いのか？というのを実感するのも良いかも。
点の数を調整すれば、計算に100年かかるって事も無いですし。

この回答へのお礼

ありがとうございます。
そういえば聞いた事があるような気がします。

手法の簡単な紹介がされたページはたくさん見つかるのですが、
具体的に細かなアルゴリズムの組み方まで示したページは
なかなか見つからないですね・・・

お礼日時：2005/10/29 14:36