最小顶点覆盖问题的加权分治算法

《最小顶点覆盖问题的加权分治算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２４卷第５期运筹与管理Ｖｏｌ．２４，Ｎｏ．５２０１５年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１５最小顶点覆盖问题的加权分治算法陈吉珍，　宁爱兵，　支志兵，　王永斐，　张惠珍（上海理工大学管理学院，上海２０００９３）摘要：最小顶点覆盖问题是组合优化中经典ＮＰ-Ｈａｒｄ问题之一，其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术，该技术主要用于对分支降阶的递归算法进行复杂性分析，其核心思想可以理解为依据问题不同的特征设

2、置一组相应的权值，以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题，并通过加权分治技术分析得出该算法的nn时间复杂度为Ｏ（１．２５５），优于常规分析下的时间复杂度Ｏ（１．３２５）。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。关键词：图论；算法复杂性；加权分治技术；分支降阶技术；最小顶点覆盖中图分类号：Ｏ２２３　　　文章标识码：Ａ文章编号：１００７-３２２１（２０１５）０５-０１５１-０５MeasureandConquer

3、ApproachfortheMinimumVertexCoverProblemＣＨＥＮＪｉ-ｚｈｅｎ，ＮＩＮＧＡｉ-ｂｉｎｇ，ＺＨＩＺｈｉ-ｂｉｎｇ，ＷＡＮＧＹｏｎｇ-ｆｅｉ，ＺＨＡＮＧＨｕｉ-ｚｈｅｎ（SchoolofManagement，UniversityofShanghaiforScienceandTechnology，Shanghai２０００９３，China）Abstract：Ｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒｓｅｔｐｒｏｂｌｅｍｉｓａｗｅｌｌ-ｋｎｏｗｎＮＰ-Ｈａｒｄｐｒｏｂｌｅｍ

4、ｉｎｔｈｅａｒｅａｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉ-ｍｉｚａｔｉｏｎａｎｄｈａｓｉｍｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．ＴｈｅａｎａｌｙｔｉｃａｌｔｅｃｈｎｏｌｏｇｙｏｆＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒｉｓｗｉｄｅｌｙｕｓｅｄｔｏａｎａｌｙｚｅｔｈｅｗｏｒｓｔ-ｃａｓｅｒｕｎｎｉｎｇｔｉｍｅｏｆｅｘａｃｔａｌｇｏｒｉｔｈｍｓｂａｓｅｄｏｎｂｒａｎｃｈａｎｄｒｅｄｕｃｅ．ＴｈｅｍａｉｎｉｄｅａｏｆＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒｉｓｆｏｃｕｓｅｄｏｎｃｈｏｏｓ

5、ｉｎｇａｒｅｆｉｎｅｄｎｏｎ-ｓｔａｎｄａｒｄｍｅａｓｕｒｅｔｏｍｅａｓｕｒｅｔｈｅｓｉｚｅｏｆｔｈｅｐｒｏｂｌｅｍａｎｄｉｔｓｓｕｂ-ｐｒｏｂｌｅｍｓａｔｔｈｅｅａｃｈｂｒａｎｃｈｉｎｇｐｈａｓｅ．Ｉｎｔｈｉｓｗｏｒｋ，ｗｅｆｉｒｓｔｕｓｅｔｈｅｔｅｃｈｎｏｌｏｇｙｏｆＢｒａｎｃｈａｎｄＲｅｄｕｃｅｔｏｄｅｓｉｇｎａｎｅｘａｃｔａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒｐｒｏｂｌｅｍ，ｔｈｅｎｕｓｅｔｗｏｋｉｎｄｓｏｆｍｅｔｈｏｄｓｔｏａｎａｌｙｚｅｔｈｅｗｏｒｓｔ-ｃ

6、ａｓｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｗｅｉｍｐｒｏｖｅｔｈｅｗｏｒｓｔ-ｃａｓｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅｓａｍｅａｌｇｏｒｉｔｈｍｆｒｏｍＯ（１．３２５ｎ）ｔｏＯ（１．２５５ｎ）ｂｙｅｍｐｌｏｙｉｎｇｔｈｅｍｅｔｈｏｄｏｆＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒ．ＴｈｅｒｅｓｕｌｔｓｏｆｔｈｉｓｗｏｒｋｉｎｄｉｃａｔｅｔｈａｔＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒａｐｐｒｏａｃｈｃａｎｓｉｇｎｉｆｉｃａｎｔｌｙｓｐｅｅｄｕｐｅｘａｃｔａｌｇｏｒｉｔｈｍｓａｎｄｈａ

7、ｓｗｉｄｅａｐｐｌｉ-ｃａｔｉｏｎｓｉｎｔｈｅａｎａｌｙｓｉｓｏｆｅｘａｃｔａｌｇｏｒｉｔｈｍｓ．Keywords：ｇｒａｐｈｔｈｅｏｒｙ；ａｌｇｏｒｉｔｈｍｃｏｍｐｌｅｘｉｔｙ；ＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒ；ＢｂｒａｎｃｈａｎｄＲｅｄｕｃｅ；ＭｉｎｉｍｕｍＶｅｒｔｅｘｃｏｖｅｒ０　引言［１］顶点覆盖问题及其各种变形问题在图论、组合数学、运筹学、管理及计算机科学等领域被广泛的研究。最小顶点覆盖（ｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒ，以下简称ＭＶＣ）问题是顶点覆盖问题中最常见、研究最多及应用

8、最广的一种，也是组合优化中典型ＮＰ-Ｈａｒｄ问题，除非Ｐ＝ＮＰ，否则不存在多项式时间算法。人们对［２～６］［７～１１］ＭＶＣ问题的精确算法、近似算法和启发示算法做了大量研究。近年来，由于加权分治分析技术收稿日期：２０１４-１１-０４基金项目：国家自然科学基金（７１４０１１０６）；上海市一流学科建设项目资助（Ｓ１２０１ＹＬＸＫ）；高等学校博士学科点专项科研基金联合资助课题（２０１２３１２０１２０００５）作者简介：陈吉珍（１９９０-），女，硕士生，研究方向为算法、物流工程；宁爱兵（１９７２-），男，