Download presentation
Presentation is loading. Please wait.
1
複習 2013/12/24 Jehn-Ruey Jiang 江振瑞
2
近似演算法 (Approximation algorithm) on Dec. 10, 2013
我們介紹了NP-hard問題 此類問題可以使用最差狀況下時間複雜度為指數函數的演算法來解決 可改用最差狀況下時間複雜度為多項式函數的近似演算法(approximation algorithm)以近似比例界(approximation ratio bound) ( 1)來解決之 我們已經介紹了一些解決以下問題的近似演算法 頂點覆蓋問題(Vertex Cover Problem) 裝箱問題(Bin Packing Problem)
3
－ 符合三角不等式旅行銷售員問題 (TSP with triangular inequality) 2-近似TSP演算法 － 歐幾里德旅行銷售員問題(ETSP) (3/2)-近似ETSP演算法： 步驟1：對於給定的包含n個平面點的集 合S，找出其MST，設其為T。
4
步驟2：對於T中奇數相鄰數的節點，找 出其最小歐氏權重配對(Minimum Euclidean Weighted Matching) M，並令G=TM。 步驟3：找出G的尤拉迴圈(Eulerian cycle) G的漢彌爾頓迴圈(Hamiltonian cycle) ETSP的一個可行解，其權重至多為最佳解的(3/2) 藉由跳過(bypass)先前走訪過的節點 來遍訪(traverse)G
5
匈牙利演算法(Hungarian Algorithm)可用於解決
－指派問題(Assignment Problem) －最大權重完美二分匹配問題 (Maximum Weight Perfect Bipartite Matching Problem) 福特-弗克森演算法(Ford-Fulkerson Algorithm)與艾德蒙-卡普演算法(Edmons-Karp Algorithm)可以用於解決最大流量問題(Maximum Flow Problem)
Similar presentations
