8

(これはまさに私が抱えている問題ではありませんが、同形であり、この説明が他の人にとって最も理解しやすいと思います。)

n次元空間に一連の点があるとします。たとえば、3 次元を使用すると、次のようになります。

A : [1,2,3]
B : [4,5,6]
C : [7,8,9]

この空間で可能な動きを表す一連のベクトルもあります。

V1 : [+1,0,-1]
V2 : [+2,0,0]

次に、点destが与えられた場合、最も効率的な方法で dest に移動する開始点pと一連のベクトル移動を見つける必要があります。効率は「最小の移動数」として定義され、必ずしも「最小の直線距離」ではありません。移動セットがより少ない移動でそこに到達できるようなものである場合、他の候補よりもdestから離れたpを選択することは許容されます。移動中のベクトルは、使用可能なベクトルの厳密なサブセットでなければなりません。入力セットに複数回出現しない限り、同じベクトルを複数回使用することはできません。

入力には ~100 個の開始点とおそらく ~10 個のベクトルが含まれており、次元数は ~20 です。開始点と利用可能なベクトルは、アプリの存続期間中固定されますが、非常に多くの異なる目的地へのパスを見つけます。メモリではなく速度を最適化したい。アルゴリズムが失敗することは許容されます ( destへの可能なパスが見つからないため)。

承認されたソリューションで更新

以下で「承認済み」とマークされているものと非常によく似た解決策を採用しました。すべてのポイントとベクトルを繰り返し処理し、到達可能なすべてのポイントのリストとそれらに到達するためのルートを作成します。このリストを < dest , p+vectors >のハッシュに変換し、目的地ごとに最短のベクトル セットを選択します。(ハッシュ サイズの最適化も少しありますが、ここでは関係ありません。) 後続のdestルックアップは一定の時間で発生します。

4

6 に答える 6

6

実際には、約10個のベクトルがあることを考慮すると、特定の宛先ポイントに対して、ベクトルのサブセットから1024個の「ターゲット」のみを計算できます。たとえば、到達可能なすべてのスペースで、そこに到達する一連の動きに関する情報を使用できます。これは、コンテキストに応じて「遅い」または「速い」場合があります（GPUなどの並列コンピューティングデバイスに実装されている場合は、途方もなく高速です）。

そこに到達するすべてのセットがあると、パスをはるかに迅速に計算できます。次に、クエリまたはそれ以降のサブセットから選択して、最も少ない移動で目的地に到達するポイントを選択できます。

（Strilancに感謝します）

于 2010-01-21T19:05:30.147 に答える
5

A *（別名Aスター）パスファインディングアルゴリズムの一般化されたアプリケーションを作成できると思います。N番目のスペースでそれができない理由はありません。各移動のコストを説明できれば、最適なパスが保証されます。

http://en.wikipedia.org/wiki/A*_search_algorithm

于 2010-01-21T19:03:42.380 に答える
5

したがって、サブセットの合計が特定の値になるように、ベクトルのセットのサブセットを検索する必要があります。1次元では、これはサブセット和問題と呼ばれ、 NP完全です。

幸いなことに、ベクトルは10個までしかないため、問題のサイズは実際には非常に小さく、扱いやすくなっています。まず、開始点ごとに2 ^ 10の移動の組み合わせをすべて試し、最適な組み合わせを選択します。次に、そこから簡単な最適化を探します。

うまくいくかもしれないいくつかの簡単な最適化：

  • 正しい方向を向いているベクトルを含むサブセットの検索を優先します。
  • ミートインザミドル。ハッシュテーブルを使用して、移動セットの前半のサブセットを使用して到達可能なすべてのポイントを格納し、移動セットの後半を使用して最後からヒットできるかどうかを確認します。
  • 後方に移動します。エンドポイントは1つしかないため、そこから到達可能なすべての開始点をハッシュしてから、考えられるすべての開始点と照合します。
  • 並行性
于 2010-01-21T19:07:05.743 に答える
2

開始点と固定されたベクトルのセットがある場合、到達可能なすべての目的地のリストを計算してから、特定の目的地を検索できますか？

于 2010-01-21T19:00:25.740 に答える
1

Kornelが述べているように、到達可能な宛先は最大2 ^ 10=1024です。したがって、単純な再帰的生成によって、到達可能なすべての宛先を2 ^ N時間（Nはベクトルの数）で生成できます。もちろん、これは十分に高速になります。しかし、あなたがそれを伸ばしたいと思ったとしましょう。

ミートインザミドルソリューションを使用して、O（2 ^（N / 2 + 1））時間に最適化できます。ベクトルセットを2つのサブセットに分割し、各サブセットの到達可能なすべての宛先を個別に生成します。次に、到達可能な目的地の1つのセットを反復処理し、場所ごとに、その場所とターゲットの目的地の違いを見つけます。その差ベクトルが到達可能な目的地の他のセットにある場合、解決策があります。2つを組み合わせると完了です。ここでの難しさは、他のセットに必要なベクトルがあるかどうかを効率的にクエリすることです。これは、ハッシュテーブルを使用してO（1）時間で実行できます。

これは、サブセットあたりO（2 ^（N / 2））時間であり、2つのサブセットを掛けるとO（2 ^（N / 2 + 1））になります。2つを結合するには、O（2 ^（N / 2））時間です。つまり、全体としてO（2 ^（N / 2 + 1））の時間が得られます。

于 2010-01-21T20:37:18.393 に答える
0
  1. 最初から始めます。
  2. しばらくしてください
  3. 目的地までの距離を取得します
  4. 考えられるすべての動きをテストし、1回の動きで目的地に最も近いものを選びます。
  5. 終わります

これは目的地の周りで振動するかもしれませんが、それはあなたを近づけるでしょう。

于 2010-01-21T19:05:04.993 に答える