作者jimmy1112111 (jxu)
看板Grad-ProbAsk
標題[理工] 108 交大 資演 12
時間Sun Nov 21 22:49:33 2021
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1637506175.A.E54.html
1F：→ mathtsai: 這選項是對的嗎？ 如果圖都存整數要怎麼變出小數？11/22 00:51
2F：推 VF84: 我跟樓上有一樣的疑問11/22 10:00
4F：→ jacksoncsie: 答案是可以擁有非整數的Edge，只不過現實不會用倒是11/22 10:52
5F：推 VF84: 原來如此@@11/22 11:28
6F：→ mathtsai: 喔 我大概知道了11/22 13:08
7F：→ mathtsai: 可以有非整數edge11/22 13:08
8F：→ mathtsai: （隨便畫個圖就能知道）11/22 13:08
9F：→ mathtsai: 但是肯定不是用FFA找的11/22 13:08
10F：推 joywilliamjo: E是對的吧，根據題目給的演算法，算出來只會是趨近11/22 13:57
11F：→ joywilliamjo: 整數的小數？11/22 13:57
12F：→ jimmy1112111: 感謝11/22 14:08
13F：→ mathtsai: E不用管題目的算法吧？11/22 14:24
14F：推 joywilliamjo: 他題目都跟你說consider the following proposed al11/22 15:07
15F：→ joywilliamjo: go了...11/22 15:07
16F：→ mathtsai: 題目是很像FFA 但我想不到怎麼找出小數解11/22 15:15
17F：→ mathtsai: joy你能舉個例子嗎？11/22 15:15
18F：→ mathtsai: 應該說 怎麼讓edge上出現小數11/22 15:15
19F：→ mathtsai: 你說的 趨近整數的小數 是怎麼得到的？11/22 15:17
20F：推 joywilliamjo: 喔不是，我算錯了，但假設s,t中間只有一條capacity=11/22 15:44
21F：→ joywilliamjo: 1的路徑11/22 15:44
23F：→ joywilliamjo: 這樣嗎？抱歉上面我的接近整數那個回答應該是錯的，11/22 15:45
24F：→ joywilliamjo: 但答案應該要有E11/22 15:45
25F：→ mathtsai: K = 0.5不會再進迴圈了吧11/22 15:52
26F：→ mathtsai: 我覺得 題目應該是想說augmenting path可以取小數11/22 15:54
27F：→ mathtsai: 反正他符合augmenting的規則11/22 15:54
28F：→ mathtsai: 也沒人說不能這麼做11/22 15:54
29F：→ mathtsai: 就像我上面說的那樣11/22 15:54
30F：→ mathtsai: 不然FFA實作上應該是取path上最小的edge來做11/22 15:55
31F：→ mathtsai: 這樣怎麼做都是整數 11/22 15:55
32F：→ mathtsai: 可能我題目哪邊漏看 那就再麻煩補充 11/22 15:55
33F：推 joywilliamjo: 一開始K=1的時候會進while loop然後變0.5再跳出去 11/22 16:47
34F：推 lena2689: 他是從capacity scaling algo改過來的演算法，所以加一 11/22 18:30
35F：→ lena2689: 個proposed。原版while的condition是找到沒有augmenting 11/22 18:30
36F：→ lena2689: path為止，但這個改成K>=1。所以求出的f 不一定是maxim 11/22 18:30
37F：→ lena2689: um flow，真正的maximum flow要考慮樓上講的情況。 11/22 18:30
38F：→ lena2689: 應該吧我也不確定>< 11/22 18:30
39F：→ mathtsai: 喔 我看懂joy的圖了 11/22 19:25
40F：→ mathtsai: 啊這就和我說的一樣 11/22 19:25
41F：→ mathtsai: 他augmenting path減掉的不是path上的最小edge 11/22 19:25
42F：→ mathtsai: 而是亂減一個數字 11/22 19:25
43F：→ mathtsai: 這會導致出來的結果不是maximum flow 11/22 19:26
44F：→ mathtsai: 問題是誰會這樣做XD 11/22 19:26
45F：→ lena2689: 歐歐乾抱歉我錯了QQ ，原版也是寫K>=1。 11/22 19:54
46F：→ lena2689: 跑到k=1時，就相當於FFA，所以是max flow沒錯，m大本來 11/22 19:54
47F：→ lena2689: 講得才對，選項E應該只是想講augmenting path不一定只能 11/22 19:54
49F：→ lena2689: it.edu/moitra/docs/6854lec8.pdf 11/22 19:54
50F：→ mathtsai: 講是講不一定只能整數 11/22 20:02
51F：→ mathtsai: 但是誰會沒事弄一個小數出來XDD 11/22 20:02
52F：推 joywilliamjo: 不知道，可能是出題教授的惡意？ 11/22 20:36
53F：→ jimmy1112111: 感謝以上幾位 11/22 22:26
※ 編輯: jimmy1112111 (1.200.143.31 臺灣), 11/22/2021 22:29:45