Posted by: smallonely | January 5, 2004

[algo] Push-relable algorithms

Preflow 是一個有趣的方法, 他允許流進的量比流出的量還要多
有水來就先流進來, 流不出去再說…

我們先假定一個高度函數 h,
他代表這個點的高度, 只有 h 比較高的點才能夠將水流到 h 比較低的點

1. 在程式一開始的時候, 讓 source 的高度是 n (node數), 其他點的高度都是 0
這樣 source node 才有足夠的高度可以流往其他地方

2. 然後 s 往其他所有跟他直接相鄰的 node, 都流 水管寬度的水量
所以現在 s 直接相鄰的每一個點都有很多水了….

(流過去之後當然要計算剩下的網路情形, 即計算 residual edges )

3. (以下是迴圈)
將所有 active node (他是有水的 node) 做 relabel 的動作,
在當某個 node 明明有水, 但是他所連出去的所有對象的高度都比他還高,
則讓他的高度增加為至少有一條水管可以流出去的量
也就是讓這個有水的 active node的高度變成 比他連往的 “高度最小的 node +1 “
(流過去之後還是要計算剩下的網路情形)

4. Push -> 從 u 到 v 丟一點水過來
當某個 node 有水, 並且他有可以流出去的邊,
且他剛好比可以流出去的那個點高度高一點點 (高度恰好比他高 1)
那就把某個 node 的水流過去
要流多少呢?以下兩者取 min
– 流出去的水管的量
(也就是說, 在這個active node的水量很多, 足夠把這條水管塞滿(飽和),
這個時候就叫做 saturating push )
– 某個 node 現在的水量
(這個node的水量不足以把流出去的這個水管填滿, 所以是
non-saturating push )

5. Repeat Relabel 和 Push 的工作, 一直到沒有 active node 為止

mapping 到 algo 講義,
某個 node 的水量 -> e[v]

應該是這樣, 有錯請指正🙂

此處 Push-Relable algorithm 一定會找到最大流量,
當以上演算法停止的時候, 他的 preflow 一定就是 max flow

-> Push-Relable algo 什麼時候會停?
只要有 overflow 的時候他就可以做 Push 或 relable (Lemma 15)
也就是說, 只要某個 node 有水, 並且有邊可以流出去的時候,
那麼他就可以做 push 或 relable 的動作,
可以 push 就 push,
不能 push 就把高度升高為可以流出去(relable), 然後 push :p
當他沒有 overflow 的時候, 得到的值就是 max flow

※ 引述《truckski (我好想要馬子小組.x)》之銘言:
> ※ 引述《smallonely.bbs@babyinn.twbbs.org ( 乖寶寶聯盟 )》之銘言:
> > 我好像有點看懂了… @_@”
> > 哦哦哦….
> 那看來我明天是要問你了@@


在這幸福即將終結的最後浪漫年代裡,
我們的相遇方式如同一首詩最關鍵的句子,帶動情緒前往夢想的領土。

夫兵者不祥之器物或惡之故有道者不處君子居則貴左用兵則貴右兵者不祥之器非君子
之器不得已BBS telnet://wretch.twbbs.org 開個人板 超快 不用連署得志於天下
矣吉事尚左凶事尚右偏將軍居左上將軍居右言以喪禮處之殺人之眾以哀悲泣之戰勝以
喪禮處之道常無名樸雖小天下莫能臣侯王若能守之萬物將自賓天地相合以降甘露民莫
之令而自均始制有名名亦既有夫亦將知止知止可以不殆 alumni.csie.nctu.edu.tw海






—–


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: