[理工] 交大 演算法消失

看板Grad-ProbAsk作者時間7年前 (2017/02/08 15:34), 編輯推噓4(4推 0噓 32→)
留言36則, 6人參與, 最新討論串1/1
http://i.imgur.com/V4cGwec.jpg
題組六，知道edmonds-karp algo是透過BFS去改善FF 的方法 但first ,second,third....... iteration要怎麼做? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.235.245 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486539291.A.ED4.html
→
02/08 15:44, , 1F
路徑短的先挑
02/08 15:44, 1F
→
02/08 15:54, , 2F
你都知道要用BFS了就用BFS先找路徑阿..
02/08 15:54, 2F
→
02/08 16:02, , 3F
本魯愚笨，不知道過程，有大大可以寫出完整的解題過
02/08 16:02, 3F
→
02/08 16:02, , 4F
程嗎QQQQ
02/08 16:02, 4F
→
02/08 16:05, , 5F
14題前兩個iteration做完之後要把他們的flow扣掉喔
02/08 16:05, 5F
→
02/08 16:05, , 6F
我對的答案14題是C耶
02/08 16:05, 6F
→
02/08 16:06, , 7F
這樣第15題跑第三個iteration的時候就會選到SCDEGT了
02/08 16:06, 7F
→
02/08 16:08, , 8F
其實我覺得第14題C跟D都有可能耶@@端看BFS怎麼選點
02/08 16:08, 8F
→
02/08 16:08, , 9F
也就是for each v 屬於G.adj[u]的時候，哪個v先出現，
02/08 16:08, 9F
→
02/08 16:08, , 10F
先被放到queue裡面
02/08 16:08, 10F
推
02/08 16:09, , 11F
D的話 H到T會爆吧
02/08 16:09, 11F
→
02/08 16:11, , 12F
5 > 4，是不是我誤會了什麼QQ
02/08 16:11, 12F
→
02/08 16:15, , 13F
沒事了 跟C搞混一直帶2想說不夠哈哈
02/08 16:15, 13F
→
02/08 16:16, , 14F
我是先畫BFS-tree, s-t有兩條一樣長 選容量大的
02/08 16:16, 14F
→
02/08 16:16, , 15F
然後配合擴充路徑流量圖找 就是c
02/08 16:16, 15F
推
02/08 16:18, , 16F
如果是選容量大的話那的確會是C
02/08 16:18, 16F
→
02/08 16:20, , 17F
想了一下應該要選容量大的, 因為小的可能會是bottleneck
02/08 16:20, 17F
→
02/08 16:21, , 18F
選大的就算是該條的bottleneck也不影響比另一條大
02/08 16:21, 18F
→
02/08 16:24, , 19F
想辦法一次給他流多一點流量就對了
02/08 16:24, 19F
→
02/08 16:25, , 20F
wiki舉的例子倒是選流量小的，但我認為你說的有道理
02/08 16:25, 20F
→
02/08 16:26, , 21F
一次流多一點流量感覺可以少做一點
02/08 16:26, 21F
→
02/08 16:45, , 22F
他的想法好像是盡量減少增廣路徑的選擇
02/08 16:45, 22F
→
02/08 16:50, , 23F
有點不懂，一開始選大不是s直接就接c嗎？
02/08 16:50, 23F
→
02/08 16:53, , 24F
從BFS-tree上找出s-t最短路徑來當支流
02/08 16:53, 24F
→
02/08 16:54, , 25F
題目上有兩條, 直覺上我是選大的來擴充
02/08 16:54, 25F
→
02/08 16:54, , 26F
不過wiki是給小的
02/08 16:54, 26F
→
02/08 16:55, , 27F
yellow大這樣講也對耶@@改變策略，選比較上面的(誤)
02/08 16:55, 27F
→
02/08 16:56, , 28F
ㄟㄟ我覺得我自己在做題目的時候真的會習慣選上面的耶!
02/08 16:56, 28F
→
02/08 17:10, , 29F
答案有點微妙, 先找c應該也符合
02/08 17:10, 29F
→
02/08 17:10, , 30F
這樣就變成要用選項看取法的可能性了@@
02/08 17:10, 30F
推
02/08 17:55, , 31F
這題答案不是C嗎?
02/08 17:55, 31F
→
02/08 18:20, , 32F
cd都符合吧…題目也沒說按順序
02/08 18:20, 32F
推
02/08 23:54, , 33F
02/08 23:54, 33F
→
02/08 23:54, , 34F
想問一下，筆記上面說選最小的path，這個最小是什麼意思
02/08 23:54, 34F
→
02/08 23:54, , 35F
呢？
02/08 23:54, 35F
→
02/09 00:10, , 36F
BFS找的最短路徑
02/09 00:10, 36F
‣ 更多 yellow60127 的文章
文章代碼(AID): #1OcieRxK (Grad-ProbAsk)