資源描述：
《最小頂點覆蓋問題的加權分治算法》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、第２４卷第５期運籌與管理Ｖｏｌ．２４，Ｎｏ．５２０１５年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１５最小頂點覆蓋問題的加權分治算法陳吉珍， 寧愛兵， 支志兵， 王永斐， 張惠珍（上海理工大學管理學院，上海２０００９３）摘要：最小頂點覆蓋問題是組合優(yōu)化中經典ＮＰ-Ｈａｒｄ問題之一，其在實際問題中有著廣泛的應用。加權分治技術是算法設計和復雜性分析中的新技術，該技術主要用于對分支降階的遞歸算法進行復雜性分析，其核心思想可以理解為依據問題不同的特征設
2、置一組相應的權值，以求降低該算法最壞情況下的時間復雜度。本文依據加權分治技術設計出一個分支降階遞歸算法來求解最小頂點覆蓋問題，并通過加權分治技術分析得出該算法的nn時間復雜度為Ｏ（１．２５５），優(yōu)于常規(guī)分析下的時間復雜度Ｏ（１．３２５）。本文中的結果表明運用上述方法降低算法的時間復雜度是非常有效的。關鍵詞：圖論；算法復雜性；加權分治技術；分支降階技術；最小頂點覆蓋中圖分類號：Ｏ２２３ 文章標識碼：Ａ文章編號：１００７-３２２１（２０１５）０５-０１５１-０５MeasureandConquer
3、ApproachfortheMinimumVertexCoverProblemＣＨＥＮＪｉ-ｚｈｅｎ，ＮＩＮＧＡｉ-ｂｉｎｇ，ＺＨＩＺｈｉ-ｂｉｎｇ，ＷＡＮＧＹｏｎｇ-ｆｅｉ，ＺＨＡＮＧＨｕｉ-ｚｈｅｎ（SchoolofManagement，UniversityofShanghaiforScienceandTechnology，Shanghai２０００９３，China）Abstract：Ｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒｓｅｔｐｒｏｂｌｅｍｉｓａｗｅｌｌ-ｋｎｏｗｎＮＰ-Ｈａｒｄｐｒｏｂｌｅｍ
4、ｉｎｔｈｅａｒｅａｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉ-ｍｉｚａｔｉｏｎａｎｄｈａｓｉｍｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．ＴｈｅａｎａｌｙｔｉｃａｌｔｅｃｈｎｏｌｏｇｙｏｆＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒｉｓｗｉｄｅｌｙｕｓｅｄｔｏａｎａｌｙｚｅｔｈｅｗｏｒｓｔ-ｃａｓｅｒｕｎｎｉｎｇｔｉｍｅｏｆｅｘａｃｔａｌｇｏｒｉｔｈｍｓｂａｓｅｄｏｎｂｒａｎｃｈａｎｄｒｅｄｕｃｅ．ＴｈｅｍａｉｎｉｄｅａｏｆＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒｉｓｆｏｃｕｓｅｄｏｎｃｈｏｏｓ
5、ｉｎｇａｒｅｆｉｎｅｄｎｏｎ-ｓｔａｎｄａｒｄｍｅａｓｕｒｅｔｏｍｅａｓｕｒｅｔｈｅｓｉｚｅｏｆｔｈｅｐｒｏｂｌｅｍａｎｄｉｔｓｓｕｂ-ｐｒｏｂｌｅｍｓａｔｔｈｅｅａｃｈｂｒａｎｃｈｉｎｇｐｈａｓｅ．Ｉｎｔｈｉｓｗｏｒｋ，ｗｅｆｉｒｓｔｕｓｅｔｈｅｔｅｃｈｎｏｌｏｇｙｏｆＢｒａｎｃｈａｎｄＲｅｄｕｃｅｔｏｄｅｓｉｇｎａｎｅｘａｃｔａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒｐｒｏｂｌｅｍ，ｔｈｅｎｕｓｅｔｗｏｋｉｎｄｓｏｆｍｅｔｈｏｄｓｔｏａｎａｌｙｚｅｔｈｅｗｏｒｓｔ-ｃ
6、ａｓｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｗｅｉｍｐｒｏｖｅｔｈｅｗｏｒｓｔ-ｃａｓｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅｓａｍｅａｌｇｏｒｉｔｈｍｆｒｏｍＯ（１．３２５ｎ）ｔｏＯ（１．２５５ｎ）ｂｙｅｍｐｌｏｙｉｎｇｔｈｅｍｅｔｈｏｄｏｆＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒ．ＴｈｅｒｅｓｕｌｔｓｏｆｔｈｉｓｗｏｒｋｉｎｄｉｃａｔｅｔｈａｔＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒａｐｐｒｏａｃｈｃａｎｓｉｇｎｉｆｉｃａｎｔｌｙｓｐｅｅｄｕｐｅｘａｃｔａｌｇｏｒｉｔｈｍｓａｎｄｈａ
7、ｓｗｉｄｅａｐｐｌｉ-ｃａｔｉｏｎｓｉｎｔｈｅａｎａｌｙｓｉｓｏｆｅｘａｃｔａｌｇｏｒｉｔｈｍｓ．Keywords：ｇｒａｐｈｔｈｅｏｒｙ；ａｌｇｏｒｉｔｈｍｃｏｍｐｌｅｘｉｔｙ；ＭｅａｓｕｒｅａｎｄＣｏｎｑｕｅｒ；ＢｂｒａｎｃｈａｎｄＲｅｄｕｃｅ；ＭｉｎｉｍｕｍＶｅｒｔｅｘｃｏｖｅｒ０ 引言［１］頂點覆蓋問題及其各種變形問題在圖論、組合數學、運籌學、管理及計算機科學等領域被廣泛的研究。最小頂點覆蓋（ｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒ，以下簡稱ＭＶＣ）問題是頂點覆蓋問題中最常見、研究最多及應用
8、最廣的一種，也是組合優(yōu)化中典型ＮＰ-Ｈａｒｄ問題，除非Ｐ＝ＮＰ，否則不存在多項式時間算法。人們對［２～６］［７～１１］ＭＶＣ問題的精確算法、近似算法和啟發(fā)示算法做了大量研究。近年來，由于加權分治分析技術收稿日期：２０１４-１１-０４基金項目：國家自然科學基金（７１４０１１０６）；上海市一流學科建設項目資助（Ｓ１２０１ＹＬＸＫ）；高等學校博士學科點專項科研基金聯合資助課題（２０１２３１２０１２０００５）作者簡介：陳吉珍（１９９０-），女，碩士生，研究方向為算法、物流工程；寧愛兵（１９７２-），男，
