论文部分内容阅读
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)更加有效。