5

グラフの問題を解こうとしています。グラフは加重され、無向です。
グラフのサイズ:

no. of vertices upto  200,000 
no. of edges upto  200,000

グラフ内の指定された 2 つのノード (S & D) 間の最短経路を見つける必要があります。私はDijkstra's algorithmこれを見つけるために使用しています。
問題は、グラフが頻繁に変化することです。特定のエッジがグラフから削除された場合、S & D 間の最短経路を見つける必要があります。エッジを削除した後、グラフを新しいグラフとして扱うことにより、ダイクストラのアルゴリズムを使用して新しいパスを再度計算しています。ただし、200,000 のエッジが存在する可能性があるため、このアプローチは遅すぎます。エッジを削除するたびに最短経路を 200,000 回計算します。
メモ化手法を使用することを考えていましたが、特定のエッジがグラフから削除されると最短経路が完全に変わる可能性があるため、把握できません。
//詳細
ソースと宛先は問題全体で固定されています。
エッジの削除ごとに最大 200,000 のクエリがあります。一度に、各テスト ケースの初期グラフから 1 つのエッジのみが削除されます

4

4 に答える 4

4

エッジが追加されていないため、削除後の最短パスは常に元のパスよりも大きくなります（または等しくなります）。削除されたエッジが元の最短パスの一部でない限り、結果は変わりません。それが元の最短経路の一部である場合、アルゴリズムを再度実行することが最悪の場合の解決策です。

正確な答えを探していない場合は、おおよそのローカルメソッドを試して、欠落しているエッジを埋めることができます。

ダイクストラアルゴリズムを拡張して情報を保存すると、最初の検索中に特定の状態に戻ることができます。

これは、リラクゼーション中に最短パスを変更するたびに、ヒープを含むデータ構造に加えられた変更を記録することを意味します。これにより、最初の実行中の任意の時点にアルゴリズムの状態を復元できます。

最短経路上にあったエッジを削除するときは、エッジが緩和される直前のポイントに戻ってから、削除されたエッジが存在しなかったかのようにアルゴリズムを再起動する必要があります。

于 2012-06-18T06:56:02.797 に答える
4

私のおすすめ：

最初に Dijkstra を使用してソースから目的地までの最短経路を見つけますが、ソースと目的地の両方から同時に歩きます (移動した目的地からの距離を示すには負の距離の数値を使用します)。距離 (ソースまたは宛先のいずれかから)。逆ノードからの値を持つノードに遭遇すると、そのノードに到達するためのパスが最短になります。

次に、エッジを削除します。エッジが最短パスの一部でない場合は、現在の既知の最短パスを返します

削除されたエッジが最短経路の一部である場合は、削除されたノードのいずれか小さい方よりも大きい (正または負の) 既知の絶対距離で再度検索を実行します。既知の結果に、始点から歩くときは正、終点から壊れたセグメントまで歩くときは負として、既知の最短経路を追加します。その開始点から両方向に検索します。値セット (正または負) を持つノード、または以前の最短パスの一部であったノードにヒットすると、新しい最短パスが見つかります。

これを行う主な利点は次のとおりです。

  1. 送信元と宛先の両方から歩くので、送信元ノードが端にある場合を除き、全体的により少ないノードをさまよいます。
  2. 削除されたエッジが以前の最短パスの最初のエッジであったとしても、検索結果全体を放棄するわけではありません。最短の方法で再接続するパスを見つける必要があるだけです。

削除されたノードが既知の最短パスの一部である場合でも、毎回のブルート再計算に対するパフォーマンスはかなりのものになります。

それがどのように機能するかについては、次のグラフを検討してください。

        I
       /
  B---E
 /   /   H
A   D   /|
 \ / \ / |
  C---F--G

Aからを取得したいのでH、簡単にするために、各エッジの値が 1 であると仮定します (ただし、値は何でもかまいません)。

A から始めます。

        I
       /
  B---E
 /   /   H
0   D   /|
 \ / \ / |
  C---F--G

ここで、H の値を 0 から開始するように設定します。

        I
       /
  B---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  C---F---G

そして展開：

        I
       /
  1---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  1---F---G

次に、次に低い値を展開します。これは次のようになりますH。

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

, orのB前に来るので、任意に選択します(絶対値は同じです):CFG

        I
       /
  1---2
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

次に C

        I
       /
  1---2
 /   /        (0)
0   2        /  |
 \ / \      /   |
  1---2 & (-1)--(-1)

これで、正の値と負の値の両方を認識するノードができたので、両方への距離であることがわかりAます。最初に最短のノードを拡張していたので、これは最短のパスである必要があり、したがって、からへHの最短のパスと言えます。とコストAHA->C->F->HABS(2)+ABS(-1) = 3

ここで、C->F I / 1---2 / / (0) 0 2 / | という行を削除したとします。\ / \ / | 1 2 & (-1)--(-1)

次に、C と F の小さい方の値 (この場合は 1) を超える絶対値を持つすべての既知の値を削除します。

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1   (-1)--(-1)

ここで再び前のように展開しますB。\ / \ / | 1 (-1)--(-1)

それでC

        I
       /
  1---2
 /   /     (0)
0   2     /  |
 \ / \   /   |
  1   (-1)--(-1)

今 F:

        I
       /
  1---2
 /   /         (0)
0   2&(-2)    /  |
 \ /    \    /   |
  1      (-1)---(-1)

Aしたがって、 からへの最短経路Hは A->C->D->F->H であり、コストがかかることがわかります。ABS(2)+ABS(-2) = 4

これは、任意の数のノード、エッジ、およびエッジの重みで機能します。展開するノードがこれ以上ない場合は、「ルートなし」応答を返します。

以前の最短パスにあったノードのノード値をリセットしないことで、さらに最適化できます。そうすることで、単純な性質は失われますが、過度に複雑ではありません。

上記の例では、最初は違いはありませんが、チェーン内A->Cの および他のノードのコストをC(負として)覚えているため、リンケージを削除すると違いが生じます。

片面ダイクストラを使用して、削除されたエッジの前にロールバックする場合の利点を以下に示します。

        I
       /
  1---E
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G

次に展開しBます。

        I
       /
  1---2
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G

子：

        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   F--G

D:

        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

E:

        3
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

ふ:

        3
       /
  1---2
 /   /   4
0   2   /|
 \ / \ / |
  1   3--4

次に、パスが現在であり、コストが 4 であると判断しA->C->D->F->Hます。ここで 5 つの展開ステップを実行する必要があることに注意してください。双方向の方法で必要な 3 つと比較してください。

削除されたエッジがパスの中央に近づくにつれて、双方向のグラフ ウォーキング アルゴリズムを使用して新しいパスを再計算することにより、節約が大幅に改善されます。たとえば 50 個のノードがぶら下がっていて、そこからへHの経路が 1 つしかない場合を除きますが、これはごくまれなケースであり、通常のネットワークでは起こりそうにありません。ここで、 からへの直接パスは 1 つしかありませんが、 には50 個のエッジが接続されています。AHHAA

約 200,000 個のエッジがあり、最大 200,000 個のノードがある可能性がある場合、9 個のノードと 11 個のエッジしかない私の例のグラフと比較して、かなりの節約が見られるでしょう。これは、計算時間の大部分がループに費やされる可能性が高いため、ノード展開が最も少ないアルゴリズムを探しているという考えに基づいています。

于 2012-06-18T14:28:34.243 に答える
0

考えがある：

  • 初めてダイクストラ法を実行し、送信元から宛先までの最短パスのすべてのエッジを記憶します。
  • 削除を行うときは、最短パスからエッジを削除したかどうかを確認します。いいえの場合、結果は同じです。はいの場合、別のダイクストラ法を実行します。

別のアイデア：

  • 最初にダイクストラを実行し、各頂点について、その頂点に依存するすべての要素を念頭に置いてください。
  • 削除を実行するときは、トポロジカルソートのようなことを行う必要があり、頂点に依存するすべての頂点に対して更新を実行し、それらの頂点で部分的なダイクストラを実行します。
于 2012-06-18T06:55:32.080 に答える
0

削除されたエッジが最も短いパスからのものでない場合、パスは同じままです。それ以外の場合、問題は単調であるため、適切な正確な解はおそらくありません。ノード C を使用する A から B への最短パス sp (sp(A, B)) は、sp(A, B) = sp(A , C) + sp(C, B) (すべての C)。

1 つの (非常に良い) エッジを削除すると、これらのパスをすべて破棄できます。最善の解決策 (正確ではありません) は、Floyd-Warshall アルゴリズムを使用して、すべてのノードのペア間の最短パスをすべて計算し、パスからエッジを削除した後、最短の迂回路を使用してパスを修復することです。

于 2012-06-18T09:18:32.277 に答える