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.