ZH算法的性質及一種新視角分析

李鵬坤+姜新文+蓋方宇

摘 要：文獻[1]提出的MSP問題是一個NP完全問題。為了求解MSP問題，文獻[1]給出了ZH算法。本文以ZH算法為研究對象，剖析ZH算法主要過程，從新的角度解讀其作用，給出并證明ZH算法的兩條重要性質——頂點邊集守恒性質和頂點邊集存在性質。對算法過程和作用的新視角分析為MSP問題的研究提供重要參考，ZH算法的重要性質也為算法的正確性證明提供幫助。

關鍵詞：MSP問題；ZH算法；算法分析；算法性質

中圖分類號：TP301.6 文獻標識碼：A

Abstract：Jiang（2016） proposed Z-H Algorithm to solve MSP Problem. This paper analyzed the main process of Z-H Algorithm， interpreted its role from a new perspective and put forward two important properties of Z-H Algorithm. The analysis from a new angle provided an important reference for the research of MSP Problem， and the properties of Z-H Algorithm also assisted to prove the correctness of the algorithm.

Key words：MSP Problem； Z-H Algorithm； algorithm analysis； algorithm properties

1引言

NP完全問題是理論計算機科學領域的重要研究課題。文獻[1]提出的MSP問題是一個NP完全問題。在文獻[1]中，作者給出了求解MSP問題的多項式時間算法以及關于算法正確性的證明，該問題對于NP完全問題的研究具有重要意義。本文對MSP問題求解算法ZH算法進行深入分析，從新的視角解讀該算法，分析算法主要執行過程，并指出算法本身具有的一些重要性質。這種新視角的分析以及算法的性質，能夠使研究人員更好的理解MSP問題及其求解算法，為MSP問題的研究提供有價值的幫助。

2ZH算法分析

MSP問題相關的一些基本定義及求解MSP問題的ZH算法詳見文獻[1]，鑒于文章篇幅原因，本文不再贅述。本文涉及的所有符號和算法過程都來自文獻[1]（新的符號會另行說明）。

ZH算法整體上以多級加標圖的可達路徑集邊集R（E）為基礎運行，算法不斷循環去除R（E）中的邊，同時不斷縮減每個頂點的邊集中的邊，使得頂點邊集的改變和R（E）的改變互相約束，最終達到平衡。具體的修改過程包含兩方面：一是通過執行Change（R（u，v，l））修改邊?u，v，l?的可達路徑集邊集R（u，v，l）；二是通過執行Comp（λ（v），v，R（E））修改頂點v對應的邊集λ（v）。對R（E）的修改是ZH算法中最主要的過程，因此下文對ZH算法的分析，將首先探討可達路徑集邊集的意義，之后分析兩個基本算子Comp（ES，v，R（E） ）和Change（R（u，v，l））的作用和性質，最后給出完整修改過程的分析。

4 結束語

文獻[1]提出的MSP問題是NP完全問題的重要表達。本文對ZH算法進行了詳細分析，從新的角度指出了算法的意義。在對算法的分析過程中，分析了組成算法的兩個主要基本算子Comp（ES，v，R（E） ）和Change（R（u，v，l））的作用和性質。最后給出并證明了ZH算法的兩條重要性質——頂點邊集守恒性和頂點邊集存在性。對ZH算法的分析及其性質為MSP問題的研究提供了重要參考。

參考文獻

姜新文，吳添君，李鵬坤，等.MSP問題的一個求解算法[J].計算技術與自動化，2016，35（1）：60-70.

Jiang X W. Determining the H Property of A Graph by Changing It into Multistage Graph[J]. Computing Technology And Automation， 2004， 23（2）：52-54.

Jiang X W， Wang Q， Jiang Z H. The Fourth Version of The Proof for Z-H Algorithm to Solve MSP Problem[J]. Computing Technology & Automation， 2010， 29（3）：35-48.

Jiang X W， Peng L H， Wang Q. MSP Problem： Its NP-Completeness and Its Algorithm[C]// Ubiquitous Information Technologies and Applications （CUTE）， 2010 Proceedings of the 5th International Conference on. IEEE， 2010：1-5.

吳添君，姜新文.MSP問題NP完全性研究[J].計算機科學，2015，42（07）：12-14.

Fan S， Jiang X W， Peng L H. Polynomial-time heuristic algorithms for several NP-complete optimization problems[J]. Journal of Computational Information Systems， 2014， 10（22）：9707-9721.

Jiang X W， Liu W W， Wu T J， et al. Reductions from MSP to SAT and from SUBSET SUM to MSP[J]. Journal of Computational Information Systems， 2014， 10（3）：1287-1295.

Jiang X W. A Polynomial Time Algorithm for the Hamilton Circuit Problem[J]. Computer Science， 2013.

樊碩，姜新文.SAT問題可多項式歸結到MSP問題[J].計算機科學，2012，39（11）：179-182.

姜新文.MSP問題及其求解研究[J].計算技術與自動化，2006，25（4）：145-159.