1

もともとSortedDictionaryを使用したEricLippertのPriorityQueue実装を使用したボードゲーム用のA-*の実装がありますが、ボードサイズに対してパフォーマンスが不十分です。

PriorityQueueのMinHeap実装を使用すると、長い対角パスで* 2のスピードアップが得られました（5〜6秒から2〜3秒）。しかし、それから私はそれが不安定な種類を提供することに気づきました。このアプリケーションでは、安定したソートが必要です。

MinHeapの効率を組み合わせながら、SortedDictionaryと同じように安定したソートを提供するPriorityQueueのよく知られた実装はありますか？

更新：以下のコメントからの追加の詳細：

  • 必要なPriorityQueue操作：Enqueue（）、Dequeue（）＆Count;
  • A- *の各反復で：IsEMpty＆Dequeue（）が1回ずつ呼び出され、Enqueue（）が6回呼び出されます。

解像度：

との複雑さはSortedDictionary<uint,Queue<TValue>>同じMinListHeap<KeyValuePair<TPriority,TValue>>ですが、挿入順序を維持するための追加のコードの複雑さは、一定のtmeペナルティのようです。これは決定的なものではないかもしれませんが、私は洗練のこの段階でぶら下がっている果物を探していました。

さらに、問題についてもっと考えてみると、安定性は短いパスでのみ必要であり、長いパスでは必要ないことに気づきました。そのため、開始から目標までの距離の初期ヒューリスティック推定に基づいて、FindPath（）へのエントリ時にPriorityQueueの必要な実装を選択することができました。

4

1 に答える 1

1

これはコメントのはずですが、長すぎます。だからここに行きます：

あなたが提案したリンクに続く並べ替えられた辞書としての優先度キューの実装を見つけることができませんでしたが、グーグルで検索すると、この優先度キューは二分探索木を使用して実装されていることが示唆されます。その場合、BST をヒープに置き換えることで 2 倍の改善が得られる理由が理解できないため、これらは自己均衡検索ツリーではないように思われます。セルフバランシング BST により、 および で log(n) パフォーマンスが保証されinsert()ますfind()。deque()同じことが(= removeMin()) にも当てはまります: また、log(n) が保証されている必要があります: 左の子がなくなるまで左に移動します。

わかりましたので、二分探索木 (BST) のすべての操作に対して log(n) があります。ヒープはどうですか？さて、あなたが見ている操作については、同じです: removeMin()(= dequeue()) は、最高/最低のキー (これは O(1)) を持つノードを返しますが、最後のノードを最初の場所に配置し、それを沈めます。それをその子と再帰的に比較することによって。これには、各レベルで 2 つの比較が必要であり、通常は log(n) レベルが含まれます。O( log removeMin()(n) ) 操作も同様です。insert()( =enqueue())? ここで、通常の実装では、新しい項目を最後に配置してから、その親と比較して浮き上がらせます。通常、これには 0.5*log(n) 操作、つまり O( log(n) ) が必要です。これは、BST とヒープの両方が enqueue() と dequeue() で log(n) のパフォーマンスを持つ必要があることを意味します。また、両方のデータ構造は で O(1) パフォーマンスを持つ必要がありますisEmpty()。

この推論が正しければ、次のいずれかが示唆されます。

  • BST 実装の定数係数は、minHeap 優先度キューの定数係数を小さくします
  • 使用される BST は自己平衡ではありません。

ヒープオンの方が BST よりも優れ0.5*log(n)ていると思う人もいるかもしれませんが、実際には BST 挿入も実際にはほぼ同じであるため、これはあり得ないと思います。一定の要因はもっともらしいです: minHeap が自動サイズ変更配列 (またはより良いのは非サイズ配列) として実装されている場合、minHeap はBST 実装が行う必要がある追加のストレージ領域を に割り当てる必要がない場合があります。insert()insert()0.5*log(n)enqueue

BST が自己平衡を保っていない可能性もあります。この場合、アイテムが追加される順序に応じて、最悪の場合、dequeue()または のいずれかが O(n) 時間かかります。enqueue()したがって、これは注目すべきものです。

EDIT 1 : 通常の BST 実装を安定させる方法は、同じキーを持つノードを挿入すると、新しいノードが (たとえば) 同じキーを持つノードの正しい子になるという規則を採用することです。このようにして、同じキーを持つ最初のノードがデキューされます。自己平衡 BST では、回転がこの望ましい不変量に違反する可能性があるため、これにはもう少し作業が必要になる場合があります。この場合、私が何をするか ( AVL ツリーではなく、赤黒ツリーを考える) は、2 つのノード A と BI を回転させて、それらのキーが実際には同一であるかどうかを確認し、そうであれば、ノード データを切り替えることだと思います。ノード構造を維持しながら。しかし、この問題にはもっと良い解決策があるかもしれません。

EDIT 2このアクティクルによると、SortedDictionary は実際には赤黒木に基づいています。これは、実装のバグ (疑わしいが前代未聞ではない) か、原因として一定の要因のいずれかを示唆しています。

于 2013-03-19T05:50:03.633 に答える