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