« 宇宙船で小惑星帯を通り抜けるとき、どのくらい小惑星に接近するの? | Main | クワッドコアの威力 »

October 20, 2010

小惑星の数が増えると、どう宇宙船に再接近する距離が縮まるか、計算時間が増えるか

前回のコンテンツで、E223「小惑星の数の平方根の逆数に比例している。計算時間は、小惑星の数の1.5乗と比例」と書いたが、何故、そのような関係になるかを考察した。

ある瞬間における宇宙船と小惑星との距離は、三次元的ものである。ところが、宇宙船が小惑星帯を通り抜けるような旅程全体での最短距離は、概念的には、イラストに示したように、速度ベクトルに垂直な平面への垂線との交点との距離になる。つまり、小惑星との距離は二次元的な直線距離になる。

小惑星の個数と各小惑星が平面で占有できる面積は反比例の関係になり、従って最短距離は小惑星の個数の平方根と比例することになのだ。

計算時間の話だが、私のアルゴリズムでは宇宙船の出発から到着まで一定時間間隔で計算しているのではない。最短にある小惑星までの近い時は細かい間隔で、遠い時は荒い間隔で計算している。具体的には、どんな事があっても最短距離の小惑星が宇宙船にぶつかって通り過ぎることの無いように、小惑星の速度の最大値(そこの太陽からの距離での第三宇宙速度)と宇宙船の速度との単純和速度で最短距離の小惑星までの距離を割った時間を計算時間の間隔としている。
つまり、計算回数は小惑星の平方根と比例するのだ。
また、一回の計算時間は単純に小惑星の数に比例する。

計算回数は小惑星の平方根と比例し、一回の計算時間は単純に小惑星の数に比例するわけだから、全体の計算時間は小惑星の数の1.5乗に比例することになる。

ここまでに、実は私が断りもなしに大胆な仮定をおいていることを、聡明な読者は気づいているかも知れない。その一つが「小惑星の動きに比較して宇宙船の相対的な速度が大きいこと」、もう一つが「宇宙船の速度ベクトルが直線的であること」である。

実は、これら二つの仮定は、少なくとも前回のコンテンツで示した地球〜木星のホーマン軌道においては、成立しているようである。と言うのも、前回のコンテンツの最後に示したグラフのように、小惑星の個数の平方根と最短距離は比例しているし、小惑星の個数の1.5乗と計算時間が比例しているからである。どうやら、宇宙船の速度ベクトルは、各時点時点でのベクトルを直線で近似しても良いようだ。

しかし、小惑星帯の中を、小惑星と同じ速度で周回している宇宙船だと、こうならないだろう。私の予想では、最短距離は小惑星の個数の立方根と比例し、計算時間は小惑星の数の1.33乗に比例すると思うのだが、まだ試していない。

|

« 宇宙船で小惑星帯を通り抜けるとき、どのくらい小惑星に接近するの? | Main | クワッドコアの威力 »

Comments

気になったので、コメントを。

計算量が n^1.5 ということは、例えば 100 個のグループに分けて 100 回計算すれば、一つのグループは 1/1000 の時間で終わるので、全体でも 1/10 の時間で終わることになります。

原理的には、 n 個のグループにわける、つまり、小惑星 1 個毎にもっとも近付く距離を計算すると、小惑星の数に比例する時間で終わります。

Posted by: まきの | October 21, 2010 02:55 PM

まきのさん、実は、このコンテンツその物が、読者への挑戦状になっていたのです。
何が挑戦なのかさえ隠したままですので、挑戦状であることすら、ほとんどの人が気付かなかったと思います。
次のブログ更新(予定では土曜日)までに、その点を指摘する人が現れるか否か楽しみにしていました。

ずばり、正解です。
次回コンテンツ更新時にもう少し詳しい説明を書きます。

ところで、すいませんが、どちらの「牧野さん」ですか?
実は知り合いに「牧野さん」が3人居るのですが、その内、二人は、このような聡明なコメントをする可能性があるので、どちらの牧野さんか迷っています。

Posted by: 野田篤司 | October 21, 2010 09:53 PM

座標でふるい分けしてって話は前からツッコミ入れてたつもりだったのですが…条件がはっきりしてなかったのであまり強く言ってなかったと思いますが。

時間経過による移動も考慮に入れていたのですね。普通に物理シミュレーションの問題として時間の刻み幅も問題になってくるでしょう。「パチンコゲームを作ったら玉が釘を飛び越した」みたいな。

ODE(Open Dynamics Engineだったかな?)などの衝突判定の入った物理シミュレータにデータ変換してつっこむと良いかもしれません。

Posted by: 2sure781 | October 21, 2010 10:34 PM

「座標でふるい分け」と言うのを、完全に理解しているかは不安ですが、今のアルゴリズムでも座標によるソートを行ってから計算してますので、既にある程度考慮に入っています。
現状、私の最終結論は、結局は「まきのさん」に一致しています。

Posted by: 野田篤司 | October 21, 2010 10:40 PM

あ、GRAPE のほうです。HPL ベンチマーク実行中で、呆然と待っているだけだったりするのでついつい Web 巡回したり、、、

Posted by: まきの | October 22, 2010 12:57 AM

まきのさん、そうでしたか。
実は私が同じ結論に達するのに数日を要しているのです。まきのさんがブログ更新からコメント書き込みまで4時間程度で、その時間以内に結論を得ているので、正直「やられたな」と思っていたところです。
さすがに多数演算の専門家ですね。アッという間に正解に達するのには脱帽しました。

Posted by: 野田篤司 | October 22, 2010 06:31 AM

Post a comment



(Not displayed with comment.)


Comments are moderated, and will not appear on this weblog until the author has approved them.



TrackBack


Listed below are links to weblogs that reference 小惑星の数が増えると、どう宇宙船に再接近する距離が縮まるか、計算時間が増えるか:

« 宇宙船で小惑星帯を通り抜けるとき、どのくらい小惑星に接近するの? | Main | クワッドコアの威力 »