没有合适的资源?快使用搜索试试~ 我知道了~
近似算法若干问题研究.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 121 浏览量
2022-07-12
08:06:30
上传
评论
收藏 990KB PDF 举报
温馨提示
试读
25页
近似算法若干问题研究.pdf
资源推荐
资源详情
资源评论
摘
要
九十年代以来,近似算法的研究取得了突破性发展。这种发展包括两方面的内容,一是NP难问
题的的难近似性(我们称其为问题的下界)及另一个是NP难问题的可近似性(我们也称其为问题的
上界)。
f当今世界正面临着一场新的技术革命,计算技术,通讯技术及生物技术的研究居于其核心的
地位。但是在计算技术,通讯技术及生物技术的应用与研究中有大量的问题是NP一难的,也就是说
在现有的计算能力下这类问题不太可能有高效率的算法。但是其中的许多问题是有着重要的不
可回避的需求背景的。于是理论计算机科学的研究者们开展了近似算法的研究。近似算法给出的
是与最优解具有一定性能比的多项式算法。事实上近似算法的研究是如此成功,以至于他的研究
思想成为当今许多算法研究领域的一种主要研究工具,例如计算生物学(computational
biology),
计算几何学(computational
geometry),计算化学(computational
chemistry)等。)—1,
本文的主要内容分四章。第一章对和近似算法有关的背景知识作了回顾,其中包括近似算法
的一般概念,评价近似算法的若干因素以及和近似算法有关的分类等。第二章对近似算法的难近
似性fInapproximability)进行了讨论并力图给出问题难近似性证明的几种常用途径。第三章定义
了批处理机调度问题(batch
scheduling),然后讨论了机器完成所有工作时间最短的目标函数,并
对一种特殊的情况给出了一个多项式算法。第四章讨论了批处理机调度问题的平均响应时间最
短的目标函数,并对于机器的容量不受限模型给出了一个PTAS。
关键词:近似算法,难近似性,可近似性,线性规划,批处理机调度。
分类号:TP30l
6
第一章近似算法概述
1.1
引言
本章将对和近似算法有关的基本概念,结论及其他预备知识作一简要的回顾。
.
如何处理NP难问题?对于大多数问题而言一种常用的方法是穷举法,对于穷举法可以采用
一些加速的方法,如分治法(divide
and
conquer),分支限界法(brance
and
bound),割厦婆(cutt…ing.
planel,随机法-(randoFIIUess)等。我们有时也可以放弃对最优解的要求,去找一些次优解。常用
的方珐有启发式算法(heuristics),局部搜索法(10cal
search),褪火法(simulated
annealing),遗传算
法fgenetie
algorithms),tabu
search及近似算法。
研究近似算法的目的何在?以下是几个可能的理由:
这些难的问题需要一个解。
以严格的数学角度来研究启发式算法。
对问题的难度有更深入的了解。
研究着玩
另外对于近似算法的研究有以下两个前提:
l通常对于近似算法的研究是指优化问题而不是判定问题。
2近似算法的研究是基于理论计算机界的一个普遍信念:P≠NP。
以下的部分虽然有时候并不特别指出这一点,但其实都基于这一假设。
1.2
概念及早期结果
下面首先给出近似算法的几个常用的定义:
定义1.1如果一个多项式时间算法A对于问题的每个实例,供最优解为0P丁(,)唐B有以下关系
式成立:MAX{帮,石鲁竿击)≤6,则称|4为一个6一近似算法。
我们称6为算法A的近似率(approximation
ratio)。根据以上定义可知所有近似算法的近似率
的值都是大于l的。
根据算法的时间复杂度,我们还可以将近似率为1+e(e为任意小的常数)的近似算法进行分
类
定义1_2对于一个问题,如果一组算法"。)。rf为不同的任意小常数J中每个算法A。的近似率
为1+e且其运行时间为输入的多项式时间,则我们称该组算法f|4。l。为一个多项式时间近似方
案(polyliomial
lime
approrunation
scheme)、简称PTAS。
定义1.3对于一个问题,如果一组算法{A。)。rc为不同的任意小常数,中每个算法^。的近似率
为1+c且其运行时间为输人和;的多项式时间,则我们称该组算法似。)。为一个完全多项式时间
近似方案仇“g
polynomial
f
zme
approximation
scheme),简称FPTAS
第一章近似算法概述
Table
1
1:四类难近似问题及其代表
』类
难近似翠 代表同题
l
l
L+E
MAX一3SAT
f
2
O(109n)
SETCOVER
【3
2l091—1“
LABELCOVER
l
4
nf
CLlQUE
2
早在NP一完全的定义给出之前,就有了近似算法的研究。其代表是Gra.ham的近似率为2的调
度问题的近似算法『111和度量TsP问题的近似算法[22]。其后Garey,Uilman和Johnson等人给出
了许多问题的一些简单的近似算法。在近似算法的研究早期,来自结构复杂性方面的最成功的结
果是Garey和Johnson对强NP难的定义和研究。
定义1.4如果判定问题n属:T-NP并-.E].存在一个整系数多项式p使得,■是Ⅳ雕的(,■表示把Ⅳ限制
在那些满足M。。f川<p(Leng£^[朋)的实例【上所得到的子问题。),那么称问题”是强Ⅳ雕的。
Garey和Johns。n证明:
定理1.1如果P≠NP,强NP难问题不可能有FPTAS。
在80年代中期近似算法的研究有两个大的成就。其一是Leighton和Ra0【23】首次利用线性规
划及其对偶工具对一些图论问题设计近似算法。事实上这个工具是如此有效以至于在九十年代
它成为近似算法设计的最流行的工具并且有着大量的非常成功的结果。
其二是Papadimitriou和Yannakakis
f271给出的MAX—SNP的定义。类似于NP完全的模式,他
们定义了一种保持近似性的规约并且证明了一些经典的问题是MAX.SNP完全的,其代表是MAx一
3SAT问题。他们证明任何对于MAX,3SAT的难近似性结果都可以推广到任何一个MAX—SNP难问
题上。
但是当时还无法找到MAX一3SAT的好的难近似性结果。当人们研究一个问题时,通常是首先
找其可能的多项式算法,如果经过一段时间的努力而没有找到,人们通常会尝试证明其是NP难
的;而当证明NP难遇到很大困难时又会考虑找到其多项式算法。如此过程反复,从而对问题的计
算本质有了一步步的深入的认识。在近似算法的研究过程当中也是相似的情形。不同的是,尽管
人们普遍猜测对于某一些问题要达到某种近似率是NP难的,对绝大多数问题却始终无法证明这
一点。于是当人们研究近似算法的时候总是有种缺憾感,他们无法理直气壮的说他们的算法究竟
离可能最好的近似算法有多大的距离。幸运的是,这种困境在伴随着PcP定理的降临而得到改变。
1.3
PCP定理
PCP定理证明MAX一3SAT问题没有PTAS算法,从而我们可以称MAS.SNPY;Iti问题均无PTAS算
法。(即达到一定的常数的近似率的算法是NP难的。)由于MAX.3SAT的常数近似算法是早就存在
的,所以MAX一3SAT可以看作是只有常数近似解的问题的代表。人们不禁会问那么会不会有的问
题是有更高的难近似率呢?同样基于PCP定理,人们证明了一系列更高的难进似率的问题,并根
据问题的难近似率对问题进行了分类。以上图表1
1所示的是近似算法研究中常用的四个大类。
当人们证明某一问题的难进似率时,通常会首先试图证明其是MAX.SNP难的。然后考虑证
明其可能的更高的难近似率。但这种方法并不一定总有效。虽然根据过去的经验,几乎所有的
无PTAS的问题都可以证明其是MAX+SNP难的,但对于在L。。范式下的最短格向量问题(Shortest
Lattice
Vector
Problem),人们却无法证明它是MAX—SNP)t隹的。尽管它的难近似率是2
JoF…n。目
前来讲这一思路仍是~个证明的常用方法。
PCP定理是九十年代理论计算机科学的一个重大事件。它不仅为近似算法的研究提供了坚
实的基础而且它综合了许多领域的研究成果,是理论计算机科学家近十年研究的结晶,充分体现
了理论计算机科学中研究的美的旋律。以下g'J'PCP定理相关的知识给出简单的介绍。
剩余24页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功