私は最適化問題を解いており、特にフロー ネットワークを最大化する必要があります。Sedgewick の本「Algorithms in Java, Third Edition, Part 5: Graph Algorithms」に掲載されている次のJava コードに基づいて、C++ コード ベースのフロー最大化アルゴリズムを実装しました。これは、頂点ベースの PREFLOW を使用してネットワーク フローを最大化します。プッシュ アルゴリズム:
class NetworkMaxFlow
{ private Network G; private int s, t;
private int[] h, wt;
private void initheights()
NetworkMaxFlow(Network G, int s, int t)
{ this.G = G; this.s = s; this.t = t;
wt = new int[G.V()]; h = new int[G.V()];
initheights();
intGQ gQ = new intGQ(G.V());
gQ.put(s); wt[t] = -(wt[s] = Edge.M*G.V());
while (!gQ.empty())
{ int v = gQ.get();
AdjList A = G.getAdjList(v);
for (Edge e = A.beg(); !A.end(); e = A.nxt())
{ int w = e.other(v), cap = e.capRto(w);
int P = cap < wt[v] ? cap : wt[v];
if (P > 0 && v == s || h[v] == h[w]+1) // first observation (see below)
{ e.addflowRto(w, P);
wt[v] -= P; wt[w] += P;
if ((w != s) && (w != t)) gQ.put(w); // enqueue w if it is not source or sink
}
}
if (v != s && v != t && wt[v] > 0) // why check v != t if t never enter the queue?
{ h[v]++; gQ.put(v); }
}
}
}
私の実装は、そのコードに基づいて、次のネットワークを最大化できません
実行後のフローは次のよう
になります
この
フローでは、フローの値は 8 ですが、最大値は 9 です。
私の理解では、アルゴリズムは本の説明と一致しています。しかし、私は2つの奇妙なものを見ます
- ソースからの明示的なプリフロー フェーズはありません。これは に含まれ
while、述語P > 0 && v == sが true の場合に最初に 1 回だけ実行されます。多分これはコードを短くするために行われた - 私の理解と本書の言説によれば、シンクはキューに入ることはありません。ただし、高さが増加すると、コードは v != t であることを確認します。これには何か理由がありますか？
これは、C++ でのこのアルゴリズムの実装からの抜粋です。
template <class Net, class Q_Type> typename Net::Flow_Type
generic_preflow_vertex_push_maximum_flow(Net & net)
{
init_height_in_nodes(net); // breadth first traverse from sink to
// source. Nodes are labeled with their
// minimal distance (in nodes) to sink
auto source = net.get_source();
auto sink = net.get_sink();
using Itor = __Net_Iterator<Net>;
Q_Type q; // generic queue (can be fifo, heap or random) of active nodes
// preflow: floods all nodes connected to the source
for (Itor it(source); it.has_curr(); it.next())
{
auto arc = it.get_curr();
arc->flow = arc->cap; // saturate arc to its maximum
auto tgt = net.get_tgt_node(arc);
put_in_active_queue(q, tgt);
assert(node_height<Net>(source) == node_height<Net>(tgt) + 1);
assert(not is_residual<Net>(source, arc));
}
while (not q.is_empty()) // while there are active nodes
{
auto src = get_from_active_queue(q);
auto excess = net.get_in_flow(src) - net.get_out_flow(src);
for (Itor it(src); it.has_curr(); it.next())
{
auto arc = it.get_curr();
auto tgt = net.get_connected_node(arc, src);
if (node_height<Net>(src) != node_height<Net>(tgt) + 1)
continue; // this arc is not eligible
typename Net::Flow_Type flow_to_push;
if (is_residual<Net>(src, arc))
{
flow_to_push = std::min(arc->flow, excess);
arc->flow -= flow_to_push;
}
else
{
flow_to_push = std::min(arc->cap - arc->flow, excess);
arc->flow += flow_to_push;
}
excess -= flow_to_push;
if (tgt != sink and tgt != source)
put_in_active_queue(q, tgt);
}
if (excess > 0) // src still active?
{
node_height<Net>(src)++;
put_in_active_queue(q, src);
}
}
return net.flow_value(); // sum of all outing flow from source
}
私のコードと Sedgewick のコードの間に論理的な矛盾を見つけた人はいますか? 私のコード (およびおそらく Sedgewick も) が高さの増加を適切に処理していないという印象があります。しかし、私はその理由を理解することができません
最大化に失敗したネットワークの詳細な実行トレースを示します (トレースは while の最初の q.get() から始まります。括弧内の値は高さの値です。IN はノードへの着信フローです。OUT は来るもの。
例として、ライン
4104 (2) --> 0 (1) pushing 1 from 4104 toward 0
適格アーク 4104-->0 を参照します。ノード４１０４の高さは２であり、ノード０の高さは１である。「１を押す」という表現は、１単位のフローが目的のノード（０）に向かって押されることを意味する。行================は、各キュー抽出を区切ります。キューは FIFO であり、その状態は各処理の最後に出力されます。
多くの場合、ゼロ フロー ユニットがプッシュまたは削減されますが、宛先ノードがアクティブになることに注意してください。
これは実行トレースです
Initial Queue = 4104 4105 4106 4107 4108
Active node 4104 Height = 2 IN = 1 OUT = 0
4104 (2) --> source (3) not eligible
4104 (2) --> 0 (1) pushing 1 from 4104 toward 0
4104 (2) --> 1 (1) pushing 0 from 4104 toward 1
4104 (2) --> 2 (1) pushing 0 from 4104 toward 2
4104 (2) --> 4 (1) pushing 0 from 4104 toward 4
Excess = 0
Queue = 4105 4106 4107 4108 0 1 2 4
================
Active node 4105 Height = 2 IN = 3 OUT = 0
4105 (2) --> source (3) not eligible
4105 (2) --> 1 (1) pushing 1 from 4105 toward 1
4105 (2) --> 4 (1) pushing 1 from 4105 toward 4
4105 (2) --> 6 (1) pushing 1 from 4105 toward 6
Excess = 0
Queue = 4106 4107 4108 0 1 2 4 6
================
Active node 4106 Height = 2 IN = 1 OUT = 0
4106 (2) --> source (3) not eligible
4106 (2) --> 1 (1) pushing 1 from 4106 toward 1
4106 (2) --> 5 (1) pushing 0 from 4106 toward 5
Excess = 0
Queue = 4107 4108 0 1 2 4 6 5
================
Active node 4107 Height = 2 IN = 1 OUT = 0
4107 (2) --> source (3) not eligible
4107 (2) --> 1 (1) pushing 1 from 4107 toward 1
4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
Excess = 0
Queue = 4108 0 1 2 4 6 5 3
================
Active node 4108 Height = 2 IN = 3 OUT = 0
4108 (2) --> source (3) not eligible
4108 (2) --> 1 (1) pushing 1 from 4108 toward 1
4108 (2) --> 2 (1) pushing 1 from 4108 toward 2
4108 (2) --> 4 (1) pushing 1 from 4108 toward 4
4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
Excess = 0
Queue = 0 1 2 4 6 5 3
================
Active node 0 Height = 1 IN = 1 OUT = 0
0 (1) --> sink (0) pushing 1 from 0 toward sink
0 (1) --> 4104 (2) not eligible
Excess = 0
Queue = 1 2 4 6 5 3
================
Active node 1 Height = 1 IN = 4 OUT = 0
1 (1) --> sink (0) pushing 2 from 1 toward sink
1 (1) --> 4105 (2) not eligible
1 (1) --> 4106 (2) not eligible
1 (1) --> 4107 (2) not eligible
1 (1) --> 4108 (2) not eligible
Excess = 2 1 goes back onto queue with label 2
Queue = 2 4 6 5 3 1
================
Active node 2 Height = 1 IN = 1 OUT = 0
2 (1) --> sink (0) pushing 1 from 2 toward sink
2 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 4 6 5 3 1
================
Active node 4 Height = 1 IN = 2 OUT = 0
4 (1) --> sink (0) pushing 2 from 4 toward sink
4 (1) --> 4105 (2) not eligible
4 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 6 5 3 1
================
Active node 6 Height = 1 IN = 1 OUT = 0
6 (1) --> sink (0) pushing 1 from 6 toward sink
6 (1) --> 4105 (2) not eligible
Excess = 0
Queue = 5 3 1
================
Active node 5 Height = 1 IN = 0 OUT = 0
5 (1) --> sink (0) pushing 0 from 5 toward sink
Excess = 0
Queue = 3 1
================
Active node 3 Height = 1 IN = 0 OUT = 0
3 (1) --> sink (0) pushing 0 from 3 toward sink
Excess = 0
Queue = 1
================
Active node 1 Height = 2 IN = 4 OUT = 2
1 (2) --> 4105 (2) not eligible
1 (2) --> 4106 (2) not eligible
1 (2) --> 4107 (2) not eligible
1 (2) --> 4108 (2) not eligible
Excess = 2 1 goes back onto queue with label 3
Queue = 1
================
Active node 1 Height = 3 IN = 4 OUT = 2
1 (3) --> 4105 (2) Reducing 1 from 1 toward 4105
1 (3) --> 4106 (2) Reducing 1 from 1 toward 4106
1 (3) --> 4107 (2) Reducing 0 from 1 toward 4107
1 (3) --> 4108 (2) Reducing 0 from 1 toward 4108
Excess = 0
Queue = 4105 4106 4107 4108
================
Active node 4105 Height = 2 IN = 3 OUT = 2
4105 (2) --> source (3) not eligible
4105 (2) --> 1 (3) not eligible
Excess = 1 4105 goes back onto queue with label 3
Queue = 4106 4107 4108 4105
================
Active node 4106 Height = 2 IN = 1 OUT = 0
4106 (2) --> source (3) not eligible
4106 (2) --> 1 (3) not eligible
4106 (2) --> 5 (1) pushing 1 from 4106 toward 5
Excess = 0
Queue = 4107 4108 4105 5
================
Active node 4107 Height = 2 IN = 1 OUT = 1
4107 (2) --> source (3) not eligible
4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
Excess = 0
Queue = 4108 4105 5 2 3 4 6
================
Active node 4108 Height = 2 IN = 3 OUT = 3
4108 (2) --> source (3) not eligible
4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
Excess = 0
Queue = 4105 5 2 3 4 6
================
Active node 4105 Height = 3 IN = 3 OUT = 2
4105 (3) --> source (3) not eligible
4105 (3) --> 1 (3) not eligible
Excess = 1 4105 goes back onto queue with label 4
Queue = 5 2 3 4 6 4105
================
Active node 5 Height = 1 IN = 1 OUT = 0
5 (1) --> sink (0) pushing 1 from 5 toward sink
5 (1) --> 4106 (2) not eligible
Excess = 0
Queue = 2 3 4 6 4105
================
Active node 2 Height = 1 IN = 1 OUT = 1
2 (1) --> sink (0) pushing 0 from 2 toward sink
2 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 3 4 6 4105
================
Active node 3 Height = 1 IN = 0 OUT = 0
3 (1) --> sink (0) pushing 0 from 3 toward sink
Excess = 0
Queue = 4 6 4105
================
Active node 4 Height = 1 IN = 2 OUT = 2
4 (1) --> 4105 (4) not eligible
4 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 6 4105
================
Active node 6 Height = 1 IN = 1 OUT = 1
6 (1) --> sink (0) pushing 0 from 6 toward sink
6 (1) --> 4105 (4) not eligible
Excess = 0
Queue = 4105
================
Active node 4105 Height = 4 IN = 3 OUT = 2
4105 (4) --> source (3) Reducing 1 from 4105 toward source
4105 (4) --> 1 (3) pushing 0 from 4105 toward 1
Excess = 0
Queue = 1
================
Active node 1 Height = 3 IN = 2 OUT = 2
1 (3) --> 4107 (2) Reducing 0 from 1 toward 4107
1 (3) --> 4108 (2) Reducing 0 from 1 toward 4108
Excess = 0
Queue = 4107 4108
================
Active node 4107 Height = 2 IN = 1 OUT = 1
4107 (2) --> source (3) not eligible
4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
Excess = 0
Queue = 4108 2 3 4 6
================
Active node 4108 Height = 2 IN = 3 OUT = 3
4108 (2) --> source (3) not eligible
4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
Excess = 0
Queue = 2 3 4 6 5
================
Active node 2 Height = 1 IN = 1 OUT = 1
2 (1) --> sink (0) pushing 0 from 2 toward sink
2 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 3 4 6 5
================
Active node 3 Height = 1 IN = 0 OUT = 0
3 (1) --> sink (0) pushing 0 from 3 toward sink
Excess = 0
Queue = 4 6 5
================
Active node 4 Height = 1 IN = 2 OUT = 2
4 (1) --> 4105 (4) not eligible
4 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 6 5
================
Active node 6 Height = 1 IN = 1 OUT = 1
6 (1) --> sink (0) pushing 0 from 6 toward sink
6 (1) --> 4105 (4) not eligible
Excess = 0
Queue = 5
================
Active node 5 Height = 1 IN = 1 OUT = 1
5 (1) --> sink (0) pushing 0 from 5 toward sink
5 (1) --> 4106 (2) not eligible
Excess = 0
Queue =