作者GoalBased (Artificail Intelligence)
看板Prob_Solve
標題[問題] Ford-Fulkerson algorithm
時間Sun Jan 13 22:00:39 2013
大家好，最近在學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
1F：推 suhorng:s -> 3 -> 5 -> 4 -> t 中經過的殘餘容量是 01/13 22:57
2F：→ suhorng: 10 7 6 10 01/13 22:58
3F：→ suhorng:裡面最小的是 5 -> 4 的 6. 他說的最小是這個 01/13 22:58
4F：→ suhorng:你看 5->4 那一條的箭頭特別粗 01/13 22:59
5F：→ tkcn:你記錯前提了，Ford-Fulkerson 沒有要求要最小的那條 01/13 23:00
6F：→ tkcn:看了樓上才知道原來誤會是在那裡 :p 01/13 23:03
7F：→ GoalBased:那請問可以走我說的那一條嗎? 01/13 23:11
8F：→ GoalBased:經過1F的說明，我現在的認知是，只要任選一條走S到T 01/13 23:12
9F：→ GoalBased:那一條路徑的流量是當中最小的就可以了? 01/13 23:13
10F：→ GoalBased:那另外請問，這個例子當中的，min cut是否是指 01/13 23:16
11F：→ tkcn:可以，但你上面這句應該是錯的。 01/13 23:17
12F：→ GoalBased:找出max flow之後，s點還可以走到3，而s和3連接到其他 01/13 23:17
13F：→ GoalBased:的點所構成的邊就是min cut 01/13 23:17
14F：→ tkcn:最小是指,path可增加的流量,是所有經過edge中剩餘流量最小的 01/13 23:18
15F：→ GoalBased:也就是S到2和3到5 這兩條? 01/13 23:18
16F：→ GoalBased:t大我解你所說的，我上面用字不精確造成誤會 01/13 23:19
17F：→ tkcn:正確 01/13 23:25
18F：→ GoalBased:相當感謝 01/13 23:26