風向郵差與混向郵差問題演算法的探討

Abstract

風向郵差問題和混向郵差問題是中國郵差問題的推廣。這兩類型郵差問題 的複雜度高，都屬於NP-complete的問題。目前有一些heuristic演算法的 提出，以polynomail-time 的求解速度而獲得近似解。在風向郵差問題方 面，如Guan[1]提出當網路滿足狀況Q(condition Q)時，使用Guan的演算 法可得最佳解，而且網路接近狀況Q(即condition Q1)時，使用Guan的演 算法所得的解有一個上界(ｓ．ε)。本論文中將證明其上界可減為原來的 一半(ｓ．ε／2)。我們並且證明在相同狀況下，多郵差風 向網路中， Pearn [4]所提出的演算法之上界為K乘以上面所證 明的風向郵差問題上 界(ｋ．ｓ．ε／2)。Pearn和Li[3]把Win的演算法步驟倒過來而獲得風向 郵差問題的近似解，稱為Reverse Win 演算法。Win[2]已經證明Win的演 算法之bound 是2，本論文也將證明Reverse Win的演算法之bound也是2。 在混向郵差問題方面，有Mixed-I演算法、Mixed-II 演算法，以及混合策 略等。Frederickson[9]已經證明Mixed-I演算法之bound是2、Mixed-II 演算法之bound也是2且兩者的混合策略之bound是5/3。本論文將證明此混 合策略之bound可減為3/2。 The Chinese postman problem on windy networks (WPP) or mixed networks (MCPP), is an interesting generalization of the classical Chinese postman problem (CPP), which has been shown to be NP-complete. Therefore, it is difficult to solve these problems exactly. For this reason, heuristic solution procedures have been proposed to solve these problems approximately. In WPP, Guan [1] proposed an algorithm which solves the WPP optimally if the network satisfies certain conditions. Guan showed that if those conditins are nearly satisfied, then his solution has a tight worst case bound. In this thesis, we show that under the same conditions, the worst-case bound can be reduced. We also showed that for k-vehicle extension of the WPP, the algorithm proposed by Pearn [4] generates a solution which has a worst-case bound equaling to k times the reduced bound for the WPP. Pearn and Li [3] proposed a new solution procedure, called the Reverse-Win's algorithm, to solve the WPP approximately. The Reverse-Win's algorithm is essentially the reverse procedure of the two-phase algorithm developed by Win [2 ], with some modifications. In this thesis, we showed that the performance of the Reverse Win's algorithm, in the worst case, is bounded by two, and the bound is approachable. In MCPP, Frederickson [9] showed that the performance of the Mixed-I algorithm has a worst-case bound of 2, the performance of the Mixed-II algorithm has a worst-case bound of 2, and the performance of the mixed-strategy algorithm with respect to Mixed-I algorithm and Mixed-II algorithm has a worst-case bound of 5/3. In this thesis, we show that the worst-case bound of the mixed-strategy approach can be reduced to 3/2.