dynamic-programming
動的プログラミングを使用したグラフ問題の解法
サーチ…
Floyd-Warshallアルゴリズム
Floyd-Warshallのアルゴリズムは、正または負のエッジ重みを持つ重み付きグラフの最短経路を見つけるためのアルゴリズムです。アルゴリズムを1回実行すると、すべての頂点ペア間の最短パスの長さ(合計ウェイト)が求められます。わずかなバリエーションで、最短パスを印刷し、グラフ内の負のサイクルを検出することができます。 Floyd-Warshallはダイナミックプログラミングアルゴリズムです。
例を見てみましょう。このグラフにFloyd-Warshallのアルゴリズムを適用します:
まず、2D行列を2つ取ります。これらは隣接行列です。行列のサイズは、頂点の総数になります。私たちのグラフでは、 4 * 4行列を取ります。 距離行列は、これまでに2つの頂点の間で見つかった最小距離を格納します。まず、エッジを、UVおよび距離/重量の間にエッジが存在する場合は、wは 、我々は、保存されます: distance[u][v] = w
。存在しないすべての辺について、 無限を置くつもりです。 Path Matrixは、2つの頂点間の最短距離パスを再生成するためのものです。最初は、 uとvの間にパスがある場合は、 path[u][v] = u
ます。つまり、 頂点-vから頂点 -vに来る最善の方法は、 vとuを結ぶエッジを使うことです。 2つの頂点の間にパスがない場合は、ここにNを入れて、現在利用可能なパスがないことを示します。グラフの2つの表は次のようになります。
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 6 | 15 | | 1 | N | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | inf | 0 | -2 | inf | | 2 | N | N | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | inf | inf | 0 | 2 | | 3 | N | N | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | inf | inf | 0 | | 4 | 4 | N | N | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
ループがないので、対角線はNに設定されます。頂点自体からの距離は0です。
Floyd-Warshallアルゴリズムを適用するために、中間頂点kを選択します。次に、各頂点iについて 、 iからkへ 、次にkからjへ行くことができるかどうかを調べる。ここで、 jは別の頂点であり、 iからjへ行くコストを最小限に抑える。現在の距離[i] [j]が距離[i] [k] + 距離[k] [j]より大きい場合、 距離[i] [j]をこれら2つの距離の合計に等しくします。そして、 経路[i] [j]は経路[k] [j]に設定されます .iからkへ、そしてkからjへ行く方が良いでしょう。すべての頂点がkとして選択されます。私たちは、3つのネストされたループがあるでしょう:kは 1から4に行くために、iは 1から4まで行くとjは我々がチェックつもり1から4に行きます:
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
基本的に調べているのは、 頂点のすべてのペアについて、別の頂点を通ることでより短い距離を得ることですか?グラフの操作の合計数は4 * 4 * 4 = 64になります。これは、この検査を64回行うつもりであることを意味します。それらのいくつかを見てみましょう:
距離よりも大きくない場合、K = 1、I = 2及びJ = 3、 距離[i] [j]が -2であり、[I] [K] + 距離[K] [J] = -2 + 0 = -2 。それで変わらないでしょう。再び、k = 1 の場合、I = 4、J = 2、 距離[i] [j]が 距離よりも大きい無限 = [I] [K] + 距離[K] [J] = 1 + 3 = 4 。そこで、 distance [i] [j] = 4を入れ、 path [i] [j] = path [k] [j] = 1を入れます。これが意味することは、 頂点4から頂点2に行くためには、経路4-> 1-> 2が既存の経路よりも短いことである。これは、両方の行列をどのように埋め込むかです。各ステップの計算をここに示します 。必要な変更を加えた後の行列は次のようになります。
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 1 | 3 | | 1 | N | 1 | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | 1 | 0 | -2 | 0 | | 2 | 4 | N | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | 3 | 6 | 0 | 2 | | 3 | 4 | 1 | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | 4 | 2 | 0 | | 4 | 4 | 1 | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
これは最短距離行列です。例えば、 1から4までの最短距離は3であり、 4から3までの最短距離は2である 。私たちの疑似コードは次のようになります:
Procedure Floyd-Warshall(Graph):
for k from 1 to V // V denotes the number of vertex
for i from 1 to V
for j from 1 to V
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
end for
end for
end for
パスの印刷:
パスを印刷するには、 パスマトリックスをチェックします。 uからvへのパスを印刷するには、 パス[u] [v]から開始します 。私たちは、スタック内の[V] [U]我々はパス[U]を見つけるまで[V] = U、V = パス[U] [V]を変え続ける設定とパスのすべての値をプッシュします。 Uを見つけた後、私たちは、Uを印刷し、スタックから項目を飛び出る開始し、それらを印刷します。これは、 パス行列が他のノードからのvへの最短経路を共有する頂点の値を格納するためである。疑似コードは次のようになります。
Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
S.push(Path[source][destination])
destination := Path[source][destination]
end while
print -> source
while S is not empty
print -> S.pop
end while
負のエッジサイクルを見つける:
負のエッジサイクルがあるかどうかを調べるには、 距離行列の主対角をチェックする必要があります。対角線の値が負の場合、グラフに負のサイクルがあることを意味します。
複雑:
ワーシャル-フロイド法の複雑さはO(V³)であり、空間の複雑さがある:O(V²)。
最小頂点カバー
最小頂点カバーは古典的なグラフの問題です。たとえば、都市ではいくつかのポイントを結ぶ道路がいくつかあります。ノードを使ってエッジと点を使って道路を表現しよう。 2つのグラフの例を見てみましょう:
私たちはいくつかの点でウォッチマンを設定したい。警備員は、ポイントに接続されているすべての道路を守ることができます。問題は、すべての道路をカバーするのに必要な監視人の最小数はいくらですか?ノードA 、 B 、 H 、 I 、 Jにウォッチマンを設定すると 、すべての道路をカバーすることができます。
これが最適なソリューションです。街全体を守るためには少なくとも5人の警備員が必要です。これをどうやって決めるの?
最初は、これはNP困難な問題であることを理解する必要があります。つまり、問題には多項式時間の解がありません。しかし、グラフがツリーの場合は、 (n-1)個のノードがあり、 nがエッジの数であり、グラフにサイクルがない場合、動的プログラミングを使用して解決できることを意味します。
DPソリューションを構築するには、次の2つの戦略を実行する必要があります。
- ノードに監視員がいない場合、ノードに接続されているすべてのノードに監視員がいるか、すべての道路がカバーされません。 uとvが接続されており、uは任意の警備員を持っていない場合は、Vは、警備員を持っている必要があります。
- あるノードに監視員がいる場合、それに接続されている別のノードには監視人がいる場合とない場合があります。つまり、警備員を持つ必要はありませんが、それは有益なことがあります。 uとvが接続されていて、 uが監視員を持っている場合は、次のようにして、
- ウォッチマンをvに設定する。
- ウォッチマンをvに設定しない。
stateが現在のノードであり、watchmanがあるかどうかを示す再帰関数を定義しましょう。ここに:
F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.
この関数は、残りのノードのウォッチマンの数を返します。
ツリーの例を見てみましょう:
ノードAに監視人を置かないと、ノードB 、 C 、 Dに監視員を置かなければならないと簡単に言うことができます。我々は推測することができます:
F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0
私たちがノードAに警備員を置かないと、必要な警備員の数が返されます。現在のノードではウォッチマンを設定していないため、最後に0を追加しました。
今、 F(A,1)
はノードAに警備員を設定することを意味します。そのためには、接続されたすべてのノードでウォッチマンを設定することも、そうしないこともできます。私たちは最低限の警備員を私たちに提供するものを取るでしょう。
F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1
各ノードでウォッチマンを設定して最適値を設定しないで設定を確認します。
私たちが注意しなければならないことの1つは、一度子ノードに行くと、親ノードを振り返ることはありません。上の例から、 AからBに行きましたので、 parent [B] = Aです。だから私たちはBからAに戻っていません。
ベースケースを判別するには、ノードから他の新しいノードに行くことができない場合、現在のノードにウォッチャーマンがある場合は1を返し、現在のノードにウォッチマンがない場合は0を返しますノード。
私たちのツリーの隣接リストを持つ方が良いです。リストをエッジで表示させる。ここで、 nは計算された値を格納するノードの数を示し、 -1で初期化する配列dp [n] [2]を持ちます。ノード間の親子関係を表す親[n]配列もあります。私たちの擬似コードは次のようになります:
Procedure f(u, isGuarded):
if edge[u].size is equal to 0 //node doesn't have any new edge
Return isGuarded
else if dp[u][isGuarded] is not equal to -1 //already calculated
Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
v := edge[u][i]
if v is not equal to parent[u] //not a parent
parent[v] := u
if isGuarded equals to 0 //not guarded, must set a watchman
sum := sum + f(v,1)
else //guarded, check both
sum := sum + min(f(v,1), f(v,0)
end if
end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]
ノードAをルートとして表すと、関数min(f(A,1), f(A,0))
が呼び出されます。つまり、ルートノードにウォッチマンを設定するのが最適かどうかをチェックします。これが当社のDPソリューションです。この問題は、最大一致アルゴリズムまたは最大フローを使用して解決することもできます。