PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] Ford-Fulkerson algorithm

看板Prob_Solve (計算數學 Problem Solving)作者 (Artificail Intelligence)時間12年前 (2013/01/13 22:00), 編輯推噓1(1推 0噓 17→)
留言18則, 3人參與, 最新討論串1/1
大家好，最近在學Maximum Flow時學到這個演算法， 這個演算法說到，在每次更新路徑(流量)的時候， 要選擇最最小的那一條，我看了手邊的範例， 無法理解他所說的最小的那一條是怎麼算出來的， http://tinyurl.com/azefzfp 這個是我在網路上找到的一個範例投影片， 第五頁的部分，他的選擇是 s -> 3 -> 5 -> 4 -> t 流量是6 為什麼不選擇 s -> 3 -> 2 -> 4 -> t 流量是2呢? 謝謝 -- ‧Simple reflex agent ‧Model-based reflex agent ‧Goal-based agent ‧Utility-based agent -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.182.131
推
01/13 22:57, , 1F
s -> 3 -> 5 -> 4 -> t 中經過的殘餘容量是
01/13 22:57, 1F
→
01/13 22:58, , 2F
10 7 6 10
01/13 22:58, 2F
→
01/13 22:58, , 3F
裡面最小的是 5 -> 4 的 6. 他說的最小是這個
01/13 22:58, 3F
→
01/13 22:59, , 4F
你看 5->4 那一條的箭頭特別粗
01/13 22:59, 4F
→
01/13 23:00, , 5F
你記錯前提了，Ford-Fulkerson 沒有要求要最小的那條
01/13 23:00, 5F
→
01/13 23:03, , 6F
看了樓上才知道原來誤會是在那裡 :p
01/13 23:03, 6F
→
01/13 23:11, , 7F
那請問可以走我說的那一條嗎?
01/13 23:11, 7F
→
01/13 23:12, , 8F
經過1F的說明，我現在的認知是，只要任選一條走S到T
01/13 23:12, 8F
→
01/13 23:13, , 9F
那一條路徑的流量是當中最小的就可以了?
01/13 23:13, 9F
→
01/13 23:16, , 10F
那另外請問，這個例子當中的，min cut是否是指
01/13 23:16, 10F
→
01/13 23:17, , 11F
可以，但你上面這句應該是錯的。
01/13 23:17, 11F
→
01/13 23:17, , 12F
找出max flow之後，s點還可以走到3，而s和3連接到其他
01/13 23:17, 12F
→
01/13 23:17, , 13F
的點所構成的邊就是min cut
01/13 23:17, 13F
→
01/13 23:18, , 14F
最小是指,path可增加的流量,是所有經過edge中剩餘流量最小的
01/13 23:18, 14F
→
01/13 23:18, , 15F
也就是S到2和3到5 這兩條?
01/13 23:18, 15F
→
01/13 23:19, , 16F
t大我解你所說的，我上面用字不精確造成誤會
01/13 23:19, 16F
→
01/13 23:25, , 17F
正確
01/13 23:25, 17F
→
01/13 23:26, , 18F
相當感謝
01/13 23:26, 18F
‣ 更多 GoalBased 的文章
文章代碼(AID): #1GyhuCa2 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 GoalBased 的文章
文章代碼(AID): #1GyhuCa2 (Prob_Solve)