この時、点A群の中から任意に指定された地点に最も近い地点を求めるにはどのような方法が最も効率的か教えてください(数学的概念を用いて説明される場合は数学IIBレベルを履修した程度の人にもわかるように説明してください)
なお、提示した方法を実現するプログラムコード、もしくはそれが書かれたURLを示していただければなお助かります。
No.3
656
53
50pt
点がある偏りを示す（たとえばＡ群の点が、その存在範囲の周縁部分に偏っているとか、あるいは存在範囲の全体が帯状である、など）であれば、全数計算する他無いと思いますが、その場合は『平面上の二点間の距離』の公式に基づき『（始点A(x1,y1)から終点B(x2,y2)間の距離ABは）AB＝√(x2-x1)^2+(y2-y1)^2』で数値を出せば良いのでは。遅くても、シンプルな操作で常に100%正確な結果が必要なら、これで。
で、点が偏っていない場合、効率化を考えるなら単純に座標で絞り込みをかけるのはどうですか？
まずＡ群に属する全ての点は、緯度経度によって座標化されていると考えて良いですね。で、とりあえず点Ａ群がある場所を100×100の正方形に入れてみると、（つまり存在範囲を仮想的に10000に分割すると）5000個の点が理想的にばらけている場合、仮想の面積１に対して点がある確率は１／２と考えられ、実用を考えれば面積が１０あれば９９％以上の確率でその中に一つは点があることを期待出来ます。ここでたとえば半径２の円を想定すると、面積は１２を越えます。そしてその円は当然ながら４×４の正方形の中にすっぽり収まりますね。つまり100分割した場合１単位がいくつになるか計算して、その２倍の数値をｘ軸、ｙ軸方向に＋－で延長した範囲内の正方形内を調べれば実用上は充分ということです（半径２の円内に点がない確率は、約4000分の１）。
従って、Ａ群に属する点が理想的にばらけていると期待出来るなら、点Ａ群（Ａ0～Ａ5000）の存在する範囲を100×100に割って、点Ｂを中心にした半径２の円が最低スッポリと入る正方形…すなわち点Ｂの座標からＸ，Ｙともにその前後２程度の差の範囲内にある点をあらかじめ探し、その後範囲内のいくつかの点Ａｎと任意の点Ｂの距離をざっと計算させ、その結果を出力すれば良いのではないかと思います。実際にはＡ群の点の存在場所に偏りがあるでしょうし、円と正方形の形のズレからそのパラメータを自由に指定出来るようにプログラムした方がよいでしょうけれども。
具体的には
・変数定義
・点Ｂの座標を入力
・パラメータＣを入力（１から５まで。デフォルト値は２とする。１だと計算が速いが、見つからなかったり不正確である可能性も考慮する必要がある。）
・Ａ群データから点ＢのＸ座標の前後Ｃの値（×１単位）の範囲のデータを抽出（Ｄ群）
・Ｄ群データから点ＢのＹ座標の前後Ｃの値（×１単位）の範囲のデータを抽出（Ｅ群）
・Ｅ群が＝φ（データがない）ならばパラメータ入力（３行目）に戻る。あれば次へ。
--------------------------------------------------------------
・Ｅ群の全データに対して値ｅ√(x2-x1)^2+(y2-y1)^2を計算
・Ｅ群を値ｅ基準で並べ替え、先頭（最小）のデータＡｎを返す。
・Ａｎを結果として表示し、Ａｎの値ｅを併せて表示
・終了
みたいな流れで処理すれば、それなりに効率化できると思います。
あるいは、少し複雑になりますが、パラメータ入力を省略しかつ100%正確な値を自動で出すなら、パラメータを０．５あたりから自動でスタートしてＡｎを探すようにし、見つかればそのe値（≠０）を求め、次にその際のパラメータを√２倍して結果を求め、それでもｅ値（≠０）が変わらなければそれを最終結果として出力、変わった場合は変わった後の方の値を最終結果として出力、という風にすればよいと思います。
（理由は、上の方法だとｅ値を求める範囲が円でなく正方形なので、その正方形（α）に外接する円（β）の中に正方形（α）の端よりも中心に近い点Ａｎが存在する可能性を否定できないからです。それを確認するためにその円（β）にさらに外接する正方形（γ）を想定し、上の手順を繰り返すわけです。この場合、新たな正方形γの一辺は最初の正方形αの辺の√２倍の長さを持つので（説明は略します）パラメータを√２倍してやればよいということになります。その結果新たにより近い点が見つかればそちらの方が正解と特定できます。）
No.1
49264
50pt
任意に指定された点から、すべての点（点Ａ群）に対する距離を球面三角法の余弦定理を利用して計算し結果の中からもっとも差分（距離）が小さいものを選択する。
球面三角法余弦定理の実装は、以下に。（説明は非ユークリッド幾何学の世界なので数ⅡＢでは無理）
「小さいものを選択」は単純にソートすればいいのでそのアルゴリズムについては省略。
ようは、全数計算が必要、ということです。
#include <math.h>
#define deg2rad(x) (2.0*M_PI*x/360.0)
#define XXXX (40064.5)
double distance(x1,y1,x2,y2)
double x1,y1,x2,y2;
{
return XXXX/2/M_PI*acos(sin(deg2rad(x1))*sin(deg2rad(x2))+cos(deg2rad(x1))*cos(deg2rad(x2))*cos(deg2rad(y1)-deg2rad(y2)));
}
参考リンク先も含め、理解できるところまで読んでみました。
同じ質問をされている方がいたのですね(http://q.hatena.ne.jp/1224295014)
2点間の大圏距離を求める方法は公式として掴んではいたのですが、
やはり全数計算が必要なのですか。
今回はquestion:1224295014のように方法そのものよりもサーバ上で動作させるにあたって、いかに負荷を減らしてレスポンスを早めるかかという点に着目しています。
ですが、試しに球面三角法で大圏距離を求める方法をPHPとして実装しているページがありましたので、こちらを参考に全数計算してみたところ(緯度・経度は乱数生成)
およそ0.05秒程度で実行できました。
http://www.yamareco.com/weblog/archives/2007/02/gps2.html
全数計算は負荷が高いかと思っていましたが、案外実用的で安心しました。
緯度・経度を引き算したり、メッシュで分けたりして候補を絞り込むことも
考えていましたが、テスト段階ではまだそこまですることもなさそうです。
No.2
254
10pt
なぜかと聞かれると答えられませんが、それは、最短シュタイナー問題の解ではないでしょうか？
『最短シュタイナー問題』解答
読みました、でも今回求めているものとは違うのではないかと。
仰っている最短シュタイナー問題の解は「正n角形の中に点を取り、各点と各頂点の距離の総和が最短になるような点に対する解」であると理解しましたが、それと今回の問いとはどうもかみ合いません。
私の理解不足であるようでしたら、コメントでお返事をください。
No.3
65653
ここでベストアンサー
50pt
点がある偏りを示す（たとえばＡ群の点が、その存在範囲の周縁部分に偏っているとか、あるいは存在範囲の全体が帯状である、など）であれば、全数計算する他無いと思いますが、その場合は『平面上の二点間の距離』の公式に基づき『（始点A(x1,y1)から終点B(x2,y2)間の距離ABは）AB＝√(x2-x1)^2+(y2-y1)^2』で数値を出せば良いのでは。遅くても、シンプルな操作で常に100%正確な結果が必要なら、これで。
で、点が偏っていない場合、効率化を考えるなら単純に座標で絞り込みをかけるのはどうですか？
まずＡ群に属する全ての点は、緯度経度によって座標化されていると考えて良いですね。で、とりあえず点Ａ群がある場所を100×100の正方形に入れてみると、（つまり存在範囲を仮想的に10000に分割すると）5000個の点が理想的にばらけている場合、仮想の面積１に対して点がある確率は１／２と考えられ、実用を考えれば面積が１０あれば９９％以上の確率でその中に一つは点があることを期待出来ます。ここでたとえば半径２の円を想定すると、面積は１２を越えます。そしてその円は当然ながら４×４の正方形の中にすっぽり収まりますね。つまり100分割した場合１単位がいくつになるか計算して、その２倍の数値をｘ軸、ｙ軸方向に＋－で延長した範囲内の正方形内を調べれば実用上は充分ということです（半径２の円内に点がない確率は、約4000分の１）。
従って、Ａ群に属する点が理想的にばらけていると期待出来るなら、点Ａ群（Ａ0～Ａ5000）の存在する範囲を100×100に割って、点Ｂを中心にした半径２の円が最低スッポリと入る正方形…すなわち点Ｂの座標からＸ，Ｙともにその前後２程度の差の範囲内にある点をあらかじめ探し、その後範囲内のいくつかの点Ａｎと任意の点Ｂの距離をざっと計算させ、その結果を出力すれば良いのではないかと思います。実際にはＡ群の点の存在場所に偏りがあるでしょうし、円と正方形の形のズレからそのパラメータを自由に指定出来るようにプログラムした方がよいでしょうけれども。
具体的には
・変数定義
・点Ｂの座標を入力
・パラメータＣを入力（１から５まで。デフォルト値は２とする。１だと計算が速いが、見つからなかったり不正確である可能性も考慮する必要がある。）
・Ａ群データから点ＢのＸ座標の前後Ｃの値（×１単位）の範囲のデータを抽出（Ｄ群）
・Ｄ群データから点ＢのＹ座標の前後Ｃの値（×１単位）の範囲のデータを抽出（Ｅ群）
・Ｅ群が＝φ（データがない）ならばパラメータ入力（３行目）に戻る。あれば次へ。
--------------------------------------------------------------
・Ｅ群の全データに対して値ｅ√(x2-x1)^2+(y2-y1)^2を計算
・Ｅ群を値ｅ基準で並べ替え、先頭（最小）のデータＡｎを返す。
・Ａｎを結果として表示し、Ａｎの値ｅを併せて表示
・終了
みたいな流れで処理すれば、それなりに効率化できると思います。
あるいは、少し複雑になりますが、パラメータ入力を省略しかつ100%正確な値を自動で出すなら、パラメータを０．５あたりから自動でスタートしてＡｎを探すようにし、見つかればそのe値（≠０）を求め、次にその際のパラメータを√２倍して結果を求め、それでもｅ値（≠０）が変わらなければそれを最終結果として出力、変わった場合は変わった後の方の値を最終結果として出力、という風にすればよいと思います。
（理由は、上の方法だとｅ値を求める範囲が円でなく正方形なので、その正方形（α）に外接する円（β）の中に正方形（α）の端よりも中心に近い点Ａｎが存在する可能性を否定できないからです。それを確認するためにその円（β）にさらに外接する正方形（γ）を想定し、上の手順を繰り返すわけです。この場合、新たな正方形γの一辺は最初の正方形αの辺の√２倍の長さを持つので（説明は略します）パラメータを√２倍してやればよいということになります。その結果新たにより近い点が見つかればそちらの方が正解と特定できます。）
実に論理的に丁寧な回答で感服いたしました。おかげさまで非常にわかりやすかったです。
全区域を10000分割し、A群の各点に0-10000の区域番号をつけた上で、任意の点の近似区域を求めることで候補を絞り込むというわけですか。なるほど、確かにこれだとほとんど計算を行わずにすみますね。
なんとなく考えてはいましたが、ここまで詳しく書いていただければ実装まで持っていけそうです。現在の所、球面三角法による全数計算でもなんとかなりそうですが（ただ、質問の意図からするとこの絞り込みが最も的確かと思います）、この場合は点A群の数に比例して処理時間が延びてしまうので、スケーラビリティを考えて、この解決策を採ることも考えておこうと思います。
zzz_1980
2008/10/19 22:43:09
15
14
jo_30
leva
yamadakouzi
murakami_tak
2
1
1
実に論理的に丁寧な回答で感服いたしました。おかげさまで非常にわかりやすかったです。
全区域を10000分割し、A群の各点に0-10000の区域番号をつけた上で、任意の点の近似区域を求めることで候補を絞り込むというわけですか。なるほど、確かにこれだとほとんど計算を行わずにすみますね。
なんとなく考えてはいましたが、ここまで詳しく書いていただければ実装まで持っていけそうです。現在の所、球面三角法による全数計算でもなんとかなりそうですが（ただ、質問の意図からするとこの絞り込みが最も的確かと思います）、この場合は点A群の数に比例して処理時間が延びてしまうので、スケーラビリティを考えて、この解決策を採ることも考えておこうと思います。