周泰杨　樊硕　彭立宏

摘 要：为提高MSP问题的多项式时间算法ZH算法的计算速度，使其能够进行更大规模多级图的测试，本文对ZH算法进行了性能分析与并行的可行性评估，针对ZH算法中循环体较多的特点，分别在巨型机和普通PC机上进行MSP问题求解算法的首次并行化实践，随之对并行化算法提出优化方法，在实验中取得了较高的加速比。

关键词：MSP；并行化；巨型机

中图分类号：TP301.6 文献标识码：A

1 引 言

NP完全问题（NP complete）是指对任意的NP问题，都能在多项式时间内转化成为的问题，NPC问题一直以来都是计算科学领域的经典问题，具有很高的理论价值和应用价值，也吸引了很多学者的关注。文献[1]中提出了一个新的NP问题——多级图的简单路径问题（MSP问题），在文献中作者提出了MSP问题的一个多项式时间算法ZH算法，并且将哈密顿图问题归结到MSP问题上，从而证明了MSP问题是一个NP完全问题。大量的证明工作和测试显示，ZH算法是一个多项式时间的算法。但是由于该算法的复杂性的多项式的阶较高，导致运算需要耗费大量的时间和空间，普通的PC机难以支持较大规模多级图的测试。

有鉴于此，本文考虑利用超级计算机的强大计算能力对ZH算法进行并行化加速，并且在PC机上进行ZH算法的并行化研究。本文余下的本分按照如下的结构安排：第二节介绍MSP问题以及并行化研究的相关工作；第三节中本文提出了一种一般化的多项式时间算法的并行化思路，并对MSP问题的解决算法进行了并行化，之后提出了ZH算法并行化方案的优化方法；……