《算法第十章from wang》由会员分享，可在线阅读，更多相关《算法第十章from wang（22页珍藏版）》请在金锄头文库上搜索。
1、10.1 基本概念10.1.1 不确定的算法10.1.2 NP-Hard和NP-Complete类10.3 NP-Hard问题实例第十章 NP-Hard和NP-Complete预备知识 算法时间复杂度的渐进表示 多项式时间算法与非多项式时间算法10.1 基本概念确定算法 运算结果是唯一确定的 之前介绍的算法都是确定算法 确定算法可以在确定型图灵机上执行不确定算法 运算结果不是唯一确定的 不确定算法可以在非确定型图灵机上执行10.1.1 不确定的算法图灵机 1936年图灵提出了一个抽象计算模型 图灵 机，并用它来精确定义可计算函数。图灵机的基 本思想是模拟人用纸笔进行数学运算的过程，这 个运算过
2、程可分解为下面两种简单的动作： 1.在纸上写或擦除某个符号； 2.把注意力从纸的一个位置移动到另 一个位置。 在每个阶段将由执行运算的人决定下一步的动 作，而他的决定依赖于此人当前所关注的是纸上 哪个位置的符号，以及此人当前思维的状态。 Turing MachineDeterministic Turing Machine定义 一台图灵机由一个八元组所组成 TM = ( Q, T, I, , b, q0, qaccept , qreject ) 其中 Q：一个有限状态集； T：一个有限符号集（字母表）； I：输入字符集，I T； b：空符，bTI； ：QT 的子集Q(TL, R, S)，即转移函
3、数 或有限状态控制函数，其中L, R表示读写头左移或右 移，S表示读写头原地不动； q0：表示初始状态； qaccepr：表示终止（接受）状态； qreject：表示拒绝状态。 这里规定是单值映射，所以也称为确定型图灵机。 一个例子例：设TM =(0,1,10,11,0,1,“ ”(空格), 0,1, 0)，做一个以 1的个数表示数值的整数加法运算,在磁带上的数据设为 0000001110110000，就是3+2的意思。转移函数定义如下： 0,0 0,0R 0,1 1,1R 1,0 10,1R 1,1 1,1R 10,0 11,0L 10,1 10,1R 11,0 E 11,1 0,0S 在
4、xx,y aa,bb 中，xx是当前状态，y是当前格子的值，aa是 程序下一步的状态，b是当前格的修改值。例如第一行指令 0,0 0,0R，意思就是如果机器读到格子的值是0，就将其仍 变成0，状态变为0，读写头向右移动一格。最后两行中的E 代表错误，S代表停机。 图灵机的格局序列（粗体的字符表示读写头的当前位置）步数 状态 磁带 步数 状态 磁带1 0 0000001110110000 9 1 00000011101100002 0 0000001110110000 10 1 00000011101100003 0 0000001110110000 11 10 0000001111110000
5、4 0 0000001110110000 12 10 00000011111100005 0 0000001110110000 13 10 00000011111100006 0 0000001110110000 14 11 00000011111100007 0 0000001110110000 15 0 0000001111100000 (停机)8 1 0000001110110000其他类型的图灵机 双向无限带图灵机。其带子向左向右都是无限 长的，与确定型图灵机基本模型不同的是，它的 带子没有左端、带头永远不会走出两端。 多带多头图灵机。它具有一个有穷控制器，k个 带头和k条带子，每条带
6、子都是双向无穷的，并且 各带头在操作时相互独立，除改写带符、左右移 动外，还可以保持不动。 非确定型图灵机。这种类型的图灵机具有一个 有限控制器和一条单向无限带，对于一个给定的 状态，机器的下一动作可以有穷多个选择，每个 选择包括一个新状态，一个要打印的带符号和一 个带头移动方向。非确定型图灵机定义: 一个非确定型图灵机（NDTM）由下述八元组给出：NDTM = (Q，T，I，b，q0，qaccept，qreject) 其中Q, T, I, b, q0 和qr 的定义与确定型图灵机的 相同，唯一的区别在于状态控制函数（转移函数）。非确 定型图灵机的状态控制函数 给出的下一个动作不是唯一确 定的
7、,即为多值映射,它的值域是一个有穷集合A。因此非确 定型图灵机在下一时刻的动作可以有多种选择。在处理问 题时，对于(q1, al, , ak)的多个值，非确定型图灵机对于其 中任意一个值都存在一个格局序列可以推导下去，只要其中 有一种可以到达终止状态qaccept ，就说该问题是可以处理的（ 输入字符串被接受或函数是可计算的）。 在SPARKS语言中增加： choice(S) failure success例10.1 不确定机上的检索算法例10.2 不确定机上的排序算法不确定算法的表示非确定机在现实技术条件下是不存在的，是为了 分析计算机复杂度难题而虚构的理论模型。可以设想非确定机在执行cho
8、ice(S) 语句时，具有 主动选择正确值（导致success）的能力，这是通 过同时复制大量副本实现的。非确定算法的设计思路一般是，先随机生成解， 再检查是否为答案。不确定算法的执行只关心唯一输出的不确定算法不确定的判定算法只产生0/1输出0:当且仅当没有一种选择可导致success1:当且仅当至少存在一种选择导致success输出隐含于success和failure，此外无输出语句最优化问题和判定问题是相互对应的，很多问题满足：判定问题在多项式时间内求解当且仅当 对应的最优化问题可以在多项式时间内求解，反之亦然不确定的判定算法不确定算法的时间复杂度可满足性问题 SAT可满足性问题时间复杂度
9、O(n)10.1.2 NP-Hard和NP-Complete 对于算法A，如果存在多项式P()，使得对A的 每个大小为n的输入，A的计算时间为O(P(n) ，则称A具有多项式时间复杂度。 P是所有可在多项式时间内用确定算法求解的 判定问题的集合。 NP是所有可在多项式时间内用不确定算法求 解的判定问题的集合。cook定理 【cook定理】可满足性(SAT)在P内，当且仅 当P=NP。SAT问题如果有多项式解，当且仅当P=NP约化（多项式变换）理解：算法L1约化为算法L2当且仅当存在一个多项式时间的确定算法可将算法L1转换为算法L2【算法L2的解决意味着L1的解决，反之不一定】【 L2 可能比L1更复杂】NP-Hard和NP-Complete 如果可满足性问题可约化为一个问题L，则L是 NP-Hard 如果L是NP-Hard 且LNP，则L是NP- Complete NP-Complete NP-Hard 有的问题，判定问题是NP完全，优化问题是 NP难度但非NP完全。NP-Hard非NP-Complete实例如何证明一个问题是NP-难度的证明L是NP-难度，只需证明一个已知的NP-难度问题可约化为L证明L是NP-完全，需首先证明L是NP-难度，在找到一个解决它 的多项式时间不确定算法
