李鵬坤+姜新文+蓋方宇

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

關(guān)鍵詞：MSP問(wèn)題；ZH算法；算法分析；算法性質(zhì)

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：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完全問(wèn)題是理論計(jì)算機(jī)科學(xué)領(lǐng)域的重要研究課題。文獻(xiàn)[1]提出的MSP問(wèn)題是一個(gè)NP完全問(wèn)題。在文獻(xiàn)[1]中，作者給出了求解MSP問(wèn)題的多項(xiàng)式時(shí)間算法以及關(guān)于算法正確性的證明，該問(wèn)題對(duì)于NP完全問(wèn)題的研究具有重要意義。本文對(duì)MSP問(wèn)題求解算法ZH算法進(jìn)行深入分析，從新的視角解讀該算法，分析算法主要執(zhí)行過(guò)程，并指出算法本身具有的一些重要性質(zhì)。這種新視角的分析以及算法的性質(zhì)，能夠使研究人員更好的理解MSP問(wèn)題及其求解算法，為MSP問(wèn)題的研究提供有價(jià)值的幫助。

2ZH算法分析

MSP問(wèn)題相關(guān)的一些基本定義及求解MSP問(wèn)題的ZH算法詳見(jiàn)文獻(xiàn)[1]，鑒于文章篇幅原因，本文不再贅述。本文涉及的所有符號(hào)和算法過(guò)程都來(lái)自文獻(xiàn)[1]（新的符號(hào)會(huì)另行說(shuō)明）。

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

姜新文，吳添君，李鵬坤，等.MSP問(wèn)題的一個(gè)求解算法[J].計(jì)算技術(shù)與自動(dòng)化，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問(wèn)題NP完全性研究[J].計(jì)算機(jī)科學(xué)，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問(wèn)題可多項(xiàng)式歸結(jié)到MSP問(wèn)題[J].計(jì)算機(jī)科學(xué)，2012，39（11）：179-182.

姜新文.MSP問(wèn)題及其求解研究[J].計(jì)算技術(shù)與自動(dòng)化，2006，25（4）：145-159.