14

アルゴリズムの 1 つを劇的に最適化したいのですが、できる限り最善の方法で説明しようと思います。

件名

t = 0の時点で 2D ユークリッド システムにいます。このシステムには、 O1とO2の 2 つのオブジェクトがあります。

O1とO2は、それぞれ点PAとPCに位置しています。

O1は点PBの方向に一定の既知の速度で移動します。オブジェクトは PB に到達すると停止します。

O2は一定の既知の速度で移動でき、O1とは異なるか、またはどの方向にも移動できません。時間 0 では、O2 には方向がありません。そのための方向を見つける必要があります。

既知のパラメータ:

  • O1 : 位置、方向、速度
  • O2 : 位置、速度

これがシステムの小さな図です。

システム図

点PIと時間tiを見つけたいと思いますPosition of O1 at the time ti = Position of O2 at the time ti = PI。次に、オブジェクト O2 をポイント PI に移動させて、O2 の方向を取得します。

O2 の方向 (ポイント PI) が選択され、オブジェクト O1 と O2 の両方が移動している場合、オブジェクトは停止したり、互いに待機したりすることはありません。

この場合、結果は次のようになります (PI はこの図では D と示されています)。 最適交差点

アルゴリズム

このjsfiddleで、JS で記述された動作中のアルゴリズムを見つけることができます。これは、問題を理解するための優れた方法でもあります。

現時点では、機能するシンプルなアルゴリズムを使用していますが、多くの操作が必要なため、最適な交差点時間を取得し、その後交差点の位置を取得します。

この時間を取得するために、O1 の位置を今すぐ確認し、O2 がこの位置に移動できるかどうかを確認します。O2 がオブジェクトに間に合わなかった場合、時間を 150% 増やしますが、O2 がその時点で O1-B ラインを横切ることができた場合、時間を 50% 減らします。

最終的に、多くの概算の後、両方のオブジェクトが出会う完璧な時間を見つけます。

疑似コード

function getOptimalIntersectionTime time
   if distance between O1 and O2 at the time `time` < 1
       return time
   else if O2 could not reach the object O1 at the time `time`
       return getOptimalIntersectionTime time * 1.5
   else
       return getOptimalIntersectionTime time * 0.5

なぜ私は心配ですか？

私のアルゴリズムは機能しますが、場合によっては (jsFiddle の "Reverse Case" など)、最適な点を見つけるために大量の計算が必要になります。

この jsFiddle では、位置 (-1000 ～ 1000) と速度 (1 ～ 200) に小さな値を使用していますが、このアルゴリズムは数値が大きいほど劇的に遅くなります。

時期尚早の最適化が悪い考えであることは知っていますが、私はプロジェクト (データベースの挿入/選択とデータ分析で構成され、何度も呼び出されるこのアルゴリズムを含む) の最後にあり、このアルゴリズムはプロジェクトの最大 80% を占めています場合によっては、プロジェクト システム リソースを使用して、改善によってシステムの安定性と応答性が実際に向上する可能性があります。

4

4 に答える 4

9

一般性を失うことなく、O2 を (0,0) に配置します。

O1 の位置と速度のベクトル、sO2の速度、t を傍受する時間とします。次に、次のようになります。vv2

|s + v * t| = t * v2

距離の定義により:

(sx + vx * t) ^ 2 + (sy + vy * t) ^ 2 = (t * v2) ^ 2

これを乗算して項を並べ替えると、次のようになります。

  sx^ 2 + 2 * sx * vx * t + vx^2 * t^2
+ sy^ 2 + 2 * sy * vy * t + vy^2 * t^2
-                           v2^2 * t^2
= 0

すなわち

  sx^2 + sy^2 + (2 * sx * vx + 2 * sy * vy) * t + (vx^2 + vy^2 - v2^2) * t^2 = 0
  \---   ---/   \------------   ----------/       \--------   ------/
      \ /                    \ /                           \ /
       c                      b                             a

ご覧のとおり、これは t の二次方程式です。2 次式を単純に適用して、 の 2 つの可能な値を見つけることができますt(方程式に解がない場合、それは切片が不可能なためです)。おそらく、将来の最も早いインターセプト、つまり > 0 の小さい t を使用することをお勧めします。

を計算したらt、交点を見つけ、そこから交点の方向を簡単に見つけることができます。

要約すると、この問題は一定時間で解決でき、反復は必要ありません。

于 2012-04-28T00:14:54.407 に答える
1

あなたは問題を考えすぎているようです。単純なジオメトリである必要があります。

最も近い点をどのように定義するかという問題はさておき、目的の点が と の中間にある状況を解いてみましょPAうPB。

サイクル全体の期間を想定する必要があります。それを と呼びましょうT。

PI = (PB - PA) / 2;  // simplified
TI = T / 2;          // simplified

[x 座標と y 座標のすべての式を別々に分解する]。

点 (PC) と線 (PA -> PB) の最も近い交点を決定するための比較的単純な式がありますが、その線が無限に長くない場合、その定義方法は複雑です。

次に、次のものが必要です。

V1 = (PB - PA) / T;  // O1's velocity
V2 = (PI - PC) / T;  // O2's velocity

これらの最後の 2 行は、以前の仮定に依存していません。交点がわかっている場合、速度は単に移動した距離をかかった時間で割ったものです。

したがって、V2 に追加の制約を課さない限り、常に解があり、それはいくつかの簡単な数学演算で計算されます。

于 2012-04-27T21:40:03.703 に答える
1

更新: @Meriton の後の回答は、私の回答よりも優れています。最初に試してみることをお勧めします。

お気づきのように、3 つの未知数 vx2、vy2、および t に 3 つの連立方程式があります。それぞれ 02 の x 速度と y 速度、および時間です。残念ながら、方程式はすべて線形ではありません。

x1o + vx1*t == x2o + vx2*t
y1o + vy1*t == y2o + vy2*t
vx2*vx2 + vy2*vy2 == vy*vy

(ここで、x1o、y1o、x2o、y2o は初期位置の座標です。)

問題を線形化する方法があるとしても、私にはわかりません。ただし、 GPS が衛星信号から自分の位置を計算するために使用するのと同じニュートン ラフソン法によって、反復的かつ迅速に解くことができます。もちろん、詳細を入力してこれを実装するには、いくつかの作業が必要です。

更新: @Alnitak が問題をかなりきれいに線形化した可能性がある と思います。したがって、彼のアプローチと私のアプローチの組み合わせが成功する可能性があります。(@Altinak のT.

于 2012-04-27T21:41:19.347 に答える
0

速度が固定されているため、これは平行航行のアイデアを使用して解決できるはずです。このように考えてください。時間 0 では、O1 と O2 の間に線 (LOS、または見通し線) があります。O2 が最適な交差パスをたどる場合、時間 1 で、O1 と O2 の間の線は時間 0 LOS と平行になります。O2 の速度があるので、時間 0 と時間 1 の間で移動する距離を計算でき、そこから時間 1 の LOS と交差する場所を計算できます。O2 の元の位置の周りに、その時間間隔で移動する距離に等しい半径の円を描くことを考えてみてください。その円と 2 番目の LOS との交点に解が含まれます。交差がなければ、解はありません。このオンライン ブックの冒頭には、概念を示す図と式があります。

http://www.crcnetbase.com/doi/abs/10.1201/9781420062281.ch2

この問題には実際のアプリケーションがあり、このソリューションが話題になっている場合もあります。たとえば、潜水艦はこれを使用して、ターゲットに接近するときにターゲットへの LOS 方位を一定に保つことにより、ターゲットとの迎撃コースを計画および維持できます。

編集：

ここに画像の説明を入力

この図は、私が話していることを示しています。これは三角法を使用して解決できますが、ターゲット O1 が直接ミサイル O2 に近づいたり遠ざかったりする特殊なケース (これは自明に解決できます) を除きます。

上の図では、任意の短い時間を取ることができます。その時間 t1 の間に、O1 は距離 b を移動し、O2 は距離 f を移動します。時刻 t0 における O1 と O2 の間の線は、時刻 t1 における O1 と O2 の間の線と平行です。O1 と O2 の初期位置が与えられているので、距離 d がわかり、O1 の方向が与えられているので、角度 A を簡単に計算できます。

So given A, b, f, and d, using the law of Cosines,
a = sqrroot(c^2 + b^2 - (2cb * cos(A)))
and
B = arccos((a^2 + c^2 - b^2)/2ac)
Using the law of Sines
E = arcsin((a * sin(B))/f)  or the ambiguous value of 180 - that value
and with that
BC = 180 - E   (because C = 180 - B - E so C+B = 180 - E

BC を使用すると解が得られ、O1 と O2 の初期位置と交点の三角形の他の側面も同様に計算できます。高校のトリグを使用してから何年も経っているので、見落としている単純化されたものがあるかもしれませんが、これで最初に説明したソリューションアプローチが説明されていることを願っています.

于 2012-04-27T23:08:21.213 に答える