Java算法第9章.ppt

1、第九章NP完全理论和近似算法，2。学习点理解随机存取存储器、随机存取存储器和图灵机计算模型理解不确定图灵机的概念理解P和NP语言的概念理解NP完全问题的概念理解近似算法的性能比和多项式时间近似格式的概念通过例子学习NP完全问题的近似算法(1)顶点覆盖问题；(2)旅行推销员问题；(3)集合覆盖问题；(4)子集和问题。3，9.1计算模型，在分析问题的计算复杂性之前，必须首先建立用于解决问题的计算模型，包括定义计算模型中使用的基本操作。建立计算模型的目的是使问题的计算复杂性分析有一个共同的目标尺度。有三种基本的计算模型：随机存取机(ram)；随机存取存储程序机(随机存取存储程序机)图灵机。这三种计算

2、模型的计算能力相当，但计算速度不同。4、9.1.1随机存取存储器，1、随机存取存储器结构，5、9.1.1随机存取存储器，2、随机存取存储器程序，一个随机存取存储器程序定义从输入带到输出带的映射。这种映射关系可以用两种不同的方式来解释。解释1:把内存程序(RAM progRAM)看作是计算一个函数。如果一个随机存取存储器程序p总是从输入带的前n个平方中读取n个整数x1，x2，xn，并在输出带的第一个平方上输出一个整数y，那么程序p计算函数f(x1，x2，xn)=y。将字符串S=a1a2an放在输入带上。将符号a1放在输入带的第一个正方形中，符号a2放在第二个正方形中，符号an放在第n个正方形中。

3、然后，在第n 1个方块中放入0作为输入字符串的结束标记。如果随机存取存储器程序P读取字符串S和结束标记0，它在输出带的第一帧输出1并停止，这表示程序P接受字符串S.6，9.1.1随机存取存储器，3。内存程序消耗标准，标准1:统一消耗标准在统一消耗标准下，每个内存指令需要一个单位时间；每个寄存器占用一个单位空间。除非另有说明，内存程序的复杂性将根据统一的消耗标准来衡量。标准2:日志成本标准日志成本标准基于这样的假设，即执行一条指令的成本与以二进制表示的指令的操作数长度成比例。在内存计算模型下，假设一个寄存器可以容纳任意大小的整数。因此，如果l(i)是整数I所占用的二进制位数，那么随机存取存储器P

4、rOgRAM 7，9.1.2机的结构就是RASP，1和RASP，RASP的整体结构与ram相似，但区别在于RASP程序存储在寄存器中。每个RASP指令占用两个连续的寄存器。第一寄存器存储操作码的代码，第二寄存器存储地址。RASP指令用整数编码。2。无论是在统一成本标准下还是在对数成本标准下，随机存取存储器程序和随机存取存储器程序的复杂性只是一个不变的因素。一个计算模型下在T(n)时间内完成的输入输出映射可以在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况类似。8，9.1.3图灵机，9，9.1.3图灵机，根据有限状态控制器的当前状态和每个读写头读取的符号，

5、图灵机的一个计算步骤可以实现以下三个操作中的一个或全部。(1)改变有限状态控制器中的状态。(2)清除当前读写头下的原签名框，写一个新的签名框。(3)独立地将任意一个或所有读写头向左(l)或向右(r)移动，或者停止在当前单元。带k带的图灵机可以正式描述为一个7元组(Q，t，I，b，q0，qf)，其中： (1)Q是一组有限状态。(2)T是带符号的有限集合。(3)I是输入符号的集合。(4)b是唯一的空白字符，BT-I. (5)q0是初始状态。(6)qf终止(或接受)。(7)是一个移动函数。这是一个从QTk的子集映射到Q (TL，r，s) k的函数。，10，9.1.3图灵机，图灵机m的时间复杂度T(n

6、)是处理长度为n的所有输入所需的最大计算步骤数。如果图灵机没有为长度为n的输入停止，则T(n)对这个n值没有定义。图灵机的空间复杂度S(n)是当它处理长度为n的所有输入时，在k条带上使用的平方数的总和。如果某个读/写头无限期地向右移动而没有停止，则S(n)是未定义的。与内存模型类似，图灵机既可以用作语言接收器，也可以用作计算函数的设备。一般来说，多项式时间算法可以解决的问题被认为是容易的问题，而需要超多项式时间才能解决的问题被认为是困难的问题。有许多问题，似乎不比排序或图形搜索更难。然而，到目前为止，人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要一个超多项式时间的下界

7、。在图灵机计算模型下，这类问题的计算复杂度是未知的。为了研究这类问题的计算复杂性，人们提出了另一种能力较强的计算模型，即非确定性图灵机计算模型，简称NDTM(Non-determinative Turing Machine)。在不确定的图灵机计算模型下，许多问题可以在多项式时间内解决。12，9.2.1不确定图灵机，不确定图灵机(NDTM):带K带的不确定图灵机M是一个7元组：(q，t，I，b，q0，qf)。与确定性图灵机不同，非确定性图灵机允许移动函数是不确定的，即对于每个值(q；X1，x2，xk)，当它属于这个域时，就有一个唯一的子集(q；X1，x2，xk)。可以在(q；X1，x2，xk)作

8、为其函数值。在图灵机计算模型中，移动函数是单值的，也就是说，对于QTk中的每个值，当它属于该域时，只有Q(TL，R，S)k中的唯一值与之对应。这个图灵机被称为确定性图灵机，缩写为DTM(确定性图灵机)。13，9 . 2 . 2 P和NP语言的定义：P=L|L是一种在多项式时间内可以被DTM接受的语言。NP=L|L是一种在多项式时间内可以被NDTM接受的语言。因为确定性图灵机可以被视为非确定性图灵机的特例，所以它可以在多项式时间内被确定性图灵机所接受。因此是NP。14、9.2.2和NP语言，NP语言给出了无向图的团问题的例子。这个问题的输入是一个有n个顶点和一个整数K的无向图G=(V，E)，需要

9、确定图G是否包含一个有K个顶点的完全子图(团)，也就是说，要确定VV是否存在，|V|=k，对于所有的U和vV，都有(U，V) E.如果图G用邻接矩阵表示，整数K用二进制串表示，那么团问题的一个例子可以用有长度的二进制串表示。因此，CLUSY问题可以用下面的语言来表达：CLUSY=w # v | w，v0，1*。以w为邻接矩阵的图G有一个包含k个顶点的团，其中V是k、15、9.2.2和NP语言的二进制表示，接受CLUSY的不确定性算法：用不确定性选择指令选择包含k个顶点的候选顶点子集V，然后确定性地检验这个子集是否是CLUSY问题的解。该算法分为三个阶段：第一阶段，对输入字符串w#v进行分解，计

10、算n=和v表示的整数k。如果输入没有w#v或|w|不是一个平方数，输入将被拒绝。显然，第一阶段可以及时完成。在算法的第二阶段，不确定地选择v的k元子集VV。算法的第三阶段是确定性地检查v的团属性。如果v是一个群，接受输入，否则拒绝输入。这显然可以及时完成。因此，整个算法的时间复杂度为。非确定性算法在多项式时间内接受CLUSE语言，因此CLIQUENP。，16，9.2.3多项式时间验证，VP=L|L*，是一个有限字符集，有一个多项式p和一个多项式时间验证算法A(X，Y)，因此对于任何X*，XL当且仅当Y*，|Y|p(|X|)和A(X，Y)=1存在。多项式时间可验证语言类VP可以定义为：定理9-1

11、: VP=NP。例如(哈密尔顿电路问题):无向图G包含哈密尔顿电路吗？无向图G的哈密尔顿电路是一个简单的电路，它只通过G的每个顶点一次。该问题可用语言HAM-CYCLE定义如下：HAM-CYCLE=G|G包含哈密尔顿电路，17，9.3NP完全问题，PNP。直观地说，P型问题在确定性计算模型下是容易解决的问题，而NP型问题在非确定性计算模型下是容易验证的问题。大多数计算机科学家认为名词短语类包含不属于名词短语类的语言，即名词短语。NP完全问题的一个令人惊讶的性质是，如果一个NP完全问题可以在多项式时间内解决，那么NP中的每个问题都可以在多项式时间内解决，即P=NP。目前多项式时间算法不存在NP完

12、全问题。18，9.3.1多项式时间变换，定义：语言l是NP完全的当且仅当(1)LNP；(2)所有低噪声点都有低功率点。如果语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。由所有NP完全语言组成的语言类被称为NP完全语言类，被记录为NPC。set，是2种语言。所谓语言可以在多项式时间内转换成语言(缩写为P)，意味着有一个镜像f:并且F满足：(1)有一个多项式时间的确定性图灵机用于计算F；(2)对于所有x，x，当且仅当f(x)。19，9.3.1多项式时间变换，定理9-2:假设l是NP完全的，那么(1)LP是当且仅当PNP；(2)如果Lp是NP，那么NP是完全的。(2)定理可

13、以用来证明问题的NP完全性。但前提是必须有第一个NP完全问题l，20，9。3.2一些典型的NP完全问题，部分NP完全问题树，21，到目前为止，还没有多项式时间算法来求解所有的NP完全问题。对于这类问题，通常可以采用以下策略。(1)仅用特殊例子解决问题(2)使用动态规划法或分枝定界法(3)使用概率算法(4)仅寻求近似解(5)使用启发式方法解决，9.4 NP完全问题近似算法，22，9.4.1近似算法性能，如果一个优化问题的最优值是c*，则近似算法获得的近似解解决问题。在正常情况下，性能比是问题输入规模n的函数(n)，即(n)。近似算法的相对误差定义为=。如果有一个函数(n)使得(n)成为问题的输入

14、规模n，那么(n)被称为近似算法的相对误差界。性能比(n)和相对误差界(n)之间显然存在以下关系：(n)(n)-1。23，9.4.2顶点覆盖问题的近似算法，问题描述：无向图G=(V，E)的顶点覆盖是其顶点集vV的子集，因此如果(U，V)是G的边，那么VV或uV。顶点覆盖V的大小是它包含的顶点数|V|。顶点集近似顶点集(图g)cset=；e1=g.e而(e1！=)取e1的任何边(u，v );cset=csetu，v；从e1中删除所有与u和v相关的边；返回c，Cset用于存储顶点覆盖中的每个顶点。最初为空，从边集e1中连续选择一条边(u，v)，将边的端点添加到cset，并删除e1中由u和v覆盖的边

15、，直到cset覆盖所有边。也就是说，e1为空。24，9.4.2顶点覆盖问题的近似算法。图(a)和(e)说明了算法的运行过程和结果。(e)表示由算法生成的近似最优顶点覆盖cset，它由顶点b、c、d、e、f和g组成.(f)是图G的最小顶点覆盖，它只包含三个顶点：b，d和e，算法的性能比为2。25，9.4.3旅行商问题的近似算法，问题描述：给定一个完全无向图G=(V，E)，每边(U，v)E有一个非负整数成本c(u，V)。寻找g的最小代价哈密顿回路例如，代价函数c通常具有三角不等式的性质，即对于任意三个顶点u，v，wV，有：c(u，w)c(u，v) c(v，w)。当图G中的顶点是平面上的一个点，并且

16、任意两个顶点之间的代价是这两个点之间的欧氏距离时，代价函数C具有三角不等式的性质。旅行商问题的一些特殊性质：满足三角不等式的26，1旅行商问题。对于给定的无向图G，我们可以用寻找图G的最小生成树的算法来设计一个寻找近似最优旅行商循环的算法。(1)选择g的任意顶点r；(2)用Prim算法找出以R为加权图G根的最小生成树T；(3)通过遍历序言中的树t获得的顶点表l；(4)在表格L的末尾加上R，根据表格L中的顶点顺序形成一个循环H，并将其作为计算结果返回；当成本函数满足三角不等式时，算法找到的旅行商循环的成本不会超过最优旅行商循环成本的两倍。27，(b)表示找到的最小生成树t；(c)指示穿越t的顺序

17、；由l产生的哈密顿回路h；在一般的旅行商问题中，没有多项式时间近似算法来求解具有常数性能比的旅行商问题，除非P=NP。换句话说，如果是概率神经网络，对于任何常数为1的旅行商问题，都没有多项式时间近似算法。29，9.4.4集合覆盖问题的近似算法，问题描述：给定一个完全无向图G=(V，E)，每边(U，v)E有一个非负整数代价c(u，V)。摘要：集合覆盖问题的一个例子是求G. X的最小代价哈密尔顿电路，它由一个有限集合X和X的子集族F组成。子集族F覆盖有限集合X。也就是说，X中的每个元素至少属于F的一个子集，即X=1。对于f中的子集CF，如果C中X的子集覆盖X，即X=，那么C覆盖X。集合覆盖问题是找出集合覆盖问题的近似算法，它覆盖f中X的最小子集C*，使得| C *