《北京大学屈婉玲算法设计与分析最新课件07》由会员分享，可在线阅读，更多相关《北京大学屈婉玲算法设计与分析最新课件07（52页珍藏版）》请在金锄头文库上搜索。
1、第7章 NP完全性第7章 NP完全性 主要内容主要内容 Turing机Turing机 计算复杂性理论计算复杂性理论计算复杂性理论计算复杂性理论 NP完全性理论的基本概念NP完全性理论的基本概念 用NP完全性理论分析问题用NP完全性理论分析问题 NPNP难度难度NPNP难度难度 1 Turing机的定义Turing机的定义 基本模型双向无限带的基本模型双向无限带的Turing机机 M = 其中其中M = , 其中其中 Q 有穷状态集有穷状态集 有穷带字符集有穷带字符集 输入字符集输入字符集 B 空白字符空白字符, B 初始状态初始状态Qq0初始状态初始状态, q0 Q F 终结状态集终结状态集,
2、 F Q, qY, qN F : (QF) Q L R状态转移函数状态转移函数 : (QF) Q L,R 状态转移函数状态转移函数 Bx1x2x3 xnB带带 读写头读写头 2 有限状态控制器有限状态控制器 FSC 瞬时描述-格局(ID)瞬时描述-格局(ID) 1q 2表示此刻表示此刻Turing机的机的FSC处于状态处于状态q, 读写头指在串读写头指在串2 的第个字符的第个字符的第的第一一个字符个字符. 例如例如Turing机机 M 的某时刻的状态转移函数是的某时刻的状态转移函数是例如例如g机机的某时刻的状态转移函数是的某时刻的状态转移函数是 (q, xi) = (p,Y,L) 带上的字符串
3、为带上的字符串为 x1x2. xi. xn, 读写头指向字符读写头指向字符 xi, 则它的则它的 1 2 i n i 瞬间描述是瞬间描述是: x1x2 . xi-1q xi . xn? ? x1x2. xi-2 p xi-1Yxi+1 . xn ? 表示由左边的? 表示由左边的ID一步达到右边的一步达到右边的ID ? ?*表示由左边的表示由左边的ID经有限步达到右边的经有限步达到右边的ID? ? 表示由左边的表示由左边的ID经有限步达到右边的经有限步达到右边的ID 3 实例实例 设设 L= 0n1n | n 1 , 设计接受设计接受 L 的的 Turing机如下机如下: MM = Q = q0
4、, q1, q2, q3, qY, qN, 0 1 = 0, 1, = 0, 1, X, Y, B , FF = qY,qN 初始将字符串放在从初始将字符串放在从 1 到到 n 方格中方格中, FSC处在状态处在状态 q0, 读写头读写头 0 指向方格指向方格 1. 将第一个将第一个0改写成改写成 X, 然后带头向右扫描然后带头向右扫描. 遇到第 一个 遇到第 一个1, 将将1改为改为Y, 然后带头向左扫描然后带头向左扫描. 遇到第一个遇到第一个 X 改为向改为向, 右扫描右扫描. 这时进入下一个巡回这时进入下一个巡回. 每个巡回将一对每个巡回将一对 0 和和 1 改为改为 X 和和 Y, 直
5、直到接受或拒斥停机到接受或拒斥停机. 4 ,到接受或拒斥停机到接受或拒斥停机 实例（续）实例（续） 转移函数如下转移函数如下 01XYB01XYB q0(q1,X,R)qNqN(q3,Y,R)qN q1(q1,0,R)(q2,Y,L)qN(q1,Y,R)qN q2(q2,0,L)qN(q0,X,R)(q2,Y,L)qN 例如输入例如输入 0011Ti机动作如下机动作如下 q3qNqNqN(q3,Y,R)qY 例如输入例如输入 0011, Turing 机动作如下机动作如下： q00011 ? ? Xq1011 ? ? X0q111 ? ? Xq20Y1 ? ? q2X0Y1 ? ? Xq00Y
6、1 ? ? XXq1Y1 ? ? XXYq11 ? ? XXq2YY ? ? Xq2XYY ? ? XXq0YY ? ? XXYq3Y ? ? XXYYq3 ? ? XXYYqY 5 Turing机接受语言Turing机接受语言 被被M接受的语言接受的语言记作记作L(M)，是，是 *上的字的集合上的字的集合. 当这些字左端对齐方格当这些字左端对齐方格 1 放在带上放在带上, M处于状态处于状态 q0, M 的带的带 头指向方格头指向方格 1 时时 经过有限步经过有限步 M 将停机在接受状态将停机在接受状态 q即即头指向方格头指向方格 1 时时, 经过有限步经过有限步 M 将停机在接受状态将停机
7、在接受状态 qY, 即即 L(M)= | *, 1, 2 *( q0 ? ?* 1qY 2) 如果字如果字 不是不是L(M)中的字中的字 M可以不停机或停机在拒斥状态可以不停机或停机在拒斥状态如果字如果字 不是不是L(M)中的字中的字, M可以不停机或停机在拒斥状态可以不停机或停机在拒斥状态 qN. 基本基本 Turing 机可以推广为机可以推广为 k 条带的条带的 Turing 机机 DTM. 确定型确定型 Turing机可以推广到机可以推广到非确定型非确定型 Turing机机 NDTM. gg 6 基本Turing机的变种基本Turing机的变种 单向无限带的 Turing 机单向无限带的
8、 Turing 机 带方格从1开始, 向右无限长. 带方格从1开始, 向右无限长. 其它与基本其它与基本 TurinTuring g 机相同机相同. . 其它与基本其它与基本g g 机相同机相同 多带的 Turing 机多带的 Turing 机k 条双向带条双向带, k 个读写头个读写头, 其中其中 k 为大为大 于于 1 的常数的常数 初始将输入写在第初始将输入写在第一一条带的方格条带的方格 1 到到 n 内内于于 1 的常数的常数. 初始将输入写在第条带的方格初始将输入写在第条带的方格 1 到到 n 内内. 其它带为空其它带为空. 每个读写头扫描一条带每个读写头扫描一条带,可以改写被扫描方
9、格 的字符 可以改写被扫描方格 的字符, 读写头然后向左或向右移动一个方格读写头然后向左或向右移动一个方格. 读写头的动读写头的动, 作由作由 FSC 的状态及的状态及 k 条带所扫描的条带所扫描的 k 个字符来决个字符来决定定. FSC 7 FSC 实 例实 例 例1 例1 L = wcwR| w为为0-1字符串字符串, 设计接受设计接受 L 的的Turing机机 M1 和和 M使得使得 M 的时间复杂度为的时间复杂度为O(n) M 的空间复杂度为的空间复杂度为和和 M2, 使得使得 M1的时间复杂度为的时间复杂度为O(n), M2的空间复杂度为的空间复杂度为 O(log n). M 有有2
10、条带条带 把把左边的左边的复制到第复制到第2条带上条带上 当发现当发现时第时第M1有有2条带条带,把把 c 左边的左边的 w 复制到第复制到第2条带上条带上. 当发现当发现 c 时第时第 2条带的读写头向左条带的读写头向左, 输入带的读写头向右输入带的读写头向右. 比较两个带头的比较两个带头的 符号符号 如果符号如果符号一一样样 字符个数字符个数一一样样 M1接受接受 x M1至多作至多作符号符号, 如果符号样如果符号样, 字符个数样字符个数样, M1 接受接受 x. M1 至多作至多作 n+1 个动作个动作. 时间复杂度为时间复杂度为 n+1. 空间复杂度为 空间复杂度为 (n-1)/2 +
11、1. M 有有2条带条带 第第2条带作为二进制的计数器条带作为二进制的计数器 首先检查输入是首先检查输入是M2有有2条带条带, 第第2条带作为二进制的计数器条带作为二进制的计数器. 首先检查输入是首先检查输入是 否只有否只有1个个 c, 以及以及 c 左边和右边的符号是否一样多左边和右边的符号是否一样多. 然后逐 个比较 然后逐 个比较 c 左边和右边的字符左边和右边的字符, 用上述计数器找到对应的字符用上述计数器找到对应的字符. , 如果所有的字符都一样如果所有的字符都一样, M2接受停机接受停机. 空间复杂度为二进制 的计数器的占用空间 空间复杂度为二进制 的计数器的占用空间, 即即 O(
12、log n). 时间复杂度为时间复杂度为 O(n2). 8 计算复杂性理论计算复杂性理论 空间和时间复杂度的形式定义空间和时间复杂度的形式定义 确定型确定型Turing机机 计算复杂度的有关结果计算复杂度的有关结果计算复杂度的有关结果计算复杂度的有关结果 带压缩带压缩 线性加速线性加速线性加速线性加速 带数目的减少带数目的减少 9 确定型Turing机确定型Turing机 空间复杂度的形式定义空间复杂度的形式定义空间复杂度的形式定义空间复杂度的形式定义 $ 通常反之亦真通常反之亦真. 18 组合优化问题与判定问题组合优化问题与判定问题 组合优化问题组合优化问题 * 由由3部分组成部分组成: (
13、1) 实例集实例集D(1) 实例集实例集D * (2) I D *, 有一个有穷非空集 有一个有穷非空集 S(I), 其元素称作其元素称作 I 的可行解的可行解 (3) S(I) 有一个正整数有一个正整数 ( ) 称作称作的值的值(3) s S(I), 有一个正整数有一个正整数 c(s), 称作称作 s 的值的值 如果如果 s* S(I), 对所有的对所有的 s S(I), 当当 *是最小是最小 ( 大大 ) 化问题时化问题时, ( *) ( )( ( *) ( ) )c(s*) c(s) ( c(s*) c(s) ) 则称则称 s*是是 I 的最优解的最优解, c(s*)是是 I 的最优值的
14、最优值, 记作记作OPT(I). *对应的判定问题对应的判定问题 = 定义如下定义如下: D = (I, K) | I D *, K Z*, 其中 其中Z*是非负整数集合是非负整数集合. 当当 *是最小化问题时是最小化问题时, Y = (I, K) | OPT(I) K ; 当当 *是最大化问题时是最大化问题时, Y = (I, K) | OPT(I) K . () |( ) 19 7.1.3 NP类类 (di i ili l)(nondeterministic polymial) 定义定义7 2 所有多项式时间可解的判定问题组成的问题类称所有多项式时间可解的判定问题组成的问题类称定义定义7.
15、2 所有多项式时间可解的判定问题组成的问题类称所有多项式时间可解的判定问题组成的问题类称 作作 P类类. 定义定义设判定问题设判定问题如果存在两个输入变量的如果存在两个输入变量的定义定义7.3 设判定问题设判定问题 = , 如果存在两个输入变量的如果存在两个输入变量的 多项式时间算法多项式时间算法 A 和多项式和多项式 p，对每一个实例，对每一个实例 I D, I Y 当当 且仅当存在且仅当存在| | (|I|) 且且 A对输入对输入 I 和和 输出输出“Y ” 则则且仅当存在且仅当存在 t, |t| p(|I|), 且且 A 对输入对输入 I 和和 t 输出输出“Yes”, 则则 称称 是是多项式时间可验证的多项式时间可验证的, A是是 的的多项式时间验证算法多项式时间验证算法, 而当而当 I Y 时时 称称 t 是是 I Y 的的证据证据而当而当 I Y 时时, 称称 t 是是 I Y 的的证据证据. 由所有多项式时间可验证的判定问题组成的问题类称作由所有多项式时间可验证的判定问题组成的问题类称作 NP 类类. HC(哈密顿回路哈密顿回路), TSP(货郎货郎), 0-1背包背
