[理工] 108 交大 資演 12

看板Grad-ProbAsk作者 (jxu)時間4年前 (2021/11/21 22:49), 4年前編輯推噓9(9推 0噓 44→)
留言53則, 6人參與, 4年前最新討論串1/1
https://i.imgur.com/CU5Boiy.jpg
https://i.imgur.com/nOSpSel.jpg
想問第12題組26題的e選項(答案有e) 我沒理解錯的話，在作ford algo前會讓整個graph的edge capacity整數化，這樣才能預估a lgo完成時間，因此這個選項是說先找出max flow後會再normalize，所以有non-integral也 可以的意思嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.143.31 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1637506175.A.E54.html
→
11/22 00:51, 4年前 , 1F
這選項是對的嗎？ 如果圖都存整數要怎麼變出小數？
11/22 00:51, 1F
推
11/22 10:00, 4年前 , 2F
我跟樓上有一樣的疑問
11/22 10:00, 2F
推
11/22 10:50, 4年前 , 3F
11/22 10:50, 3F
→
11/22 10:52, 4年前 , 4F
答案是可以擁有非整數的Edge，只不過現實不會用倒是
11/22 10:52, 4F
推
11/22 11:28, 4年前 , 5F
原來如此@@
11/22 11:28, 5F
→
11/22 13:08, 4年前 , 6F
喔 我大概知道了
11/22 13:08, 6F
→
11/22 13:08, 4年前 , 7F
可以有非整數edge
11/22 13:08, 7F
→
11/22 13:08, 4年前 , 8F
（隨便畫個圖就能知道）
11/22 13:08, 8F
→
11/22 13:08, 4年前 , 9F
但是肯定不是用FFA找的
11/22 13:08, 9F
推
11/22 13:57, 4年前 , 10F
E是對的吧，根據題目給的演算法，算出來只會是趨近
11/22 13:57, 10F
→
11/22 13:57, 4年前 , 11F
整數的小數？
11/22 13:57, 11F
→
11/22 14:08, 4年前 , 12F
感謝
11/22 14:08, 12F
→
11/22 14:24, 4年前 , 13F
E不用管題目的算法吧？
11/22 14:24, 13F
推
11/22 15:07, 4年前 , 14F
他題目都跟你說consider the following proposed al
11/22 15:07, 14F
→
11/22 15:07, 4年前 , 15F
go了...
11/22 15:07, 15F
→
11/22 15:15, 4年前 , 16F
題目是很像FFA 但我想不到怎麼找出小數解
11/22 15:15, 16F
→
11/22 15:15, 4年前 , 17F
joy你能舉個例子嗎？
11/22 15:15, 17F
→
11/22 15:15, 4年前 , 18F
應該說 怎麼讓edge上出現小數
11/22 15:15, 18F
→
11/22 15:17, 4年前 , 19F
你說的 趨近整數的小數 是怎麼得到的？
11/22 15:17, 19F
推
11/22 15:44, 4年前 , 20F
喔不是，我算錯了，但假設s,t中間只有一條capacity=
11/22 15:44, 20F
→
11/22 15:44, 4年前 , 21F
1的路徑
11/22 15:44, 21F
→
11/22 15:44, 4年前 , 22F
11/22 15:44, 22F
→
11/22 15:45, 4年前 , 23F
這樣嗎？抱歉上面我的接近整數那個回答應該是錯的，
11/22 15:45, 23F
→
11/22 15:45, 4年前 , 24F
但答案應該要有E
11/22 15:45, 24F
→
11/22 15:52, 4年前 , 25F
K = 0.5不會再進迴圈了吧
11/22 15:52, 25F
→
11/22 15:54, 4年前 , 26F
我覺得 題目應該是想說augmenting path可以取小數
11/22 15:54, 26F
→
11/22 15:54, 4年前 , 27F
反正他符合augmenting的規則
11/22 15:54, 27F
→
11/22 15:54, 4年前 , 28F
也沒人說不能這麼做
11/22 15:54, 28F
→
11/22 15:54, 4年前 , 29F
就像我上面說的那樣
11/22 15:54, 29F
→
11/22 15:55, 4年前 , 30F
不然FFA實作上應該是取path上最小的edge來做
11/22 15:55, 30F
→
11/22 15:55, 4年前 , 31F
這樣怎麼做都是整數
11/22 15:55, 31F
→
11/22 15:55, 4年前 , 32F
可能我題目哪邊漏看 那就再麻煩補充
11/22 15:55, 32F
推
11/22 16:47, 4年前 , 33F
一開始K=1的時候會進while loop然後變0.5再跳出去
11/22 16:47, 33F
推
11/22 18:30, 4年前 , 34F
他是從capacity scaling algo改過來的演算法，所以加一
11/22 18:30, 34F
→
11/22 18:30, 4年前 , 35F
個proposed。原版while的condition是找到沒有augmenting
11/22 18:30, 35F
→
11/22 18:30, 4年前 , 36F
path為止，但這個改成K>=1。所以求出的f 不一定是maxim
11/22 18:30, 36F
→
11/22 18:30, 4年前 , 37F
um flow，真正的maximum flow要考慮樓上講的情況。
11/22 18:30, 37F
→
11/22 18:30, 4年前 , 38F
應該吧我也不確定><
11/22 18:30, 38F
→
11/22 19:25, 4年前 , 39F
喔 我看懂joy的圖了
11/22 19:25, 39F
→
11/22 19:25, 4年前 , 40F
啊這就和我說的一樣
11/22 19:25, 40F
→
11/22 19:25, 4年前 , 41F
他augmenting path減掉的不是path上的最小edge
11/22 19:25, 41F
→
11/22 19:25, 4年前 , 42F
而是亂減一個數字
11/22 19:25, 42F
→
11/22 19:26, 4年前 , 43F
這會導致出來的結果不是maximum flow
11/22 19:26, 43F
→
11/22 19:26, 4年前 , 44F
問題是誰會這樣做XD
11/22 19:26, 44F
→
11/22 19:54, 4年前 , 45F
歐歐乾抱歉我錯了QQ ，原版也是寫K>=1。
11/22 19:54, 45F
→
11/22 19:54, 4年前 , 46F
跑到k=1時，就相當於FFA，所以是max flow沒錯，m大本來
11/22 19:54, 46F
→
11/22 19:54, 4年前 , 47F
講得才對，選項E應該只是想講augmenting path不一定只能
11/22 19:54, 47F
→
11/22 19:54, 4年前 , 48F
整數，例如j大的圖示QQ 證明參考http://people.csail.m
11/22 19:54, 48F
→
11/22 19:54, 4年前 , 49F
it.edu/moitra/docs/6854lec8.pdf
11/22 19:54, 49F
→
11/22 20:02, 4年前 , 50F
講是講不一定只能整數
11/22 20:02, 50F
→
11/22 20:02, 4年前 , 51F
但是誰會沒事弄一個小數出來XDD
11/22 20:02, 51F
推
11/22 20:36, 4年前 , 52F
不知道，可能是出題教授的惡意？
11/22 20:36, 52F
→
11/22 22:26, 4年前 , 53F
感謝以上幾位
11/22 22:26, 53F
※ 編輯: jimmy1112111 (1.200.143.31 臺灣), 11/22/2021 22:29:45
‣ 更多 jimmy1112111 的文章
文章代碼(AID): #1Xcbn_vK (Grad-ProbAsk)