[理工] 演算法 Ford-Fulkerson

看板Grad-ProbAsk作者 (OWWWW)時間9年前 (2017/02/03 17:35), 9年前編輯推噓7(7推 0噓 26→)
留言33則, 6人參與, 最新討論串1/1
關於Ford-Fulkerson method Capacity需為有理數才求的出max flow。 （1）是否最大的capacity可以為無理數？ 我的想法是： 因每次挑路徑其流量限制在最小capacity的邊上，因此不會有無理數造成無止盡迴圈。 這樣想是否正確？ ---------------分隔-------------- 另外所有capacity乘上常數亦為原來解 （2）如果乘上無理數是否有解？ 總結1、2如果為True 給定一張圖，其中有邊之capacity為無 理數，是否'可能'存在一組min cut的解。 這敘述是否為真？ 感謝各位解惑了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.239.88 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486114514.A.529.html ※ 編輯: k1992313 (114.137.239.88), 02/03/2017 17:36:04 ※ 編輯: k1992313 (114.137.239.88), 02/03/2017 17:38:05 ※ 編輯: k1992313 (114.137.239.88), 02/03/2017 18:49:32
推
02/03 19:50, , 1F
(1)每個capacity都是有理數，相加怎麼會變成無理數呢？
02/03 19:50, 1F
→
02/03 19:50, , 2F
(1)的最後一句你是肯定句還是疑問句ㄚ？
02/03 19:50, 2F
推
02/03 19:54, , 3F
查了一下，大概的講法是：如果有irrational capacity,
02/03 19:54, 3F
→
02/03 19:54, , 4F
ford-fulkerson 會loop forever,always finding smaller
02/03 19:54, 4F
→
02/03 19:55, , 5F
and smaller augmenting path.This infinite sequence
02/03 19:55, 5F
→
02/03 19:56, , 6F
may not even converge to the maximum flow.
02/03 19:56, 6F
→
02/03 19:56, , 7F
應該就是沒法有maximum flow的意思
02/03 19:56, 7F
推
02/03 20:03, , 8F
goo.gl/4bcLyB 請參考
02/03 20:03, 8F
抱歉一些名詞打錯(1)weight改capacity (1)的最後一句是要問(2)的問題與(1)無關 關於上述的例子都是max capacity為有理數 所以才會發生無限loop(因為取到流量為無理數) 我是想問當X為無理數且最大時是否會停 ※ 編輯: k1992313 (114.137.239.88), 02/03/2017 20:30:59 ※ 編輯: k1992313 (114.137.239.88), 02/03/2017 20:36:15
推
02/03 22:27, , 9F
Ford-Fulkerson 沒有一定挑最小路徑吧
02/03 22:27, 9F
→
02/03 22:27, , 10F
Edmonds-Karp 才挑最短路徑
02/03 22:27, 10F
→
02/03 22:34, , 11F
我講的最小是指流量
02/03 22:34, 11F
※ 編輯: k1992313 (118.165.2.153), 02/03/2017 22:35:07
→
02/04 09:53, , 12F
印象中Ford–Fulkerson是隨便選可以到終點的路徑？沒有特
02/04 09:53, 12F
→
02/04 09:53, , 13F
別選哪條
02/04 09:53, 13F
推
02/04 11:15, , 14F
同上想法，且假使你說你的挑法每次都要挑最小capacity
02/04 11:15, 14F
→
02/04 11:15, , 15F
要不能保證最後加起來不會是無理數吧，這要看capacity而
02/04 11:15, 15F
→
02/04 11:15, , 16F
定
02/04 11:15, 16F
覺得說明上好像有很多誤會了，抱歉 路徑的流量被限制在路徑中最小的capacity 所以只要這些capacity為有理數即可？ 另外 舉個簡單的例子 s->a->t 如果(s,a)的capacity為10^4.2為無理數 （a,t)的capacity為10 這樣ford fulkerson也停不下來嗎 ※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:24:58 ※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:33:14 ※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:39:12 ※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:42:36
推
02/04 12:57, , 17F
假設capacity是無理數，FF可能跑不出來，一直卡在loo
02/04 12:57, 17F
→
02/04 12:57, , 18F
p裡
02/04 12:57, 18F
→
02/04 13:01, , 19F
樓上，那是因爲有取到capacity為無理數吧，假如像我舉
02/04 13:01, 19F
→
02/04 13:01, , 20F
的例子也不會停嗎
02/04 13:01, 20F
推
02/04 13:08, , 21F
如果邊是無理，augmenting path又亂取，不保証termin
02/04 13:08, 21F
→
02/04 13:08, , 22F
al
02/04 13:08, 22F
→
02/04 13:14, , 23F
可是我舉的例子應該取到路徑流量為10就停止了吧？還是
02/04 13:14, 23F
→
02/04 13:14, , 24F
有哪裡沒分析到的？
02/04 13:14, 24F
→
02/04 13:17, , 25F
你的例子10就停了
02/04 13:17, 25F
→
02/04 13:18, , 26F
你舉的例子也沒有亂取的問題存在啊
02/04 13:18, 26F
→
02/04 13:19, , 27F
或是敘述改成'如果有邊為無理數，則FFㄧ定無解'這句話就
02/04 13:19, 27F
→
02/04 13:19, , 28F
錯了？
02/04 13:19, 28F
我是因爲筆記上寫了capacity不可為無理數 覺得這句話太強烈，所以開始了這堆疑惑 ※ 編輯: k1992313 (223.137.217.9), 02/04/2017 13:21:33
→
02/06 01:48, , 29F
capacity為無理數且該條擴充流會無限取並收斂時會跑不出
02/06 01:48, 29F
→
02/06 01:48, , 30F
來
02/06 01:48, 30F
→
02/06 01:49, , 31F
有無理數時,即使是最大邊 也有可能在幾次取流後變成會無
02/06 01:49, 31F
→
02/06 01:49, , 32F
限收斂的路徑
02/06 01:49, 32F
→
02/06 01:50, , 33F
我是這樣理解的
02/06 01:50, 33F
‣ 更多 k1992313 的文章
文章代碼(AID): #1Ob4xIKf (Grad-ProbAsk)