- ベストアンサー
複数の点を最短距離で全て繋ぐアルゴリズム
C++で以下のようなプログラムを書こうと思うのですが、 効率的なアルゴリズムが思い浮かびません。 よい方法をご存知の方がおりましたら教えてください。 ------------------------ xy平面上に複数の点があります。 それぞれの点の座標は全て分かっています。 今、原点から出発して全ての点を直線で結んでいくのですが このとき引く直線の長さの総計が最小になるような 結び方を見つけたいのです。 全ての結び方をしらみつぶしに調べると (点の数)! 通りの総直線距離を計算しなければならず 点が増えるとかなり苦しいことになります・・・
- tententen_april
- お礼率13% (47/338)
- C・C++・C#
- 回答数4
- ありがとう数1
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
> 具体的に細かなアルゴリズムの組み方まで示したページは > なかなか見つからないですね・・・ こちら、GAの本なんかに載っているような標準的な方法ですが、図表なんかが多くて解説がわかりやすいです。 参考文献・資料も一緒に見ると良いとおもいます。 アルゴリズム入門 : 第 5 章 知識情報処理入門 http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/ ＃MSのサイト内ってのが灯台下暗しというか…。
その他の回答 (3)
- goma_2000
- ベストアンサー率48% (62/129)
GA等のヒューリスティクスを使うにしろ、全ての点の距離は計算しなくてはなりません。これらのヒューリスティクスな手法は、点の組み合わせを求める時に使用するものです。点の数が多い場合には距離を求めるのが難しい場合もありますからね。 今回は２次元であると条件が決まってますので、高速に解くには２次元をメッシュに切って解くのが良いでしょう。これは、メッシュ内の点同士の連結とメッシュ間の連結を分けて考える方法になります。当然、距離の計算は劇的に少なくなります。 例えば、ｘ、ｙ座標、それぞれに対して、１０区間に分けるとすると、１００個のメッシュが出来ます。このメッシュ間の距離を求めて、どのメッシュを繋いでいけばよいかを求めます。また、これとは独立に、メッシュ内に複数の点が含まれる場合には、メッシュ内での点の結び方を求めます。これらを総合すれば解が得られます。 どうでしょうか。
- 2531kbps
- ベストアンサー率13% (183/1333)
点の数や、制限時間でアルゴリズムは決まってくるんじゃないかなあ？ GA（遺伝的アルゴリズム）は、大学時代隣の研究チームがやってましたが、処理中の経過を見るだけでも楽しかったです。 コストをかけられるなら、ここからここまでの処理をお前がやれと別PCに仕事を投げても良いし。このシステムを作るのも大変だ・・・。 コンピューター群が多ければ、仕事を投げる仕事も別PCに任せた方がよいです(笑)。場合によっては仕事の振り分けが間に合わず、ひまなPCが出てきます。
- neKo_deux
- ベストアンサー率44% (5541/12319)
こちらは「巡回セールスマン問題」と呼ばれる、アルゴリズムの計算速度などの比較にも使われるようなモデル問題です。 逆に「巡回セールスマン問題」の解法などとして情報収集すると、過去に先人達が築き上げた色んなアルゴリズムが見つかると思います。 割と新しい方法で、最適解の保障が無い方法ですと、遺伝的アルゴリズムとか。 -- > 全ての結び方をしらみつぶしに調べると > (点の数)! 通りの総直線距離を計算しなければならず > 点が増えるとかなり苦しいことになります・・・ この方法は基準になりますから、一度組んでみてどれくらい遅いのか？というのを実感するのも良いかも。 点の数を調整すれば、計算に100年かかるって事も無いですし。
関連するQ&A
- 原点が複数存在する座標系は可能ですか?
普通のxy軸を持った座標は二本の直線が交差しているかたちで原点がひとつだけありますが、いま円を描いて、この円に内接する形で星型を描くと二本の線分（？）が交差する点が１０個できますが、これは全て同じような原点の資格を持っているように思われます。このような複数の原点を持った座標を使っていろいろな関数のグラフを描くと全く違うものになりそうにも思うのですが、どうなのでしょう。
- ベストアンサー
- 数学・算数
- 空間図形なんですが・・・
xy平面上の点A（rcosA,rsinA）を、x軸となす角θ（0≦θ,A≦π/2，θ≦A/2）のxy平面上の直線を軸として回転させたとき、 （１）点Aが描く円の方程式。 （２）（１）の円がxz平面と交わる点Bの座標。 （３）原点と点Bを結ぶ直線OBがx軸となす角度。 どうやって解けばいいですか？教えてください。
- ベストアンサー
- 数学・算数
- 点Qから最短距離の点Piを効率的に求めたい
平面上にP1,P2,...,Pnが与えられています。 このとき、任意の点Ｑを与えると、Ｑからの距離の最短の点（等距離の点が複数あれば、そのうちの任意の１点）を返す関数（任意といった時点で数学的には関数でなくなっていますが）が欲しいのです。 単純に考えれば、forループで、全てのPiとの距離を求め、最短のPiを返せば良いのですが、点Ｑが移動する場合、直前のＱに対応するPiである可能性が高いので、もう少し賢いアルゴリズムがある気がします。しかし、具体的なアルゴリズムが思いつきませんので、お知恵をお貸しください。 プログラミングはＣを想定しています。
- ベストアンサー
- C・C++・C#
- n角形の重心を求めるアルゴリズム
平面2次元のn角形の頂点のデータがあります。n点の座標ですから(x,y)がn個並んでいます。そのような図形の図心（重心）の座標を計算するアルゴリズムがないでしょうか。最終的にはプログラムとして離散的な処理をするため、１％ぐらいの誤差は許容範囲です。n角形と言ってもせいぜいn=3,4,5,6程度です。 欲を言うと、３次元も考えており、平面に含まれることが分かっているn個の点（３次元空間内）を平面の２次元空間に変換して重心を求め、それを３次元空間に引き戻せば３次元での重心となります。そのためにも２次元での重心の座標を求めるアルゴリズムが必要なのです。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 座標平面上の距離の和の最小値
はじめまして、こんにちは。 質問なんですが、 原点をOとする座標平面上に点Aがある。点Pは直線y=1/2x+2の上を動く このとき （１）OP^2+PA^2を最小とする点Pの座標を求めよ。 （２）OP+PAを最小とする点Pの座標を求めよ。 という問題なんですが、（１）と（２）の問いの違いがわかりません。 （１）では、P(a,1/2a+2)とおいて、OP^2とPA^2それぞれの2点間の距離を使い求めるとういことは理解できますが、（２）の解答には「点Oに関してy=1/2x+2に対する対称な点をとる」と書かれています。これ以外に解答の仕方はないのでしょうか。
- 締切済み
- 数学・算数
- 空間座標 球面上の点と空間にある点の距離について
空間座標において 「『球面上の点と空間にある点P』との(最短)距離」は球面中心と点Pを結んだ距離と球面の半径と差で求めると思うのですが、感覚的にはわかる気がしますし、平面座標だと分かりますが、空間座標になると本当にそうなのかと思ってしまいます。式で証明することができるのでしょうか。 また、「『球面上の点と直線の点』との距離」や「『球面上の点と平面の点』との距離」も同じように球面の半径から直線の点もしくは平面の点に垂線を下ろして考えるのでしょうか。
- 締切済み
- 数学・算数
- 数学の問題がわかりません。
3次元空間における点Pはx,y,zの直交座標系で成分（1,1,1）を持つとしたとき、原点と点Pを通る直線をLとする。 (i)点Pを通り、直線Lと垂直な平面をQとするときのQとxy平面の交線の式を求めよ (ii)点Pを通り、直線Lと30度の角度をなす直線を直線L周りに回転させる。 このとき、直線とxy平面の軌跡は楕円を描く。この楕円の中心を求めよ。 という問題なのですが、どう解けばいいかがわかりません。 どのように導入をするのか、式をつかえばいいかがわからないので 教えて頂きたいです。 よろしくお願いします。
- 締切済み
- 数学・算数
- 整数の問題で、１２７ｘ－３７ｙ＝０とこの直線上にない格子点との距離を求める問題
整数問題から、ユークリッダ互徐法の問題で、 「ｘｙ平面上の直線１２７ｘ－３７ｙ＝０と、この直線上にない平面上の格子点(ｘ、ｙ座標とも整数の点)との距離の最小値を求めよ」という問題で、分からないので解答を見たところ、 格子点を(ａ、ｂ)[ａ、ｂは整数]とおいて、直線１２７ｘ－３７ｙ＝０との距離より |１２７ａ－３７ｂ|／√(１２７^2＋(－３７)^2)より、(ａ、ｂ)はこの直線上にないので、 １２７ａ－３７ｂ≠０なので、１２７ａ－３７ｂ＝１になることがあれば、距離の最小値となるので、 １／√(１２７^2＋(－３７)^2)＝１／√１７４９８ とあります。 なぜ、１２７ａ－３７ｂ＝１が最小値となるのでしょうか？ 右辺の値が１であることの根拠が分かりません。 １２７と３７が互いに素、即ち１２７と３７の最大公約数が１のとき、 １２７ａ－３７ｂ＝１となる整数ａ、ｂは右辺＝１のときしか、 存在しないという意味でしょうか？ どうか、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 2次元平面における2点間の平均距離
xy座標平面上の(0,0),(a,0),(0,b),(a,b)の4点からなる平面AB． その平面ABに含まれる2点を任意に選んだ時 その2点間の距離をa,bを使って表したいです． お願いします．
- 締切済み
- 数学・算数
- ２点間の距離の公式と点と直線の公式の関係
xy平面上に放物線y=x^2と点P(0,b)を考える。ただしb＞0とする。点X(t,t^2)がこの放物線上を動くとき線分BXの長さの最小値を求めよ。」という問題なのですが、解答では、２点間の距離の公式から立式して解いているのですが、私は、点X(t,t^2)における接線を求めて、その直線と点において、点と直線の公式を使って求めようとしましたが、どこが行けないのでしょうか、確かに回りくどいですが、まちがってはいませんよね。点と直線の公式では、 BX^2={(t^2 + b)^2} / 4t^2 + 1 になってしまって、２点間の距離の公式の結果と違ってしまいました。よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。 そういえば聞いた事があるような気がします。 手法の簡単な紹介がされたページはたくさん見つかるのですが、 具体的に細かなアルゴリズムの組み方まで示したページは なかなか見つからないですね・・・