這就是在Flow Networks上找到Maximum Flow(最大流量)的問題。 以下將介紹Ford-Fulkerson Algorithm(若使用BFS搜尋路徑,又稱為Edmonds-Karp Algorithm)來回應此問題。 ... <看更多>
「ford fulkerson」的推薦目錄:
- 關於ford fulkerson 在 [理工] 演算法Ford-Fulkerson - 看板Grad-ProbAsk - 批踢踢實業坊 的評價
- 關於ford fulkerson 在 Flow Networks:Maximum Flow & Ford-Fulkerson Algorithm 的評價
- 關於ford fulkerson 在 Why is ford-fulkerson so ubiquitous? - Stack Overflow 的評價
- 關於ford fulkerson 在 prabod/Graph-Theory-Ford-Fulkerson-Maximum-Flow - GitHub 的評價
- 關於ford fulkerson 在 Finding the max flow of an undirected graph with Ford-Fulkerson 的評價
ford fulkerson 在 prabod/Graph-Theory-Ford-Fulkerson-Maximum-Flow - GitHub 的推薦與評價
Ford -Fulkerson Algorithm for Maximum Flow Problem Written in JS - GitHub - prabod/Graph-Theory-Ford-Fulkerson-Maximum-Flow: Ford-Fulkerson Algorithm for ... ... <看更多>
ford fulkerson 在 Finding the max flow of an undirected graph with Ford-Fulkerson 的推薦與評價
Yes, you should increase the capacity of reverse edge by flow sent. Each time sending some flow by edge you should update its reverse edge ... ... <看更多>
ford fulkerson 在 [理工] 演算法Ford-Fulkerson - 看板Grad-ProbAsk - 批踢踢實業坊 的推薦與評價
關於Ford-Fulkerson method
Capacity需為有理數才求的出max flow。
(1)是否最大的capacity可以為無理數?
我的想法是:
因每次挑路徑其流量限制在最小capacity的邊上,因此不會有無理數造成無止盡迴圈。
這樣想是否正確?
---------------分隔--------------
另外所有capacity乘上常數亦為原來解
(2)如果乘上無理數是否有解?
總結1、2如果為True
給定一張圖,其中有邊之capacity為無
理數,是否'可能'存在一組min cut的解。
這敘述是否為真?
感謝各位解惑了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.239.88
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486114514.A.529.html
※ 編輯: k1992313 (114.137.239.88), 02/03/2017 17:36:04
※ 編輯: k1992313 (114.137.239.88), 02/03/2017 17:38:05
※ 編輯: k1992313 (114.137.239.88), 02/03/2017 18:49:32
(1)的最後一句是要問(2)的問題與(1)無關
關於上述的例子都是max capacity為有理數
所以才會發生無限loop(因為取到流量為無理數)
我是想問當X為無理數且最大時是否會停
※ 編輯: k1992313 (114.137.239.88), 02/03/2017 20:30:59
※ 編輯: k1992313 (114.137.239.88), 02/03/2017 20:36:15
路徑的流量被限制在路徑中最小的capacity
所以只要這些capacity為有理數即可?
另外
舉個簡單的例子
s->a->t
如果(s,a)的capacity為10^4.2為無理數
(a,t)的capacity為10
這樣ford fulkerson也停不下來嗎
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:24:58
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:33:14
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:39:12
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:42:36
我是因爲筆記上寫了capacity不可為無理數
覺得這句話太強烈,所以開始了這堆疑惑
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 13:21:33
... <看更多>