[問題] 匈牙利演算法的複雜度
看板Prob_Solve (計算數學 Problem Solving)作者sandy4444 (質樸)時間11年前 (2014/06/11 17:03)推噓2(2推 0噓 2→)留言4則, 2人參與討論串1/1
剛剛學玩學會用來解決二分圖的max cost perfect matching
的匈牙利演算法
複雜度有 O(n^4) 和 O(n^3)(比較難用)
使用過程很漂亮
但是跟其他求 max cost perfect matching 在複雜度和效率比較
是否弱很多
把二分圖轉換成 s-t flow
用每次找 最短 augment path 的方法算出來的在速度上還弱(O(n^3))
所以想問的是在慢一個維度下
為什麼大家這麼愛匈牙利演算法???
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.69.191.1
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1402477415.A.014.html
推
06/11 21:51, , 1F
06/11 21:51, 1F
→
06/11 21:58, , 2F
06/11 21:58, 2F
→
06/11 21:58, , 3F
06/11 21:58, 3F
推
06/11 22:14, , 4F
06/11 22:14, 4F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
