组合优化中若干优化难题的精确算法研究
VIP免费
摘 要
组合优化是运筹学的一个重要的学科分支，其中的许多问题至今仍然是尚待
解决的 NP 难题，实际生活中的众多问题均可以视作组合优化问题的具体应用。在
精确算法领域中，分支降阶算法被广泛用来求解 NP-Hard 问题，但针对算法的常
规时间复杂度分析技术不够精确，无法得到较好的时间复杂度，因此，本文采用
加权分治技术对组合优化问题的分支降阶算法进行分析以达到降低算法时间复杂
度的目的。
加权分治技术是算法设计和分析中的一种新技术，该技术的核心思想在于对
算法进行时间复杂度分析时根据问题的特征对不同的处理对象设置不同的权值，
用于降低原问题及分支后子问题总规模的大小，最终降低算法时间复杂度。本文
的主要工作内容和创新点具体如下所述：
(1)简要阐述了计算复杂性和几种经典的组合优化问题，以及目前一些常用的
精确算法。
(2)针对删除最少顶点生成二分图问题，首先运用常规枚举方法得到一个时间
复杂度为 O(3n)的算法，然后通过增加降阶规则、改善算法设计和运用加权分治技
术进行算法设计和分析，最终得到一个时间复杂度为 O (1.8157n)的精确算法。
(3)针对最大团问题，在研究最大团问题的性质的基础上运用分支降阶技术设
计出一个精确算法求解该问题，然后运用常规技术对算法进行分析，得出其时间
复杂度为 O (1.380n)，最后运用加权分治技术对原算法进行时间复杂度分析，将该
算法的时间复杂度由 O (1.380n) 降为 O (1.325n)。
(4)针对最小顶点覆盖问题，首先根据问题的定义分析出其相应的性质，再依
据性质设计出一个分支降阶算法求解该问题。然后运用常规技术对算法进行分析，
得出其时间复杂度为 O (1.325n)，最后运用加权分治技术对在不改变算法的基础上
将该算法的时间复杂度由 O (1.325n) 降为 O (1.255n)。同时对低度图的最小顶点覆
盖问题进行了分析，结果表明 3度图的最小顶点覆盖问题可以在多项式时间内解
决。
本文的研究表明分支降阶算法能够有效地求解部分常见的 NP-Hard 问题，并
在理论上获取问题的最优解，同时分析结果表明加权分治技术能够有效地降低这
类精确算法的时间复杂度。
关键词：加权分治；删除顶点生成二分图；最大团；最小顶点覆盖；
分支降阶；算法复杂性
ABSTRACT
Combinatorial optimization is a very important discipline branch of operations
research. Many hard optimization problems in combinatorial optimization are NP-Hard
problems and still unsolved so far. Many practical problems can be regarded as specific
application of combinatorial optimization problems. Branch and reduce approach is
very widely used tool for designing an exact algorithm to solve combinatorial
optimization problems, but this method is far from producing tight worst case running
time bounds. In light of this, the approach of measure and conquer is applied to analyze
algorithms to lower the running time of exact algorithms.
The approach of measure and conquer is a new technique for algorithm design and
analysis. The main idea of Measure and Conquer is to focus on the choice of the
measure. In other words, the approach first chooses a refined non-standard measure to
measure the size of the problem and its sub-problems at the each branching phase.
Finally the running time of the algorithm can be reduced by this approach. The main
contents and innovations of the dissertation are as following:
(1)This dissertation generally elucidates computational complexity and introduces
several typical traditional combinatorial optimization problems, then introduces some
common exact algorithms which can be employed to solve combinatorial optimization
problems.
(2) For odd cycle transversals problems, this dissertation first provides an
enumeration algorithm whose running time is O(3n), then adds some rules to improve
the algorithm. In order to further improve exact algorithms for this problem, this
dissertation finally proposes a new exact algorithm and use measure and conquer
approach to analyze the new algorithm. The measure and conquer approach improves
the time-complexity of the new algorithm from O(1.9111n) to O(1.8157n).
(3)For maximum clique problem, this dissertation first analyzes some theorems of
the problem, then design an exact algorithm to resolve the maximum clique problem
through using those theorems. After that we use traditional analysis technology to
analyze the worst-case running time of the algorithm and gets O(1.380n) running time.
Finally, this dissertation employs the measure and conquer approach to improve the
time-complexity of the algorithm from O(1.380n) to O(1.325n) without modifying the
algorithm.
(4) For minimum vertex cover problem, this dissertation first analyzes some
theorems of the problem, then design an exact algorithm to resolve the maximum clique
problem through using those theorems. After that we use two kinds of methods to
analyze the worst-case time complexity of the algorithm. When we use the standard
measure, the worst-case running time of the algorithm is O(1.325n). But when we
employ the method of Measure and Conquer, we improve the worst-case time
complexity of the same algorithm from O(1.325n) to O(1.255n) . At the same time, we
analysis the minimum vertex cover problem in low-degree graph, the result show
minimum vertex cover problem on 3-degree graph can solve the in polynomial time.
The result of this dissertation shows that branch and reduce is a very useful tool to
solve some common NP-Hard problem. At the same time, the results of this work
indicate that Measure and Conquer approach can significantly speed up exact
algorithms and has wide applications in the analysis of exact algorithms.
Key words: measure and conquer, odd cycle transversals, maximum
clique, minimal vertex cover, branch and reduce，algorithm complexity
目 录
中文摘要
ABSTRACT
目 录.................................................................................................................................... 1
第一章 绪论 ....................................................................................................................... 1
1.1 研究背景 ................................................................................................................. 1
1.2 研究意义 ................................................................................................................. 2
1.3 研究内容 ................................................................................................................. 2
1.4 全文组织 ................................................................................................................. 3
第二章 基础理论知识 ...................................................................................................... 5
2.1 计算复杂性理论 .................................................................................................... 5
2.2 常见的组合优化难题 ............................................................................................ 7
2.2.1 旅行商问题 .......................................................................................................... 7
2.2.2 排序问题 .............................................................................................................. 7
2.2.3 Steiner 最小生成树问题 ..................................................................................... 7
2.2.4 最大独立集问题 .................................................................................................. 8
2.2.5 最小支配集问题 ................................................................................................. 8
2.2.6 背包问题 ............................................................................................................. 8
2.2.7 图着色问题 ......................................................................................................... 8
2.3 精确算法概述 ........................................................................................................ 8
2.3.1 分治与递归 .......................................................................................................... 9
2.3.2 回溯法................................................................................................................... 9
2.3.3 分支限界法 .......................................................................................................... 9
2.4 常规时间复杂度分析方法.................................................................................. 11
2.5 加权分治技术 ...................................................................................................... 12
2.6 本章小结 ............................................................................................................... 13
第三章 二分图问题的加权分治算法 ........................................................................... 14
3.1 OCT 问题介绍及常用符号................................................................................. 14
3.2 OCT 问题常规枚举算法及改善后的枚举算法 ............................................... 15
3.3 OCT 问题改进算法 ............................................................................................. 15
3.4 独立集问题的常规分支降阶算法及时间复杂度分析 .................................... 17
3.5 加权分治技术下的算法 MIS(G1,S2) .................................................................. 19
3.6 常规技术分析下算法的时间复杂度 ................................................................. 20
3.7 加权分治技术分析下算法的时间复杂度......................................................... 20
3.8 结束语 ................................................................................................................... 22
第四章 最大团问题的加权分治算法 ........................................................................... 24
4.1 最大团问题介绍及常用符号 ............................................................................. 24
4.2 最大团问题的性质及证明.................................................................................. 25
4.3 最大团问题的算法 .............................................................................................. 26
4.4 常规技术分析下 MC(G,S)算法的时间复杂度分析 ........................................ 27
4.5 加权分治技术分析下 MC(G,S)算法的时间复杂度 ........................................ 27
4.6 结束语 ................................................................................................................... 29
第五章 最小顶点覆盖问题的加权分治算法 ............................................................... 30
5.1 顶点覆盖问题定义和性质.................................................................................. 30
5.1.1 顶点覆盖问题定义 ............................................................................................ 30
5.1.2 顶点覆盖问题在工业生产中应用 ................................................................... 30
5.2 最小顶点覆盖问题的性质及证明 ..................................................................... 31
5.3 最小顶点覆盖问题的算法.................................................................................. 32
5.4 常规技术分析下 MVC(G,S)算法的时间复杂度分析 ..................................... 33
5.5 加权分治技术分析下 MVC(G,S)算法的时间复杂度 ..................................... 34
5.6 示例分析 ............................................................................................................... 36
5.7 结束语 ................................................................................................................... 40
第六章 总结和展望......................................................................................................... 41
6.1 总结 ........................................................................................................................ 41
6.2 展望 ........................................................................................................................ 42
参考文献 ............................................................................................................................. 43
在读期间公开发表的论文和承担科研项目及取得成果 .............................................. 48
致 谢.................................................................................................................................. 49
第一章 绪论
1
第一章 绪论
1.1 研究背景
组合优化[1,2,3]是以数学为基础的运筹学中一个重要的学科分支，在许多领域
都有着广泛的应用。比如在信息技术、信号传输、通信网络、市场分析、工业工
程、计算机视觉、生产调度及故障诊断等领域具有非常广泛的应用等领域其都发
挥着重要的作用[4,5,6]。组合优化问题的求解目标大多都是从所有可行解集中找到
其中的最优解。组合优化问题包括许多著名难题，如加工调度问题[7]、二次分配
问题[8]、0-1 背包问题[9]、图着色问题[10]及旅行商问题[11,12]等。对于这些难题的描
述都很简单，但求解起来却很困难。求解之所以困难主要是因为算法在求解这些
问题时，不仅需要极大的存储空间来存放程序，还需要指数时间来运行程序。基
于这两个原因，目前无法用计算机求解大规模情况下的此类问题。
计算复杂性理论[13,14,15]是研究算法求解问题的困难程度的相关理论。给定了
问题的输入数据，通过设计有限步的基本计算，使输入数据转化成输出数据，这
一过程即为算法设计。算法是指为了解决一个特定问题所采用的方法或者步骤。
一个算法，对任意输入符合要求的数据可以得到正确的输出数据，则称算法是正
确的。算法的正确性是算法设计中最首要的、最基本的要求。计算算法运行时所
需要资源的规模的过程，即为算法分析。理论上来说，对算法进行分析时既要分
析其运行的时间复杂性，同时还要分析其所占资源的空间复杂性。由于，算法的
空间复杂性不会超过时间复杂性，所以我们通常更关注算法的时间复杂性。
算法的时间复杂度可通过求解问题的计算量的大小来度量。按此标准可将求
解问题分为两类：一、能够在多项式时间进行求解的问题称为易解问题；二、不
确定是否能够在多项式时间内求解，即在目前看来只能在指数时间内进行求解的
问题，称为难解问题(也称 NP-hard 问题)[1,13]。由于难解问题本身的复杂性决定了
对其时间复杂度的分析也同样很困难。现在对难题的求解方法越来越复杂，但对
其的复杂性的分析方法却很简单。本文中传统的图论类算法分析时一般都是采用
图顶点的个数或是边的条数作为描述算法在分支过程中产生的所有子问题规模的
上界，从而得到算法的时间复杂度。这种分析方法虽然能得到算法的时间复杂度，
但是存在时间复杂度不够精确的问题。
摘要：
展开>>
收起<<
摘要组合优化是运筹学的一个重要的学科分支，其中的许多问题至今仍然是尚待解决的NP难题，实际生活中的众多问题均可以视作组合优化问题的具体应用。在精确算法领域中，分支降阶算法被广泛用来求解NP-Hard问题，但针对算法的常规时间复杂度分析技术不够精确，无法得到较好的时间复杂度，因此，本文采用加权分治技术对组合优化问题的分支降阶算法进行分析以达到降低算法时间复杂度的目的。加权分治技术是算法设计和分析中的一种新技术，该技术的核心思想在于对算法进行时间复杂度分析时根据问题的特征对不同的处理对象设置不同的权值，用于降低原问题及分支后子问题总规模的大小，最终降低算法时间复杂度。本文的主要工作内容和创新点具体...
相关推荐
-
跨境电商商业计划书模版VIP免费
2025-01-09 10 -
跨境电商方案范文VIP免费
2025-01-09 9 -
创业计划书VIP免费
2025-01-09 11 -
xx生鲜APP计划书VIP免费
2025-01-09 7 -
跨境电商创业园商业计划书(盈利模式)VIP免费
2025-01-09 6 -
跨境电商计划书VIP免费
2025-01-09 9 -
绿色食品电商平台项目计划书VIP免费
2025-01-09 8 -
农产品电子商务商业计划书VIP免费
2025-01-09 7 -
农村电商平台商业计划书VIP免费
2025-01-09 9 -
生鲜商城平台商业计划书VIP免费
2025-01-09 7
作者：侯斌
分类：高等教育资料
价格：15积分
属性：52 页
大小：1.89MB
格式：PDF
时间：2024-11-19
