李鹏坤+姜新文+盖方宇

摘 要：文献[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）的改变互相约束，最终达到平衡。……