作者dsa66253 (Kobe Mary)
看板Grad-ProbAsk
标题[理工] 100交大 资演maxflow loop invariant
时间Mon Dec 30 19:11:36 2019
https://i.imgur.com/Mx5uZMY.jpg
请问一下57 bc是什麽意思
https://i.imgur.com/8cYAt8o.jpg
Loop invariant这张出现两次 也查询过loop invairant说是loop前中後都不会改变的式
子？
但这题还是不知道在干嘛......
麻烦板上大神帮帮忙了 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 150.117.242.146 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577704298.A.C3A.html
1F：推 mi981027: 57 b 任何flow的流量|f| 一定小於等於任何cut的容量c(S, 12/30 19:41
2F：→ mi981027: T) 12/30 19:41
3F：→ mi981027: 所以若有flow的流量刚好等於某个cut的容量 他一定是max 12/30 19:41
4F：→ mi981027: flow 12/30 19:41
5F：→ mi981027: c 他的意思是flow的流量会被多少cut set bounded 我的想 12/30 19:41
6F：→ mi981027: 法是 12/30 19:41
7F：→ mi981027: cut set的定义必须分开s跟t，那假设有n个点，扣掉s, t 12/30 19:44
8F：→ mi981027: 剩n-2个点 12/30 19:44
9F：→ mi981027: 每个点都可以选择要分在S或T 总共的分法是2^{n-2}种 12/30 19:44
10F：→ mi981027: 所以应该是O(2^n)?? 12/30 19:44
11F：推 mi981027: loop invariant应该要解释成：某个statement 不论loop 12/30 20:01
12F：→ mi981027: 执行到什麽阶段 这个statement都为真 这样会比较好理解 12/30 20:01
13F：→ mi981027: 其实这边他就是要考辗转相除法的原理是什麽 12/30 20:01
14F：→ mi981027: 也就是gcd(m,n) = gcd(n,r) 12/30 20:01
15F：→ mi981027: 对应到42就是A选项 因为这是一个定理 所以不论loop到什 12/30 20:01
16F：→ mi981027: 麽阶段、m, n的值是什麽 都不会改变这个statement的正确 12/30 20:01
17F：→ mi981027: 性 所以他是这里的loop invariant 12/30 20:01
18F：→ mi981027: loop invariant可以用来验证algorithm的正确性 可以这 12/30 20:01
19F：→ mi981027: 样验证 12/30 20:01
21F：推 plsmaop: CLRS 第一章还是第二章有解释什麽是 loop invariant 12/31 07:53