algorithm - 近接検出の近接点

Question

3D の 3 次多項式の大規模なセットがあります。

マトリックス形式で

Pn = [1,t,t ² ,t ⁴ ]*[An]

[Pn]と[An]は1xNと4xN行列です

各関数には重み Wn があります。私は、いくつかのために、そのような最初の場所n, m, Tを見つけたいですt0tt>t0

(Wn*Wm) * |Pn-Pm| ^-2 > T

O(n ² ) の「すべてを試す」アプローチは別として、どこから始めればよいかさえわかりません。さらに言えば、既知の n & m であっても、これに答える方法がわかりません。

何か案は

編集：

• セットサイズは10～1000程度
• 重みは〜対数的に分布しています（非常に少数の大きなもの、多くの小さなもの）
• このテストは n-ボディ シミュレータの内部ループにあるため、何度も実行されます。
• 1 つのパスが変更された後に新しい答えを見つけるのにうまく (償却されて) いるバージョンは、良いことです。

Answer 1

これが分析手段で解けるかどうかわからないので、空間を検索してその基準を満たす t を見つけようとする方法はたくさんあります。

遺伝的アルゴリズム、シミュレーテッド アニーリング、その他の最適化アルゴリズムが思い浮かびます。

Answer 2

ポットに種をまく:

• 何らかの形式の「クローズ ペア ファインダー」アルゴリズムを使用して、t0 およびその他の時点でそれらのペアをヒープにシードします。
• 見つかった最も近いペアを引き出します
• これまでの最高の状態よりも十分に近い場合は、そのままにしておきます
• それらが近いか離れているかを調べる
• 現在のペアと次のペアの差を「近い」側に分割し、それをヒープに追加します。

考え？

Answer 3

Nの大きさは？徹底的な検索は可能ですか？

numpyまたはscipyディスカッション ボードで質問して、Python のスキルを磨きます。おそらく、これを最小化の問題に変えて、fmin やBFGS、またはその他の有界準ニュートン アルゴリズムを使用して、合理的な最小値を見つけることができるでしょう。おそらく、t と T の差を最小限に抑えます。行列に何か変なものがない限り、検索空間は少なくとも連続しているように見えます。

タイトルで最も接近したポイントについて言及しているので、numpy ボードでこの投稿をチェックしてください。