Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 生物信息学笔记（二）
发信站: 哈工大紫丁香 (2001年06月08日18:50:04 星期五), 站内信件

§2 组合优化的可近似性
一、组合优化的近似算法
组合优化问题
Π=(D,sol,m,goal)
其中D是实例集，任意x∈D，sol(x)是x的有穷的可行解集，m是目标函数，
任意x∈D，y∈sol(x)，m(x,y)∈Z+，goal=max或min.
实例x∈D的最优值opt(x)=goal{m(x,y)|y∈sol(x)}
最优解y*∈sol(x)，m(x,y*)=opt(x).
NP组合优化问题
(1)D是多项式时间可识别的；
(2)sol(x)（二元关系{(x,y)|x∈D，y∈sol(x)}）可在|x|的多项式
时间内识别；
(3)m(x,y)是多项式时间可计算的；
近似比
设问题Π，对于x∈D，y∈sol(x)
近似比R(x,y)=max{opt(x)/m(x,y),m(x,y)/opt(x)}
设函数r:Z+-->(1,+∞），如果对每一个实例x，R(x,A(x))<=r(|x|)，则称
A是r(n)近似算法，或称A具有近似比r(n).
多项式时间近似方案
如果对Π的每一个实例x和ε＞0，算法A输出x的一个可行解A(x，ε)，且
满足条件：（1）R(x,A(x,ε))<=1+ε,(2)对每一个固定的>0，算法A是多项式时间
的，则称A是Π的多项式时间近似方案(PTAS).
如果A是Π的多项式时间近似方案且时间复杂度不超过多项式q(|x|,1/ε)，则称
A是Π的完全多项式时间近似方案(FPTAS).
NPO表示NP组合优化问题类；
FPTAS表示NPO中存在完全多项式时间近似方案的问题类；
PTAS表示NPO中存在多项式时间近似方案的问题类；
APX表示NPO中可近似到常数的问题类；
log-APX表示NPO中可近似在O(log n)的问题类；
poly-APX表示NPO中可近似在n^O(1)的问题类；
定理
假设P≠NP，则FPTAS真包含于PTAS,PTAS真包含于APX，APX真包含于log-APX，
log-APX真包含于poly-APX，poly-APX真包含于NPO.
二、问题的语法分类及其可近似性
每一个一阶谓词逻辑公式可表成前束范式的形式，以存在量词开始，有n-1个
存在量词和全称量词交替的前束范式称作Σn公式.
定义
如果存在Σn公式φ(w,S)，使得对于NP最大化问题Π的每一个实例x,
opt(x)=max |{w:φ(w,S)}|
        S
则称Π居于MAX Σn，其中S是谓词变量；
如果存在Σn公式φ(w,S)，使得对于NP最小化问题Π的每一个实例x,
opt(x)=min |{w:φ(w,S)}|
        S
则称Π居于MAX Σn，其中S是谓词变量.
MAX Σ0和MAX Σ1也分别记作MAX SNP和MAX NP.
定义 AP归约
设两个NP组合优化问题Πi=(Di,sol i,mi,goal i),i=1,2.如果存在函数f和g
以及常数α>0满足下述条件，则称Π1可AP归约到Π2，记作Π1≤(AP)Π2
（1）对每一个x∈I1和r>1，f(x,r)∈I2;
（2）对每一个x∈I1，r>1和y∈sol2(f(x,r)),g(x,y,r)∈sol1(x);
（3）对每一个固定的r>1，f和g是多项式时间可计算的；
（4）对每一个x∈I1，r>1和y∈sol2(f(x,r)),R2(f(x,r),y)<=r蕴涵
R1(x,g(x,y,r))<=1+α(r-1)，其中R1，R2分别是Π1,Π2的近似比.
定义
设C是NPO的子集，如果对每一个Π'∈C都有Π'≤(AP) Π，则称Π在AP归约下是
C难的.如果Π在AP归约下是C难的且Π∈C，则称Π在AP归约下是C完全的.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]