35

私はダイクストラ アルゴリズムのコードを書いています。現在使用されているノードから最小の距離でノードを見つけることになっている部分については、そこにある配列を使用し、それを完全に走査してノードを見つけています。

この部分はバイナリ ヒープに置き換えることができ、O(1) 時間でノードを把握できますが、さらに繰り返してノードの距離も更新します。そのヒープをどのように組み込むのでしょうか?

配列の場合、(ith -1) インデックスに移動してそのノードの値を更新するだけで済みますが、バイナリ ヒープでは同じことはできません。ノードの位置を出力してから更新します。

この問題の回避策は何ですか?

4

7 に答える 7

4

Min-Heap 配列に加えて、ハッシュ テーブルを使用してこれを行います。

ハッシュ テーブルには、ノード オブジェクトになるようにハッシュ コード化されたキーと、それらのノードが最小ヒープ配列のどこにあるかのインデックスである値があります。

次に、最小ヒープで何かを移動するたびに、それに応じてハッシュ テーブルを更新するだけで済みます。最小ヒープ内の操作ごとに最大 2 つの要素が移動され (つまり、交換される)、1 回の移動あたりのコストはハッシュ テーブルを更新するための O(1) であるため、最小ヒープ操作。たとえば、minHeapify は O(lgn) です。minHeapify 操作ごとに 2 つの O(1) ハッシュ テーブル操作を追加しました。したがって、全体の複雑さは依然として O(lgn) です。

この追跡を行うには、最小ヒープでノードを移動するメソッドを変更する必要があることに注意してください。たとえば、minHeapify() には、Java を使用して次のように変更する必要があります。

Nodes[] nodes;
Map<Node, int> indexMap = new HashMap<>();

private minHeapify(Node[] nodes,int i) {
    int smallest;
    l = 2*i; // left child index
    r = 2*i + 1; // right child index
    if(l <= heapSize && nodes[l].getTime() < nodes[i].getTime()) {
        smallest = l;
    }
    else {
        smallest = i;
    }
    if(r <= heapSize && nodes[r].getTime() < nodes[smallest].getTime()) {
        smallest = r;
    }
    if(smallest != i) {
        temp = nodes[smallest];
        nodes[smallest] = nodes[i];
        nodes[i] = temp;
        indexMap.put(nodes[smallest],i); // Added index tracking in O(1)
        indexMap.put(nodes[i], smallest); // Added index tracking in O(1)
        minHeapify(nodes,smallest);
    }
}

buildMinHeap、heapExtract は minHeapify に依存する必要があるため、ほとんどが修正されますが、抽出されたキーもハッシュ テーブルから削除する必要があります。これらの変更を追跡するには、recreaseKey も変更する必要があります。それが修正されたら、reduceKey メソッドを使用する必要があるため、insert も修正する必要があります。それはすべてのベースをカバーするはずであり、アルゴリズムの漸近的な境界を変更することはなく、優先キューにヒープを使用し続けることができます。

この実装では、実際には標準の最小ヒープよりもフィボナッチ最小ヒープが優先されることに注意してください。

于 2013-07-19T17:11:33.020 に答える
4

任意の形式のヒープを使用する際に遭遇した問題は、ヒープ内のノードを並べ替える必要があることです。そのためには、必要なノードが見つかるまでヒープからすべてをポップし続け、次に重みを変更して、それを (ポップした他のすべてのものと共に) 押し戻す必要があります。正直なところ、配列を使用するだけで、おそらくそれよりも効率的でコーディングしやすくなります。

これを回避する方法は、赤黒ツリーを使用することでした (C++ ではset<>、STL のデータ型にすぎません)。データ構造には、 (コスト) と(ノード)を持つpair<>要素が含まれていました。ツリー構造のため、最小要素へのアクセスは非常に効率的です (C++ では、最小要素へのポインターを保持することでさらに効率的になっていると思います)。doublestring

ツリーとともに、特定のノードの距離を含む double の配列も保持しました。そのため、ツリー内のノードを並べ替える必要があるときは、dist 配列からの古い距離とノード名を単純に使用して、セット内でノードを見つけました。次に、その要素をツリーから削除し、新しい距離でツリーに再挿入します。ノードを検索してO(log n)ノード O(log n) を挿入するため、ノードを並べ替えるコストはO(2 * log n)=O(log n)です。バイナリ ヒープの場合、O(log n)挿入と削除の両方の も含まれます (検索はサポートされません)。したがって、必要なノードが見つかるまですべてのノードを削除するコストがかかり、その重みを変更してから、すべてのノードを挿入し直します。ノードが並べ替えられたら、配列内の距離を変更して新しい距離を反映します。 .

ヒープ全体の構造はノードが維持する重みに基づいているため、ノードの重みを動的に変更できるようにヒープを変更する方法は正直思いつきません。

于 2013-01-10T17:29:30.617 に答える
2

このアルゴリズム: http://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html は、「インデックス付きヒープ」を使用してこの問題を回避します: http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java .htmlキーから配列インデックスへのマッピングのリストを本質的に維持します。

于 2013-06-23T15:40:18.410 に答える