作者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/m.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