作者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/cn.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