ネットワークフローアルゴリズム(Network Flow)
8626 ワード
ネットワーク・フローの概要
1.ネットワークフロー(Network Flow)概念
ネットワークストリームは交通ネットワークの解析に起源し,非公式の例を挙げると,ネットワークストリームアルゴリズムの目的は,帯域重み有向図におけるソース点から集約点までのtrafficの大きさを見つけることである.私たちの目標は多項式時間内に問題を解決することです.
私たちが一般的に求めているのは最大流ですが、源点を工場にたとえると、問題は工場から最大でどれだけの貨物を出すことができるかを求め、道路の容量制限を超えない、つまり最大流です.
2.ネットワークフローの定義
トラフィックネットワーク:有向図G=(V,E)を与え、各エッジeには非負数の容量ceがある.また、図にはソース点s∈Vと、もう一つの集約点t∈Vがある.
ソースポイント:図中にn個のポイントがあり、m本のエッジがあり、1つのポイントsが特殊で、出エッジだけがエッジに入らず、ソースポイントと呼ばれています.
汇点:もう一つの点tも特殊で、进辺だけ出辺がなく、汇点と呼ばれています.
容量と流量:図中の各有向辺に2つの量がある、容量cと流量f、iからjまでの容量は通常c[i,j]で表され、流量は通常f[i,j]である.例えば、通常はこれらの辺を道路と想像することができて、流量はこの道路の車の流量で、容量は道路が耐えられる最大の車の流量です.明らかに,流量<=容量である.ソースポイントと送金ポイントではないポイントごとに、記憶機能のない貨物の中継所を類比することができ、すべての「入る」彼らの流量と、彼自身から「出る」すべての流量に等しい.
s−t flow:各エッジに非負の流量値f(e)を割り当てる関数であり、ここでは2つの条件を満たす必要がある:1.容量制限(Capacity conditions):各エッジeに対して0≦f(e)≦ce.2.平衡制限(Conservation conditions):sおよびt以外の各点について、合流点eの流量は、流出点eの流量に等しくなければならない.
value of a flow:ソースポイントsから流出する流量の統合.ソースポイントsから複数のエッジを有することができ、ここでは図全体の総流量を指す.
最大流:源点を工場にたとえると、最大流の問題は工場から最大でどれだけの貨物を出荷できるかを求め、道路の容量制限を超えないことです.Flow NetworkのMaximum Flow value、これが最大ストリームの定義です.
Residual graph:図Gの流派から生まれ、Gfと記す.-Gf has the vertices of G - Gf has two kinds of edges: for each edge e=(u,v)∈E(G) - Forward edges: if e has leftover capacity. Gf contains the edge (u,v) with capacity ce−f(e) - **Backward edges:**if e has positive flow Gf contains the edge (v,u) with capacity f(e)
augmenting path:残りの図Gfにおけるs−tのパスである.•The bottleneck of a path is the minimum residual capacity of all edges in that path • To augment flow f using path P consists of modifying the flow in all edges of P as follows: ◮ let b= bottleneck of P ◮ increase the flow by b in all forward edges of P ◮ decrease the flow by b in all backward edges of P
3.
4.
ダイナミックプランニングの古典的な問題
1.重み付け間隔スケジュール
入力:開始時間、終了時間、および期間の重みを持つn間隔のセット.≪出力|Output|emdw≫:互いに重ならない最大ウェイトを持つ間隔セットのセット.Eg:解決方法:「記憶付き」の保存と再帰による解決.
間隔は終了時間順に並べ替えられ、j番目の間隔の重みと、j番目の間隔と一致しない前の間隔のOpt(p(j))との和であるべきである.Opt(j-1)と等しい.中で一番大きいです.
下から上への繰返しで計算することもできます
2.セグメント最小二乗問題
n個の点のセットを与え、これらの点を最良にフィットさせることができる直線を決定する必要がある.error=点から直線までの距離の二乗があり、この直線は最小のerrorを有する.
複数の直線を使用すると、より良いフィットが得られますが、より多くのセグメントに分割することは、私たちのデータ分析には意味がありません.指数の異なる区分(求子集に相当)があるため、暴力的な検索は現実的ではない.
解決方法:アルゴリズムのペナルティ値として可変変数Cを導入し,分割にフィットする線が多ければ多いほどC値が大きくなる.そこで私たちの目標は、C+各線のerror値を最小限に抑えることです.定義e(i,j)はpiからpjの点にフィットするerrorである.OPT(i)はpiからpjへの最適解(OPT(0)＝0)である.次のことがわかります.
OPT(j)=e(i,j)+C+OPT(i−1)
iの値は決定できませんが、最小値を与えるiの値を選択できます.
OPT(j)=min1≤i≤j(e(i,j)+C+OPT(i−1))
これにより、擬似コードを得ることができます.
各点のセグメント最小二乗のerror値を計算し、配列に格納した後、配列を巡回して最適なフィット線を得る.
3.自動車積載問題
できるだけ多くの貨物を自動車に積むことを要求する.入力:n個の箱、各箱iに重量wiがある;自動車の総荷重はWである.出力:総重量制限を満たす下で、できるだけ多くの積載重量を満たす箱のサブセット.
解決方法:明らかに,この場合,貪欲アルゴリズムは最適解を与えることができない.例えば、自動車の総荷重は10で、4つの箱があり、それぞれ重量は8、3、3、3である.最適解は9ですが、欲張りは重さ8の箱を選ぶだけです.
箱の数を減らし、総重量制限を減らすことで、問題をより小さな問題に解消することができます.私はOPT(i,w)で私たちが重量制限wの条件の下で、前のiつの箱の中で積載できる最大重量を表します.
i番目の箱の場合、マウントするか、マウントしないかを選択できます.
OPT(i,w)=max(wi+OPT(i−1,w−wi),OPT(i−1,w))
wiはwより大きくすることはできません.そうしないと、箱iを積まないことしか選択できません.このアルゴリズムには時間的複雑さ:O(n・W)がある.
4.バックパック問題(Knapsack Problem)
入力:n件の物品、物品iは重量wiと価値viがあります;リュック総重量W.出力:総重量制限を満たす最大価値のあるアイテムのセット.
解決方法:このとき貪欲も最適解を得ることができず、例えばW=100で、2つの品物があり、重量と価値はそれぞれ(20,80)、(90,90)であり、このとき貪欲は最小重量を選択するが、リュックサックはもう入れられない.
リュックサックの問題は、価値を導入したトラックの積載問題のようなものだ.OPT(i,w)は、前のi品のうち、w重量制限下で得られる最大価値を示す.私たちはこの品物を選ぶことができます.
OPT(i,w)=max(vi+OPT(i−1,w−wi),OPT(i−1,w))
wiはwより大きくしてはならない.そうしないと、物品iを積まないことしか選択できない.このアルゴリズムには時間的複雑さ:O(n・W)がある.
4.シーケンス比較(Sequence Alignment)
2つのシーケンス間の類似性を決定するために,2つのstringを一定の法則に従って配列した.シーケンスには間隔を挿入することでより良い類似性を得ることができるが,gapとmismatchにはcostを持つ異なる罰則値を割り当てる.2つのstringを与えて、それらの間の類似度の解決方法を計算します:2つのstringをxとyにして、私達はA(i,j)にx 1からxiに対して、y 1からyjの最適な整合値、すなわち最小のgapとmismatchの懲罰値を表します.疑似コード:
5.負のエッジを持つ最短パス(Bellman-Ford Shorest Path Algorithm)
入力:重み付き図G,c(v,w)は頂点vからwまでのエッジを表すcostであり、負であってもよい.出力:負のループ(すべてのエッジのcostの和が負)またはsからtまでの最短パス.
実際の生活では,例えば経済学における相互振り替えは負のエッジを導入する可能性があるが,Dijkstraアルゴリズムは制限されており,解決できない.この場合、Bellman-Ford Shortest Path Algを使用する必要があります.使用前に、図に負のループがない場合、n個の点を持つ図Gに対して、点sからtまでの最短経路がn-1個のエッジを多く含むという定理を知る必要があります.
解決方法:OPT(i,v)をi辺以下の場合、点vから点tまでの最小path costを表す.我々が求めているのはOPT(n−1,s)であり,再帰初期条件OPT(0,t)＝0,OPT(0,v)＝＋∞(v!＝t)がある.疑似コード:
OPT(i,v)を計算し,エッジ(v,w)が存在する点のみをとることで,時間的複雑度をO(m・n)に低減できる.
参照先:https://www.zhihu.com/question/23995189
1.ネットワークフロー(Network Flow)概念
ネットワークストリームは交通ネットワークの解析に起源し,非公式の例を挙げると,ネットワークストリームアルゴリズムの目的は,帯域重み有向図におけるソース点から集約点までのtrafficの大きさを見つけることである.私たちの目標は多項式時間内に問題を解決することです.
私たちが一般的に求めているのは最大流ですが、源点を工場にたとえると、問題は工場から最大でどれだけの貨物を出すことができるかを求め、道路の容量制限を超えない、つまり最大流です.
2.ネットワークフローの定義
トラフィックネットワーク:有向図G=(V,E)を与え、各エッジeには非負数の容量ceがある.また、図にはソース点s∈Vと、もう一つの集約点t∈Vがある.
ソースポイント:図中にn個のポイントがあり、m本のエッジがあり、1つのポイントsが特殊で、出エッジだけがエッジに入らず、ソースポイントと呼ばれています.
汇点:もう一つの点tも特殊で、进辺だけ出辺がなく、汇点と呼ばれています.
容量と流量:図中の各有向辺に2つの量がある、容量cと流量f、iからjまでの容量は通常c[i,j]で表され、流量は通常f[i,j]である.例えば、通常はこれらの辺を道路と想像することができて、流量はこの道路の車の流量で、容量は道路が耐えられる最大の車の流量です.明らかに,流量<=容量である.ソースポイントと送金ポイントではないポイントごとに、記憶機能のない貨物の中継所を類比することができ、すべての「入る」彼らの流量と、彼自身から「出る」すべての流量に等しい.
s−t flow:各エッジに非負の流量値f(e)を割り当てる関数であり、ここでは2つの条件を満たす必要がある:1.容量制限(Capacity conditions):各エッジeに対して0≦f(e)≦ce.2.平衡制限(Conservation conditions):sおよびt以外の各点について、合流点eの流量は、流出点eの流量に等しくなければならない.
value of a flow:ソースポイントsから流出する流量の統合.ソースポイントsから複数のエッジを有することができ、ここでは図全体の総流量を指す.
最大流:源点を工場にたとえると、最大流の問題は工場から最大でどれだけの貨物を出荷できるかを求め、道路の容量制限を超えないことです.Flow NetworkのMaximum Flow value、これが最大ストリームの定義です.
Residual graph:図Gの流派から生まれ、Gfと記す.-Gf has the vertices of G - Gf has two kinds of edges: for each edge e=(u,v)∈E(G) - Forward edges: if e has leftover capacity. Gf contains the edge (u,v) with capacity ce−f(e) - **Backward edges:**if e has positive flow Gf contains the edge (v,u) with capacity f(e)
augmenting path:残りの図Gfにおけるs−tのパスである.•The bottleneck of a path is the minimum residual capacity of all edges in that path • To augment flow f using path P consists of modifying the flow in all edges of P as follows: ◮ let b= bottleneck of P ◮ increase the flow by b in all forward edges of P ◮ decrease the flow by b in all backward edges of P
3.
4.
ダイナミックプランニングの古典的な問題
1.重み付け間隔スケジュール
入力:開始時間、終了時間、および期間の重みを持つn間隔のセット.≪出力|Output|emdw≫:互いに重ならない最大ウェイトを持つ間隔セットのセット.Eg:解決方法:「記憶付き」の保存と再帰による解決.
int Memoized Opt(j)
if j = 0 then return(0)
else
if M[j] = "undefined" then
M[j] ← max v(j) + Opt(p(j)), Opt(j − 1)
return M[j]間隔は終了時間順に並べ替えられ、j番目の間隔の重みと、j番目の間隔と一致しない前の間隔のOpt(p(j))との和であるべきである.Opt(j-1)と等しい.中で一番大きいです.
下から上への繰返しで計算することもできます
IterativeComputeOpt
M[0] ← 0
for j ← 1 to n do
M [j] ← max v(j) + M [p(j)], M [j − 1] 2.セグメント最小二乗問題
n個の点のセットを与え、これらの点を最良にフィットさせることができる直線を決定する必要がある.error=点から直線までの距離の二乗があり、この直線は最小のerrorを有する.
複数の直線を使用すると、より良いフィットが得られますが、より多くのセグメントに分割することは、私たちのデータ分析には意味がありません.指数の異なる区分(求子集に相当)があるため、暴力的な検索は現実的ではない.
解決方法:アルゴリズムのペナルティ値として可変変数Cを導入し,分割にフィットする線が多ければ多いほどC値が大きくなる.そこで私たちの目標は、C+各線のerror値を最小限に抑えることです.定義e(i,j)はpiからpjの点にフィットするerrorである.OPT(i)はpiからpjへの最適解(OPT(0)＝0)である.次のことがわかります.
OPT(j)=e(i,j)+C+OPT(i−1)
iの値は決定できませんが、最小値を与えるiの値を選択できます.
OPT(j)=min1≤i≤j(e(i,j)+C+OPT(i−1))
これにより、擬似コードを得ることができます.
各点のセグメント最小二乗のerror値を計算し、配列に格納した後、配列を巡回して最適なフィット線を得る.
SegmentedLeastSquares(n)
Array M[0...n]
M[0] ← 0
for all pairs (i, j)
compute least squares error[i, j] for segment pi . . . pj
for j ← 1 to n
M [j ] ← min1≤i≤j (error[i, j ] + C + M [i − 1] )
Find Segments(j)
find i that minimizes error[i,j]+C+M[i−1]
if i > 1 then Find Segments(i − 1)
output the best fit line for segment pi...pj
3.自動車積載問題
できるだけ多くの貨物を自動車に積むことを要求する.入力:n個の箱、各箱iに重量wiがある;自動車の総荷重はWである.出力:総重量制限を満たす下で、できるだけ多くの積載重量を満たす箱のサブセット.
解決方法:明らかに,この場合,貪欲アルゴリズムは最適解を与えることができない.例えば、自動車の総荷重は10で、4つの箱があり、それぞれ重量は8、3、3、3である.最適解は9ですが、欲張りは重さ8の箱を選ぶだけです.
箱の数を減らし、総重量制限を減らすことで、問題をより小さな問題に解消することができます.私はOPT(i,w)で私たちが重量制限wの条件の下で、前のiつの箱の中で積載できる最大重量を表します.
i番目の箱の場合、マウントするか、マウントしないかを選択できます.
OPT(i,w)=max(wi+OPT(i−1,w−wi),OPT(i−1,w))
wiはwより大きくすることはできません.そうしないと、箱iを積まないことしか選択できません.このアルゴリズムには時間的複雑さ:O(n・W)がある.
4.バックパック問題(Knapsack Problem)
入力:n件の物品、物品iは重量wiと価値viがあります;リュック総重量W.出力:総重量制限を満たす最大価値のあるアイテムのセット.
解決方法:このとき貪欲も最適解を得ることができず、例えばW=100で、2つの品物があり、重量と価値はそれぞれ(20,80)、(90,90)であり、このとき貪欲は最小重量を選択するが、リュックサックはもう入れられない.
リュックサックの問題は、価値を導入したトラックの積載問題のようなものだ.OPT(i,w)は、前のi品のうち、w重量制限下で得られる最大価値を示す.私たちはこの品物を選ぶことができます.
OPT(i,w)=max(vi+OPT(i−1,w−wi),OPT(i−1,w))
wiはwより大きくしてはならない.そうしないと、物品iを積まないことしか選択できない.このアルゴリズムには時間的複雑さ:O(n・W)がある.
4.シーケンス比較(Sequence Alignment)
2つのシーケンス間の類似性を決定するために,2つのstringを一定の法則に従って配列した.シーケンスには間隔を挿入することでより良い類似性を得ることができるが,gapとmismatchにはcostを持つ異なる罰則値を割り当てる.2つのstringを与えて、それらの間の類似度の解決方法を計算します:2つのstringをxとyにして、私達はA(i,j)にx 1からxiに対して、y 1からyjの最適な整合値、すなわち最小のgapとmismatchの懲罰値を表します.疑似コード:
ALIGN( X[1:m],Y[1:n] )
for j ← 0 to n
A[0,j] ← jδ
for i ← 1 to m
A[i, 0] ← iδ
for j ← 1 to n
A[i,j]←min{αxi,yj +A[i−1,j−1], δ+A[i−1,j],
δ+A[i,j−1] }5.負のエッジを持つ最短パス(Bellman-Ford Shorest Path Algorithm)
入力:重み付き図G,c(v,w)は頂点vからwまでのエッジを表すcostであり、負であってもよい.出力:負のループ(すべてのエッジのcostの和が負)またはsからtまでの最短パス.
実際の生活では,例えば経済学における相互振り替えは負のエッジを導入する可能性があるが,Dijkstraアルゴリズムは制限されており,解決できない.この場合、Bellman-Ford Shortest Path Algを使用する必要があります.使用前に、図に負のループがない場合、n個の点を持つ図Gに対して、点sからtまでの最短経路がn-1個のエッジを多く含むという定理を知る必要があります.
解決方法:OPT(i,v)をi辺以下の場合、点vから点tまでの最小path costを表す.我々が求めているのはOPT(n−1,s)であり,再帰初期条件OPT(0,t)＝0,OPT(0,v)＝＋∞(v!＝t)がある.疑似コード:
Shortest-Path(G, s, t)
n ← number of nodes in G
for all v except t, initialize M[v] ← +∞
M[t] ← 0
for i←1 to n−1
for all e=(v,w)∈E(G)
M [v] ← min(M [v], c(v, w) + M [w])
return M[s]OPT(i,v)を計算し,エッジ(v,w)が存在する点のみをとることで,時間的複雑度をO(m・n)に低減できる.
参照先:https://www.zhihu.com/question/23995189