[理工] 100交大 資演maxflow loop invariant

看板Grad-ProbAsk作者 (Kobe Mary)時間6年前 (2019/12/30 19:11), 編輯推噓3(3推 0噓 18→)
留言21則, 2人參與, 6年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1577704298.A.C3A.html
推
12/30 19:41, 6年前 , 1F
57 b 任何flow的流量|f| 一定小於等於任何cut的容量c(S,
12/30 19:41, 1F
→
12/30 19:41, 6年前 , 2F
T)
12/30 19:41, 2F
→
12/30 19:41, 6年前 , 3F
所以若有flow的流量剛好等於某個cut的容量 他一定是max
12/30 19:41, 3F
→
12/30 19:41, 6年前 , 4F
flow
12/30 19:41, 4F
→
12/30 19:41, 6年前 , 5F
c 他的意思是flow的流量會被多少cut set bounded 我的想
12/30 19:41, 5F
→
12/30 19:41, 6年前 , 6F
法是
12/30 19:41, 6F
→
12/30 19:44, 6年前 , 7F
cut set的定義必須分開s跟t，那假設有n個點，扣掉s, t
12/30 19:44, 7F
→
12/30 19:44, 6年前 , 8F
剩n-2個點
12/30 19:44, 8F
→
12/30 19:44, 6年前 , 9F
每個點都可以選擇要分在S或T 總共的分法是2^{n-2}種
12/30 19:44, 9F
→
12/30 19:44, 6年前 , 10F
所以應該是O(2^n)??
12/30 19:44, 10F
推
12/30 20:01, 6年前 , 11F
loop invariant應該要解釋成：某個statement 不論loop
12/30 20:01, 11F
→
12/30 20:01, 6年前 , 12F
執行到什麼階段 這個statement都為真 這樣會比較好理解
12/30 20:01, 12F
→
12/30 20:01, 6年前 , 13F
其實這邊他就是要考輾轉相除法的原理是什麼
12/30 20:01, 13F
→
12/30 20:01, 6年前 , 14F
也就是gcd(m,n) = gcd(n,r)
12/30 20:01, 14F
→
12/30 20:01, 6年前 , 15F
對應到42就是A選項 因為這是一個定理 所以不論loop到什
12/30 20:01, 15F
→
12/30 20:01, 6年前 , 16F
麼階段、m, n的值是什麼 都不會改變這個statement的正確
12/30 20:01, 16F
→
12/30 20:01, 6年前 , 17F
性 所以他是這裡的loop invariant
12/30 20:01, 17F
→
12/30 20:01, 6年前 , 18F
loop invariant可以用來驗證algorithm的正確性 可以這
12/30 20:01, 18F
→
12/30 20:01, 6年前 , 19F
樣驗證
12/30 20:01, 19F
→
12/30 20:02, 6年前 , 20F
12/30 20:02, 20F
推
12/31 07:53, 6年前 , 21F
CLRS 第一章還是第二章有解釋什麼是 loop invariant
12/31 07:53, 21F
‣ 更多 dsa66253 的文章
文章代碼(AID): #1U2Tjgmw (Grad-ProbAsk)