计算机算法分析与设计 第9章.ppt

1 第9章NP完全性理论与近似算法 2 学习要点理解RAM RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念理解NP完全问题的概念理解近似算法的性能比及多项式时间近似格式的概念通过范例学习NP完全问题的近似算法 1 顶点覆盖问题 2 旅行售货员问题 3 集合覆盖问题 4 子集和问题 3 在计算机算法理论中 最深刻的问题之一是 从计算的观点来看 要解决的问题的内在复杂性如何 它是 易 计算的还是 难 计算的 若知道了一个问题的计算时间下界 就可以较正确地评价解决该问题的各种算法的效率 进而确定对已有算法还有多少改进的余地 在许多情况下 要确定一个问题的内在复杂性是相当困难的 但问题的计算复杂性可以通过解决该问题所需计算量的多少来度量 4 如何区分一个问题是 难 还是 易 人们通常将在多项式时间内解决的问题看作是 易 解决的问题 而将需要指数时间解决的问题看作是 难 问题 这里是针对问题的规模而言 对于实际遇到的很多问题 人们至今未确切地了解其内在的计算复杂性 只能用分类的方法 将计算复杂性大致相同的问题 归类研究 5 计算模型 在进行问题的计算复杂性分析之前 首先必须建立求解问题所用的计算模型 包括定义该计算模型中所用的基本运算 建立计算模型的目的 是为了使问题的计算复杂性分析 有一个共同的客观尺度 3个基本计算模型 随机存取机RAM RandomAccessMachine 随机存取存储程序机RASP RandomAccessStoredProgramMachine 图灵机 TuringMachine 这3个计算模型在计算能力上是等价的 但在计算速度上是不同的 6 NP完全问题 7 新千年的七个数学问题 1900年在巴黎召开的 国际数学家大会 上 Hilbert提出著名的23个数学问题 深刻影响 和推动 了20世纪的数学发展 在新千年来临之际 2000年5月24日 就在希尔伯特提出23个世纪难题之后的整整一百年后 在巴黎又宣布了新的7个数学问题 这次是由 柯莱数学研究所 http www claymath org ClayMath Inst Cambridge MA USA 宣布 为7个问题中的任一个解答设立一百万美元奖金 8 在这7个问题中 排在第一位的是P与NP问题 即P 问题即是可被 运行多项式时间的 一个算法解决的问题 多项式时间 运行时间最多是输入量的多项式函数 NP 问题即是有一个 可用多项式时间检验的 解答的问题 P NP 9 2 黎曼假设 RiemannHypothesis 黎曼Zeta 函数的非平凡零点的实部都是1 2 3 庞加莱猜想 PoincareConjecture 任意闭单连通3 流型同胚于3 球 4 霍奇猜想 HodgeConjecture 在非奇异复射影代数簇上 任一霍奇类是代数闭链类的有理线性组合 5 BSD猜想 BirchandSwinnerton DyerConjecture 6 奈维尔 斯托克斯方程 Navier StokesEquatoins 7 杨 米尔斯理论 Yang MillsTheory 证明诸量子杨 米尔斯场存在而且有一个大缺口 10 背景 计算机处理能力受限于内存大小与中央处理器速度等 导致算法本身的数据结构对于其执行效率有很大的影响 在分析算法时 主要以时间复杂度与空间复杂度两者为分析依据 随着计算器发展迅速 算法的空间复杂度已经不是那么重要的一件事 目前分析主要是在时间复杂度方面 P问题 线性时间或者多项式时间内能够解决的问题 如能够在O n O nlog2n O nk 数量级内解决的问题 它们都是以多项式时间为上界 NP问题 不能在多项式时间内解决的问题 如计算时间数量级为O n O 2n 不可解问题 图灵停机问题 任何计算机耗费任意时间不能解决 逻辑学家阿朗索 丘奇证明了所谓的判定问题也是不可解的 判定一个已知的语句是否表达一个算术的真值 决不可能有一般的过程 换句话说 能够输出所有算术真值的计算机是不存在的 P与NP问题 图灵 图灵奖及图灵奖获得者简介 1912年6月23日 出生于英国伦敦 1931年 1934年 在英国剑桥大学国王学院学习 1932年 1935年 研究量子力学 概率论和逻辑学 1935年 由于独立发现中心极限定理 获Smith奖 年仅23岁被选为剑桥大学国王学院院士 1936年 研究可计算理论 提出 图灵机 的构想 1936年 1938年 主要在美国普林斯顿大学做博士研究 涉及逻辑学 代数和数论等领域 1938年 1939年 返回剑桥从事研究工作 并应邀加入英国政府破译二战德军密码的工作 1940年 1942年 作为主要参与者和贡献者之一 在破译纳粹德国通讯密码的工作上成就杰出 并成功破译了德军U 潜艇密码 为扭转二战盟军的大西洋战场战局立下汗马功劳 1943年 1945年 担任英美密码破译部门的总顾问 1945年 应邀在英国国家物理实验室从事计算机理论研究工作 1946年 图灵在计算机和程序设计原始理论上的构思和成果 已经确定了他的理论开创者的地位 由于图灵的杰出贡献 他被英国皇室授予OBE爵士勋衔 1947年 1948年 主要从事计算机程序理论的研究 并同时在神经网络和人工智能领域做出开创性的理论研究 1948年 应邀加入英国曼彻斯特大学从事研究工作 担任曼彻斯特大学计算实验室副主任 1949年 成为世上第一位把计算机实际用于数学研究的科学家 1950年 发表论文 计算机器与智能 为后来的人工智能科学提供了开创性的构思 提出著名的 图灵测试 理论 1951年 提出生物增长的非线性理论研究 年仅39岁即被选为英国皇家学会会员 1953年 1954年 继续在生物和物理学等方面的研究 1954年6月7日 42岁 图灵死于家中的床上 床头有一个咬了一半的 在氰化物溶液中浸泡过的苹果 警方调查结论是自杀 一代英灵 就此过早离去 成为人类科学史上的一大遗憾 TuringAward 被公认为是计算机科学界的诺贝尔奖 最高奖项 奖励在计算机科学技术研究中做出了创造性贡献的杰出科学家 1966年开始由ACM设立 美国计算机协会 1947年成立 与IEEEComputerSociety并列为计算机界最著名的两大国际学术组织 用Turing的名字来命名该奖 以纪念这位伟人对于计算机科学技术发展的功绩 通常每年1名获奖者 偶尔2名 同方向 02年3名 RSA Rivest Shamir Adelman 虽未明确规定 但授奖较偏重于计算机科学理论和软件技术方面作出贡献的科学家 唯一华人获奖者是姚期智 AndrewYao 美籍 2000年 1972 E W Dijkstra 美Burroughs公司 求最短路径的Dijkstra算法 PV操作 结构化程序设计 goto有害 等1974 D E Knuth stanford 算法最早的奠基人之一 现代 算法 与 数据结构 等名词及内涵的提出 KMP算法 多卷算法巨著的作者 LR k 文法 Tex编辑器等 1976 M O Rabin 以色列人 D S Scott 英国人 师兄弟 导师A Church 非确定有穷自动机的提出 判定问题等 Rabin 计算复杂性概念的雏形 随机算法的思想奠定 寻找及判定素数算法 单向函数等 Scott 语义学等 1978 R W Floyd Stanford Heap sort算法 求最短路径的Floyd动态规划算法等 编译及优化 优先文法等 程序正确性证明等 1982 S A Cook 加Toronto大学 NP 完全 概念的提出与理论的奠定 算法复杂性等 1984 N Wirth 瑞士苏黎世高工 程序 算法 数据结构 结构化程序设计分 创始人 ExtendedBNF等 Pascal之父 1985 R M Karp UC Berkeley 计算机系 数学系 工业工程运筹学系 三栖教授 哈佛文学士 理学硕士 数学博士 分枝限界法的创始人 与Held Rabin Karp子串匹配算法 求网络最大流的Edmonds Karp算法 NP 完全理论 Karp规约等 随机算法 并行算法等 1986 J E Hopcroft Cornell R E Tarjan Princeton 图论算法 e g 深度优先算法 连通性 平面图判定 数据结构Hopcroft 形式语言与自动机名著作者 与Ullman 算法名著作者 与Aho Ullman 算法好坏的衡量尺度 渐进时间复杂性 2 3树 机器人等 Tarjan D E Knuth的博士生 集合的Union find算法 平摊分析 持久性数据结构及各种数据结构 e g 动态树 八字型 树 自调整结构 1993 J Hartmanis Cornell R E Stearns Albany 计算复杂性理论的主要奠基人 系统化的理论体系及命名 Hartmanis Hartmanis矩阵乘法 Hartmanis快速离散傅立叶变换 Stearns 首先提出将上下文无关文法理论应用于编译器设计等 2000 AndrewYao 姚期智 Princeton 现在清华 计算复杂性 量子计算 密码学 e g 单向函数 通信理论等 2002 RonaldL Rivest AdiShamir LeonardM Adelman 公共密钥算法 RSA算法是当前在互联网传输 银行以及信用卡产业中被广泛使用的安全基本机制 22 图灵机 A Turing在1936年介绍了这样一个通用的计算模型 该模型具有以下两个性质 该模型的每个过程都是有穷可描述的 过程必须是由离散的 可以机械执行的步骤组成 图灵机是计算机的一种简单数字模型 尽管简单 但它具有模拟通用计算机的计算能力 通过研究TM来研究递归可枚举集和部分递归函数 为算法和可计算性研究提供了形式化描述工具 Finite control X 1 B B X 2 X n X i 带 tape 单元格 cell 带符 tapesymbol 读写头在每一时刻扫描带上的一个单元带有一个最左单元 向右则是无限的 带的每个单元可容纳一个带符号开始时 最左边n个单元装着输入 n 0 n为有限数 它是一个字符串 符号都选自 带符号 的一个子集 即所谓的 输入符号集合 余下的有穷个单元都存放空白符 它是一个特殊的带符号 但不是输入符号 图灵机的基本模型 24 图灵机的工作机制 在一个图灵机的动作中 图灵机根据带头 读写头 所扫描的符号和有限控制器的状态可能作改变状态在被扫描的带单元上重新写一个符号 以代替原来写在该单元上的符号 将带头向左或者右移一个单元 图灵机和双向有限自动机的区别 图灵机能改变它带上的符号 图灵机的形式化描述 有限状态集有限输入符号集有限带符号集转移函数开始状态特殊带符 空白符终态集合 q0 QT B TF Q 转移函数 Q Q L R 形式定义一个图灵机TM Turingmachine 是一个七元组M Q T q0 B F 函数示例 Q Q L R q ai p B L q p Q q ai p b R ai b 格局用w1qw2描述图灵机的瞬间工作状态 瞬像 q为M的当前状态 w1w2 w1w2是当前时刻从开始端 因为可写 到右边空白符号为止的内容当读写头已达到带的右端 则w1w2为读写头以左的内容 约定 w1qw2表示读写头正扫描w2的最左字符w2 则表示读写头正扫描一个空白字符 图灵机的函数与格局 27 图灵机的格局 给定图灵机M Q T q0 B F 定义格局之间的推导关系 M如下 1 设 q Xi p Y L 则有X1X2 Xi 1qXiXi 1 Xn MX1X2 Xi 2pXi 1Y Xn 但有如下两个例外 1 i 1时 qX1X2 Xn MqYX2 Xn 和 2 i n及Y B时 X1X2 Xn 1qXn MX1X2 Xn 2pXn 1B 28 2 设 q Xi p Y R 则有X1X2 Xi 1qXiXi 1 Xn MX1X2 Xi 1YpXi 1 Xn 但有如下两个例外 1 i n时 X1X2 Xn 1qXn MX1X2 Xn 1YpB 和 2 i 1及Y B时 qX1X2 Xn MBpX2 Xn 1Xn 图灵机接受的语言 L M T 且q0 1p 2 p F 1 2 图灵机接受的语言是输入字母表中这样一些字符串的集合 初始时 这些字符串放在M的带上 M处于状态q0 且M的带头处在最左单元上 这些字符串将使M进入某个终止状态 假定 当输入被接受时 图灵机将停止 没有下一个动作 任给图灵机M Q T q0 B F 以及输入字符串w T 试问 对于w M是否停机 停机是指图灵机不存在下一个移动步 move 结论 图灵机的停机问题是不可解的 即不可判定的 结论 任给图灵机M 很容易构造一个图灵机M 使得L M L M 并满足 如果w L M 则对于w M 接受w并一定停机 如果没有特别指出 总是假定图灵机到达终态 接受态 后一定停机 但是 对不能接受的字符串 图灵机可能永不停止 只要M还在某个输入上运行 无法知道是因为运行的时间不够长而没有被接受 还是根本就不会停机 图灵机的停机问题 图灵机举例 例1 设语言L anbn n 1 设计图灵机接受L 思路 最初带上为aa abb bBBB n个an个b首先用x替换M最左边的a 再右移至最左边的b用y替换之 左移寻找最右的x 然后右移一单元到最左的a 重复循环 如果 1 当在搜寻b时 M找到了空白符B 则M停止 不接受该串 此时 a的个数大于b的个数 2 当将b改为y后 左边再也找不到a 此时 若右边再无b 接受 若仍有b 则b的个数大于a的个数 不接受 举例L anbn n 1 q0 a q1 x R q0 y q3 y R q1 a q1 a R q1 y q1 y R q1 b q2 y L q2 a q2 a L q2 y q2 y L q2 x q0 x R q3 y q3 y R q3 B q4 B R 例 aabb的接收格局序列q0aabb xq1abb xaq1bb xq2ayb q2xayb xq0ayb xxq1yb xxyq1b xxq2yy xq2xyy xxq0yy xxyq3y xxyyq3B xxyyq4 例2L 0n1n2n n 1 该图灵机的七元组形式为 M q0 q1 q2 q3 q4 q5 q6 0 1 2 0 1 2 X Y Z B q0 B q6 转移函数可由上图的转移图形式给出 转移图与转移表 35 其他图灵机模型 实际的 的图灵机模型单带图灵机 1TM 多带图灵机 kTM 随机存取机 RAM 实际的 单位时间内完成的工作量有一个多项式上界所有 实际的 计算模型多项式时间等价 36 多带图灵机 37 图灵机M的时间复杂性T n 是它处理所有长度为n的输入 所需的最大计算步数 如果对某个长度为n的输入 图灵机不停机 T n 对这个n值无定义 图灵机的空间复杂性S n 是它处理所有长度为n的输入时 在k条带上所使用过的方格数的总和 如果某个读写头无限地向右移动而不停机 S n 也无定义 图灵机既可作为语言接受器 也可作为计算函数的装置 38 问题变换与计算复杂性归约 通过问题变换技巧 可以将2个不同问题的计算复杂性联系在一起 将一个问题的计算复杂性 归结为另一个问题的计算复杂性 从而实现问题的计算复杂性归约 39 假设有2个问题A和B 将问题A变换为问题B是指 将问题A的输入 变换为问题B的适当输入 解出问题B把问题B的输出 变换为问题A的正确解 40 若用O n 时间能完成上述变换的第 1 和 3 步 则称问题A是 n 时间可变换到问题B 且简记为A n B 其中n通常为问题A的规模 大小 当 n 为n的多项式时 称问题A可在多项式时间内变换为问题B 特别地 当 n 为n的线性函数时 称问题A可线性地变换为问题B 41 命题1 计算时间下界归约 若已知问题A的计算时间下界为T n 且问题A是 n 可变换到问题B 即A n B 则T n O n 为问题B的一个计算时间下界 命题2 计算时间上界归约 若已知问题B的计算时间上界为T n 且问题A是 n 可变换到问题B 即A n B 则T n O n 是问题A的一个计算时间上界 问题变换与问题计算复杂性归约的关系 在命题1和2中 当 n o T n 时 问题A的下界归约为问题B的下界 问题B的上界归约为问题A的上界 42 P类与NP类问题 非确定性图灵机P类与NP类语言多项式时间验证 43 确定性图灵机 在图灵机计算模型中 是单值的 即对于Q Tk中的每一个值 当它属于 的定义域时 Q T L R S k中只有惟一的值与之对应 称这种图灵机为确定性图灵机 简记为DTM DeterministicTuringMachine 44 非确定性图灵机 NDTM 一个k带的非确定性图灵机M是一个7元组 Q T I b q0 qf 非确定性图灵机允许 具有不确定性 即对于Q Tk中每一个值 q x1 x2 xk 当它属于 的定义域时 Q T L R S k中有惟一子集 q x1 x2 xk 与之对应 可以在 q x1 x2 xk 中随意选定一个值作为它的函数值 非