2

一様コスト検索で述べられているように、繰り返される状態を破棄する必要があることが非常によくあります。

  if n is in frontier with higher cost
  replace existing node with n

Priority Queue は、アイテムの優先度を検索して更新するためのインターフェイスを提供しません。これに関するリソースが見つからないことに驚いています。どなたか助けてください。

4

3 に答える 3

1

優先検索キューを探しています。

優先検索キューは、検索ツリーと優先キューの両方の操作を効率的にサポートします。Binding は、キーと優先度の積です。バインディングは、キューで (通常は対数時間で) 挿入、削除、変更、および照会でき、優先度が最も低いバインディングは一定時間で取得できます。

以下はHaskellでの実装です。

于 2012-10-02T10:14:44.933 に答える
1

多くのプライオリティ キューの実装では、キュー要素への参照を保持し、それを使用してこの要素を削除/更新できます。

プライオリティ キューを二分探索木として実装すると、このような参照を簡単に保持できます。バイナリ ヒープの場合、これは可能ですが、より困難です。すべての要素の参照を更新し、アップヒープまたはダウンヒープに移動する必要があります。

プライオリティ キューの実装があり、均一コスト検索などのアルゴリズムで使用すると要素を効率的に更新できます。ペアリング ヒープとフィボナッチ ヒープを参照してください。

于 2012-10-02T10:30:32.823 に答える
0

実際には、均一コスト検索の通常の優先度キューで問題を解決できます。

古いものを削除せずに、新しいより良い (ノード、コスト) ペアを挿入できます。新しく挿入されたエントリを常に最初に処理し (そのほうがよいため)、古いエントリの処理は事実上何もしません。欠点は、(O(V) ではなく) 優先キューに O(E) 要素が残る可能性があることです。

于 2021-02-06T13:38:14.737 に答える