作者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