加权分治技术在Set Packing问题中的应用与研究

论文摘要

NP-完全理论是算法研究方面的重要的基本理论，它在计算机、电气工程和运筹学方面都有重要的地位。本文主要以算法技巧为着眼点来研究此类问题，希望在解决方式上有新的突破。加权分治技术由F．V．fomin首先提出，是在分析算法中产生的一项新技术，该方法基于选择不同的量来描述分支子问题的大小，以求从中得到在最差情况下最好的时间复杂度。在加权分治技术中采用伪凸规划技术对回溯算法来确定各个权值，使得时间复杂度最小。我们也给出了一种新方法，通过进化算法求解赋权函数以求得最小上界，同样可以来确定权值，且比前种方法更加简单。根据加权分治技术的应用范围选定Set Packing问题进行深入研究，依据所研究问题的差异，将Set Packing问题分成5类，并给出了具体的定义。在此基础上，分别介绍了求解这5类问题的相关算法，着重分析和比较了参数算法中所运用的各项技术，并提出了该问题算法研究的发展方向。对于GSP问题本文给出了一个简单的递归算法，并利用加权分治技术深入分析了其时间复杂度。以前对于GSP问题转换成独立集问题来求，并没有考虑到符号全集的大小，我们的算法将符号全集的大小引入进来，通过应用加权分治技术来分析包含n个子集且符号全集为N的set packing问题的一个简单的递归算法，得到其精确算法的时间复杂度为O*(1.1686n+N)，当N≤n／4时，比现有最佳的算法O*（1.2209n）更加有效。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.2 课题研究内容
• 1.3 论文组织
• 第二章 Set Packing问题的研究进展
• 2.1 问题的分类
• 2.2 非参数化Set Packing相关算法
• 2.2.1 常规Set Packing
• 2.2.2 m-Set Packing
• 2.2.3 带权Set Packing
• 2.3 参数化m-Set Packing相关算法
• 2.3.1 局部贪婪法
• 2.3.2 代数法
• 2.3.3 核心化法
• 2.3.4 分治法
• 2.3.5 着色法
• 2.4 本章小结
• 第三章 加权分治技术
• 3.1 加权分治技术具体应用
• 3.1.1 最小支配集
• 3.1.2 最大独立集
• 3.2 加权分治技术相关研究
• 3.2.1 加权分治技术与参数计算相结合的可能性
• 3.2.2 加权分治技术应用范围
• 3.2.3 加权分治技术的一般分析步骤
• 3.3 权值求解方法
• 3.3.1 求解问题规范化
• 3.3.2 设计思想
• 3.3.3 具体实现
• 3.4 本章小结
• 第四章 一种基于加权分治技术的Set Packing算法
• 4.1 基本知识
• 4.2 基本算法
• 4.3 基于加权分治技术的分析方法
• 4.4 本章小结
• 第五章 结束语
• 5.1 研究工作总结
• 5.2 进一步研究工作展望
• 参考文献
• 致谢
• 研究成果