[理工] 108 交大 資演 12

[jimmy1112111 (jxu)]

 
 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
→ mathtsai: 這選項是對的嗎？ 如果圖都存整數要怎麼變出小數？
推 VF84: 我跟樓上有一樣的疑問
推 jacksoncsie: https://reurl.cc/xEb0NN
→ jacksoncsie: 答案是可以擁有非整數的Edge，只不過現實不會用倒是
推 VF84: 原來如此@@
→ mathtsai: 喔 我大概知道了
→ mathtsai: 可以有非整數edge
→ mathtsai: （隨便畫個圖就能知道）
→ mathtsai: 但是肯定不是用FFA找的
推 joywilliamjo: E是對的吧，根據題目給的演算法，算出來只會是趨近
→ joywilliamjo: 整數的小數？
→ jimmy1112111: 感謝
→ mathtsai: E不用管題目的算法吧？
推 joywilliamjo: 他題目都跟你說consider the following proposed al
→ joywilliamjo: go了...
→ mathtsai: 題目是很像FFA 但我想不到怎麼找出小數解
→ mathtsai: joy你能舉個例子嗎？
→ mathtsai: 應該說 怎麼讓edge上出現小數
→ mathtsai: 你說的 趨近整數的小數 是怎麼得到的？
推 joywilliamjo: 喔不是，我算錯了，但假設s,t中間只有一條capacity=
→ joywilliamjo: 1的路徑
→ joywilliamjo: https://i.imgur.com/rMoGm7x.jpg
→ joywilliamjo: 這樣嗎？抱歉上面我的接近整數那個回答應該是錯的，
→ joywilliamjo: 但答案應該要有E
→ mathtsai: K = 0.5不會再進迴圈了吧
→ mathtsai: 我覺得 題目應該是想說augmenting path可以取小數
→ mathtsai: 反正他符合augmenting的規則
→ mathtsai: 也沒人說不能這麼做
→ mathtsai: 就像我上面說的那樣
→ mathtsai: 不然FFA實作上應該是取path上最小的edge來做
→ mathtsai: 這樣怎麼做都是整數
→ mathtsai: 可能我題目哪邊漏看 那就再麻煩補充
推 joywilliamjo: 一開始K=1的時候會進while loop然後變0.5再跳出去
推 lena2689: 他是從capacity scaling algo改過來的演算法，所以加一
→ lena2689: 個proposed。原版while的condition是找到沒有augmenting
→ lena2689:  path為止，但這個改成K>=1。所以求出的f 不一定是maxim
→ lena2689: um flow，真正的maximum flow要考慮樓上講的情況。
→ lena2689: 應該吧我也不確定><
→ mathtsai: 喔 我看懂joy的圖了
→ mathtsai: 啊這就和我說的一樣
→ mathtsai: 他augmenting path減掉的不是path上的最小edge
→ mathtsai: 而是亂減一個數字
→ mathtsai: 這會導致出來的結果不是maximum flow
→ mathtsai: 問題是誰會這樣做XD
→ lena2689: 歐歐乾抱歉我錯了QQ ，原版也是寫K>=1。
→ lena2689: 跑到k=1時，就相當於FFA，所以是max flow沒錯，m大本來
→ lena2689: 講得才對，選項E應該只是想講augmenting path不一定只能
→ lena2689: 整數，例如j大的圖示QQ  證明參考http://people.csail.m
→ lena2689: it.edu/moitra/docs/6854lec8.pdf
→ mathtsai: 講是講不一定只能整數
→ mathtsai: 但是誰會沒事弄一個小數出來XDD
推 joywilliamjo: 不知道，可能是出題教授的惡意？
→ jimmy1112111: 感謝以上幾位
※ 編輯: jimmy1112111 (1.200.143.31 臺灣), 11/22/2021 22:29:45