C++で以下のようなプログラムを書こうと思うのですが、
効率的なアルゴリズムが思い浮かびません。
よい方法をご存知の方がおりましたら教えてください。
------------------------
xy平面上に複数の点があります。
それぞれの点の座標は全て分かっています。
今、原点から出発して全ての点を直線で結んでいくのですが
このとき引く直線の長さの総計が最小になるような
結び方を見つけたいのです。
全ての結び方をしらみつぶしに調べると
(点の数)! 通りの総直線距離を計算しなければならず
点が増えるとかなり苦しいことになります・・・
No.3ベストアンサー
- 回答日時:
> 具体的に細かなアルゴリズムの組み方まで示したページは
> なかなか見つからないですね・・・
こちら、GAの本なんかに載っているような標準的な方法ですが、図表なんかが多くて解説がわかりやすいです。
参考文献・資料も一緒に見ると良いとおもいます。
アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Art …
#MSのサイト内ってのが灯台下暗しというか…。
参考URL:http://www.microsoft.com/japan/msdn/academic/Art …
No.4
- 回答日時:
GA等のヒューリスティクスを使うにしろ、全ての点の距離は計算しなくてはなりません。
これらのヒューリスティクスな手法は、点の組み合わせを求める時に使用するものです。点の数が多い場合には距離を求めるのが難しい場合もありますからね。今回は2次元であると条件が決まってますので、高速に解くには2次元をメッシュに切って解くのが良いでしょう。これは、メッシュ内の点同士の連結とメッシュ間の連結を分けて考える方法になります。当然、距離の計算は劇的に少なくなります。
例えば、x、y座標、それぞれに対して、10区間に分けるとすると、100個のメッシュが出来ます。このメッシュ間の距離を求めて、どのメッシュを繋いでいけばよいかを求めます。また、これとは独立に、メッシュ内に複数の点が含まれる場合には、メッシュ内での点の結び方を求めます。これらを総合すれば解が得られます。
どうでしょうか。
No.2
- 回答日時:
点の数や、制限時間でアルゴリズムは決まってくるんじゃないかなあ?
GA(遺伝的アルゴリズム)は、大学時代隣の研究チームがやってましたが、処理中の経過を見るだけでも楽しかったです。
コストをかけられるなら、ここからここまでの処理をお前がやれと別PCに仕事を投げても良いし。このシステムを作るのも大変だ・・・。
コンピューター群が多ければ、仕事を投げる仕事も別PCに任せた方がよいです(笑)。場合によっては仕事の振り分けが間に合わず、ひまなPCが出てきます。
参考URL:http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E% …
No.1
- 回答日時:
こちらは「巡回セールスマン問題」と呼ばれる、アルゴリズムの計算速度などの比較にも使われるようなモデル問題です。
逆に「巡回セールスマン問題」の解法などとして情報収集すると、過去に先人達が築き上げた色んなアルゴリズムが見つかると思います。
割と新しい方法で、最適解の保障が無い方法ですと、遺伝的アルゴリズムとか。
--
> 全ての結び方をしらみつぶしに調べると
> (点の数)! 通りの総直線距離を計算しなければならず
> 点が増えるとかなり苦しいことになります・・・
この方法は基準になりますから、一度組んでみてどれくらい遅いのか?というのを実感するのも良いかも。
点の数を調整すれば、計算に100年かかるって事も無いですし。
ありがとうございます。
そういえば聞いた事があるような気がします。
手法の簡単な紹介がされたページはたくさん見つかるのですが、
具体的に細かなアルゴリズムの組み方まで示したページは
なかなか見つからないですね・・・
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 球面と接する直線の軌跡が表す領域 4 2023/07/30 12:37
- 数学 数学ベクトルに関しての質問 3 2022/05/25 23:21
- 数学 ベクトル方程式(ヘッセの標準形)についての質問 2 2022/04/23 18:00
- 数学 数学三 複素数平面 添付してある画像の問題において、「点Cは半直線AB上にある」という記述があります 1 2023/06/17 11:28
- 統計学 直線の傾き(回帰係数)から相関係数を計算できるのでしょうか? 2 2022/09/16 19:28
- その他(法律) 2車線以上であっても、歩行者は横断歩道がない道路を横断できますよね? 3 2022/04/19 15:58
- その他(IT・Webサービス) 2点の住所を入力して直線距離を算出する方法・サイト 1 2023/02/22 16:52
- 数学 『Cの微分.2』 3 2023/02/15 19:47
- 高校 数Ⅱの軌跡という単元について質問です。 問題の最後に、逆に、この~上の全ての点は条件を満たすとかく場 3 2023/03/21 16:38
- 政治 日本もラウンドアバウト交差点を増やすべきではないですか? 4 2023/06/26 23:27
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
Dijkstraて
-
C言語初心者の質問失礼いたしま...
-
画像から文字を認識してテキス...
-
[ EXCEL VBA ] 図形を読み込む...
-
期間重複チェックがわかりません
-
プログラミング能力とアルゴリ...
-
「FFTW」についての質問です。
-
C# 再帰よるスタックオーバー...
-
連立方程式を解く
-
タテヨコで数字の被らない二次...
-
アルゴリズムが全くわからない
-
アルゴリズム オーダー記法 定...
-
対話型遺伝的アルゴリズムにつ...
-
BCDについて
-
ランダム関数を作りたい。
-
Vba 実数および実数タイプの変...
-
0除算して、落ちるプログラムと...
-
VBAで仕様書は書きますか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
Dijkstraて
-
Stuck
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
三次元形状曲面の導出法
-
あいまい検索(文字列一致率)
-
Visual studio2019 C#で生まれ...
-
gooという検索エンジンの後にGo...
-
フリーセルの難易度について
-
CRC-CCITT16の算出法
-
経路探索について
-
C♯で電卓を作成しています。演...
-
理系の高校生です。大学で情報...
-
OpenCVのライセンスについて
-
偏りのある乱数のアルゴリズム
-
詰め将棋をとくのは、アルゴリ...
おすすめ情報