4

A* のオープン リストにスキップ リストを使用することに興味があります。しかし、私を悩ませているのは、その確率論的な性質です。オープン リストは、非常に小さなセットから膨大な数のノードまでさまざまであり、それぞれのパフォーマンスを維持する必要があります。

私が理解しているように、スキップリストはランダムに小さなデータセットに対して悪い結果を与える可能性が高くなります。多数の短いパスが生成されると、これが問題になる可能性があると思います。

これを修正して、乱数をある程度ウォッチドッグしないように考えていました。各レベルのノード数の現在の合計を保持し、各レベル間のノードの理想的な分散を維持するために、介入してノードを特定のレベルにすることがあります。

特定のアプリケーションでこれがどれだけうまく機能するかはわかりません。代わりに、開いているリストの別のデータ構造に集中する必要があるかもしれません。

私がスキップリストで読んだすべての記事は、そのような最適化について言及していません. 私はパフォーマンスプロファイリングゲーム全体にかなり慣れていないので、文書化されたデータ構造を改善しようとするのをためらっています.

4

3 に答える 3

2

A*アルゴリズムで作成されると予想される長さのスキップリストをランダムに生成するプログラムを作成することをお勧めします。それらのリストを調べて、最適ではないリストがいくつあるかを確認します。

提案したモニタリングを備えたプロダクションスキップリストデータ構造を作成することはお勧めしません。一般的なケースでは、監視および介入コードによってスキップリストのパフォーマンスが低下する可能性があります。

于 2012-10-24T02:06:22.683 に答える
1

  1. はい、その通りです。小さなスキップ リストについて話すと、スキップ リストが減衰する可能性が高くなります。
    一般に、この論文alphaによると、スキップ リストがalpha * nスペースを超える確率がそれより小さくなるような定数があります。そのため、スキップ リストが大きくなるにつれて、この (この制限を超える) 確率はますます小さくなります。1/2Ω(sqrt(n))

  2. スキップ リストの最悪のケースを回避するために、元のスキップ リストのバリエーションである決定論的スキップ リストを使用できます。この主題は、この論文で議論されています

  3. その他の代替手段は、 AVLやred-black-treeなどのバランスの取れた BST 、またはB+ ツリー(通常はファイル システムに好まれる) です。

  4. 「開集合」が実際に非常に小さい場合 - 分岐因子も非常に小さい (1 に近い) か、正確にはB^d(d=解の深さ; B=分岐因子) も小さくなる可能性があります。これにより、スキップ リストの実装に関係なく、ルックアップが高速になります。これは、必要なノードがほとんどないと予想されるためです。

于 2012-10-24T12:17:52.787 に答える
0

「スキップリストは、小さなデータセットに対してランダムに悪い結果をもたらす可能性が高い」と言うとき、あなたは正確に何を恐れていますか？

恐れてはいけないのは、たとえば10個の要素のリストの場合、トラバーサルを高速化するのに十分なレベル2または3のノードがないことです。2要素または10要素のリンクリスト（レベル2+ノードのないスキップリストの要約）を反復することの違いは、タイトなループ（データに必要なノード参照管理のタイプ）でも基本的に存在しません。構造はおそらくより大きな影響を与えるでしょう）。

明らかに、より多くの要素に到達すると、十分な高レベルのノードがないことの影響が大きくなります。しかし、幸いなことに、より高いレベルのノードを取得する可能性も高くなります。たとえば、8つの要素を追加した場合、それらがすべてレベル1ノードになる可能性は0.5 ^ 8 = 0.39％です。つまり、非常にまれです。

于 2012-10-24T07:59:10.727 に答える