8


0

特定のポイントに到達するための最も効率的な動きを見つけるアルゴリズム

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

_n_次元空間に点のセットがあると仮定します。 たとえば、3次元を使用します。

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

また、この空間で起こりうる動きを記述する一連のベクトルもあります。

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

ここで、ポイント_dest_が与えられた場合、出発点_p_とベクトルのセット_moves_を見つけて、最も効率的な方法で_dest_に移動する必要があります。 効率は、「最小直線距離」ではなく「最少移動数」として定義されます。移動セットがより少ない移動でそこに着くことができる場合、他の候補よりも_dest_から遠い_p_を選択することは許容されます。 _moves_のベクトルは、利用可能なベクトルの厳密なサブセットでなければなりません。入力セットに複数回表示されない限り、同じベクトルを複数回使用することはできません。

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

承認済みソリューションで更新

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

6 回答


6


実際には、約10個のベクトルがあることを考慮すると、特定の_dest_ポイントに対して、ベクトルのサブセットから* 1024 "ターゲット" *のみを計算できます。 。 これは、コンテキストに応じて「遅い」または「速い」場合があります(GPUなどの並列コンピューティングデバイスに実装されている場合、それはとてつもなく速いです)。

そこに到達するすべてのセットを使用すると、パスをより迅速に計算でき、クエリまたはそれ以上のもののサブセットから選択して、最も少ない移動で_dest_に到達するポイントを選択できます。

(Strilancに感謝)


5


A *(別名Aスター)パス検索アルゴリズムの一般化されたアプリケーションを作成できると思います。 N番目のスペースでできない理由はありません。 各移動のコストを説明できる場合、最適なパスを保証します。


5


したがって、サブセットが合計されて特定の値になるように、ベクトルのセットのサブセットを見つける必要があります。 1次元では、これはhttp://en.wikipedia.org/wiki/Subset_sum_problem[subset sum problem]と呼ばれ、NP完全です。

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

動作する可能性のあるいくつかの簡単な最適化:

  • 右側を指すベクトルを含む検索サブセットの優先順位付け 方向。

  • ミドルインザミドル。 ハッシュテーブルを使用して、到達可能なすべてのポイントを保存する 移動セットの前半のサブセットを使用して、最後から移動セットの後半を使用して何かをヒットできるかどうかを確認します。

  • 後方に移動します。 エンドポイントは1つだけなので、到達可能なすべての開始点をハッシュします そこからポイントはすべての可能な開始ポイントに対してチェックします。

  • 並行性


2


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


1


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

Meet-in-the-Middleソリューションを使用して、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))時間になります。


0


  1. 最初から始めます。

  2. しばらくの間

  3. 目的地までの距離を取得する

  4. すべての可能な動きをテストし、あなたに最も近いものを選びます 一度の移動で目的地。

  5. 終了する

これは目的地を中心に揺れ動くかもしれませんが、あなたを近づけます。