作者：姜新文 王琪 姜子恒算法msp问题hc问题np问题np完全问题
摘要：提出多级图简单路径求解问题,我们称之为MSP问题。给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性。最后通过将HC问题（哈密顿图判定问题）多项式归结成MSP问题,证明MSP问题的NP完全性质。本文极大地简化文献[6,7]中αβ引理的证明,特别是对证明过程中的各种情形进行分割,将一个巨大的证明分成系列引理。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
《计算技术与自动化》（CN：43-1138/TP）是一本有较高学术价值的大型季刊，自创刊以来，选题新奇而不失报道广度，服务大众而不失理论高度。颇受业界和广大读者的关注和好评。 《计算技术与自动化》坚持理论与实践相结合的方针，跟踪世界最新科技动态，以其前沿的报道和新颖实用的内容，迅速向社会各界传递技术信息，为企业和科研院所架起联系的纽带和桥梁。
省级期刊
人气 90282 评论 69
北大期刊、CSCD期刊、统计源期刊
人气 53961 评论 51
统计源期刊
人气 50746 评论 50
人气 48624 评论 69
