复杂性理论

上节回顾 不确定算法 舍伍德法 数值概率算法 拉斯维加斯法 蒙特卡罗法 总能找到正确解 找到精度随时间增加而提高的近似解 找到的一定是正确解，但有时可能找不到解 蒙特卡罗法 所求解正确的概率随时间增加而提高 无法有效判定所求解是否正确

本节内容 有穷自动机 图灵机 P，NP，NP完全，NP难 近似算法

复杂性理论 分析问题复杂程度的一个学科 什么问题是好解决的问题？

回忆 有穷自动机 a,b

a,b a,b

a a,b b

设计 设计一个自动机，接受的语言为： 所有由a,b组成，并且有奇数个b的字符串

b a

图灵机 和自动机类似 可以在磁带上读写

图灵机 读写头 磁带 有限的符号集 {0,1,B} 有限的状态 但是可以随时延长 有限的符号集 {0,1,B} 有限的状态 初始状态 终止状态 推荐阅读 http://blog.csdn.net/mentat/archive/2005/04/15/348386.aspx 0 1 0 1 1 q

移动函数 左移 (q,s,q’,s’,L) 右移 (q,s,q’,s’,R) 不移 (q,s,q’,s’,-) 确定的图灵机 Deterministic Turing Machine 针对某一组(q,s)，移动方式只有一种

例1：二进制下的后继数 初始状态q0 终止状态q2

输入->输出，两种解释 解释一：看成计算一个函数 自变量x1，x2，…，xn先写在输入带上，图灵机经过计算，输出一个y后停机，那么就说图灵机计算了函数 f(x1，x2，…，xn)=y 解释二：当作一个语言接受器 将字符串S=a1a2…an写在输入带上。图灵机经过若干步计算，会在S属于语言L时进入一个终止状态，就说图灵机识别语言L。

例2：判断回文串 输入一个串 为回文串输出yes 否则no

非确定性图灵机(NDTM) 一组(q,s)可以对应多组转移方式，运行时随机选择一组。 很多原本用DTM不能在多项式时间内解决的问题，用NDTM可以在多项式时间内解决。

P类与NP类语言 P类和NP类语言的定义： P={L|L是一个能在多项式时间内被一台DTM所接受的语言} NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言} P与NP的关系

P类与NP类语言 P类和NP类语言的定义： P={L|L是一个能在多项式时间内被一台DTM所接受的语言} NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言} 确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故P  NP。

计算模型 在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。

基本计算模型： 随机存取机RAM(Random Access Machine) 随机存取存储程序机RASP(Random Access Stored Program Machine) 图灵机(Turing Machine) 这3个计算模型在计算能力上是等价的，但在计算速度上是不同的

问题的描述 普通问题 判定问题 Yes or No 最优化问题 最大化或者最小化 转换——相等元素，着色问题，最大团

例 整数序列中有无相同元素 判定版——存在两个相等元素吗？ 最优化版——出现频率最高的元素 如何解决？

例 无向图着色问题 判定版——可以用k种颜色着色么？ 最优化版——需要的最少颜色是多少？

例 最大团 判定版——存在k个顶点的团吗 最优化版——团最多的顶点数

结论 我们集中分析判定问题 对于最优化问题而言，一旦判定问题解决，我们常常可以用二分搜索把最优化问题解决

P类问题 确定性算法 P问题 P问题的补也是P问题 执行过程中每步选择唯一，不论执行多少次，结果保持不变 用确定性算法在多项式时间内可以解决的问题 P问题的补也是P问题

NP类问题 ？

不确定性算法 猜测阶段（不确定） 验证阶段（确定） 当猜对解的时候输出yes，如果输出no，则可能是猜错了解 在多项式时间内猜测一个结果 在多项式时间内验证该结果是否是合法形式 如果是则在多项式时间内验证是否是解 当猜对解的时候输出yes，如果输出no，则可能是猜错了解

NP类问题 可以在多项式时间猜测一个解（不确定），并在多项式时间内验证解的正确性 问题——解空间庞大

P与NP的关系

一个故事 有人问一个计算机科学家和她的丈夫：如果你在地下室，那么如何烧一壶开水？ 他们都回答：走去厨房，然后烧水。

一个故事 那么，那人接着问，如果你在厨房，如何烧一壶开水？ 计算机科学家的丈夫说：这很简单，在壶里装满水，然后开火。

一个故事 计算机科学家笑了，说，这个问题更简单，先走去地下室，然后我们已经知道在地下室如何烧一壶开水了。

NP完全问题(NPC) NP问题中最难的一系列问题 大多数的计算机科学家认为NP类中包含了不属于P类的语言，即P≠NP。 NP完全问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。 目前还没有一个NP完全问题有多项式时间算法。

多项式归约 如果X,X’是两个判定问题，存在一个确定性算法A，如果对于问题X猜测一个解I，则A将I在多项式时间内转换成X’的一个解I’，并且X’对I’回答yes时，X对I也回答yes，则称X多项式时间归约到X’ 即我们可以利用A，在多项式时间内，将问题X转换成X’来解决，X不会比X’更难解决，或者说X’不会比X更容易解决

两个概念 NP难（NP-Hard） NP完全（NP-Complete） P、NP、NP-Hard、NP-Complete的关系？

推论 要证明一个问题是NP完全的，只需要证明 该问题属于NP 存在一个NPC问题可以多项式规约成该问题

NP的证明 可以在NP时间内猜一个解 可以在P时间内验证这个解是否满足要求 注意：验证解比构造解容易得多

可满足性问题 NPC中的第一个问题 合取范式是否存在一个真值指派使它取值为真，即是否可以满足

例 哈密尔顿回路问题 旅行售货员问题判定版 已知哈密尔顿回路问题是NPC，证明旅行售货员问题也是NPC

证明 TSP是NP问题 多项式时间猜一个结果 多项式时间验证结果 HC可以多项式归约成TSP

更多NPC问题 团问题 顶点覆盖 子集和问题

NP完全问题的近似算法 迄今为止，所有的NP完全问题都还没有多项式时间算法。 怎么办？

NP完全问题的近似算法 迄今为止，所有的NP完全问题都还没有多项式时间算法。 对于这类问题，通常可采取以下几种解题策略： 只对问题的特殊实例求解 用动态规划法等技巧算法求解 用回溯法、分支限界法求解 用概率算法求解，如模拟退火、遗传算法等 只求近似解 用启发式方法求解

近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为= 。

顶点覆盖问题(VC)的近似算法 无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。 判定版本VC(D)：无向图是否存在大小为D的顶点覆盖 VC(D)是NPC

近似算法 e1里面存放图所有的边 e1中任取一边<u,v>，放入A，同时将e1中所有和u,v相连的边删除。重复至e1为空，

顶点覆盖问题的近似算法

分析 |cset|=2|A| |cset*|>=|A| |cset|<=2|cset*| 性能比=2 显然

旅行售货员问题近似算法 前提条件：满足三角不等式性质 对任意的3个顶点u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。

满足三角不等式的TSP 选择g的任一顶点r； 用Prim算法找出带权图g的一棵以r为根的最小生成树T； 前序遍历树T得到的顶点表L； 将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；

分析 C(T)<=C(H*) C(H)<=C(W) C(H)<=C(W)=2C(T)<=2C(H*) 性能比为2 T是最小生成树，H*去一边是生成树 C(H)<=C(W) 欧几里德距离 C(H)<=C(W)=2C(T)<=2C(H*) 性能比为2

C语言版双截棍 软考室的烟味弥漫 坐满了程序员 室里面的监考官 系分 已三年 出上午试题的老师 练cpu 耍单片机 硬件功夫最擅长 还会逻辑门三极管 他们学生我习惯 从小就耳濡目染 什么软件跟网络我都耍的有摸有样 什么语言最喜欢 c++面向对象 想要去英伦美帝 学图灵诺伊曼

C语言版双截棍 怎么编 怎么编 离散数学是关键 怎么编 怎么编 数值分析也较难 怎么编 怎么编 数据结构最重要 算法不学莫后悔 死的难看 一段代码写好 一个左子树 右子树 一句不会递归有危险 不停调用 一个优秀的库函 一用好多年 拷贝好带身边

C语言版双截棍 怎么编 怎么编 我学会动态规划 怎么编怎么编 分支限界的难关 怎么编怎么编 已被我一脚踢开 哼 快使用c语言 哼哼哈兮 快使用c语言 哼哼哈兮 编程之人切记 np无敌 是谁在练汇编 背指令集

C语言版双截棍 快使用c语言 哼哼哈兮 快使用c语言 哼哼哈兮 如果我会分治 快速解题 熟用堆栈队列 系统分析 快使用c语言 哼 我用vb描述 哼 万能的回溯法