第4章讲 NP完全性理论.ppt

1 第4章 NP完全性理论 解决问题时碰到的状况 没找到有效率的算法 原因 我太笨?? 问题本身就太难，不存在有效率的算法可解决?? 2 要点： 理解P与NP的问题 NP完全与约化 NP完全问题之范例 如何处理NP完全问题 3 可满足问题(SAT) 图着色问题 作业调度问题 装箱问题 背包问题 Hamiltonian 回路 TSP(旅行商)问题 图的匹配问题 顶点覆盖问题 NP完全问题之范例： 4 1.问题的分类 无解的 例如：停机问题（halting problem） 有解的 简单的 多项式时间复杂度之内:Ο(nk) 困难的 指数时间复杂度:Ο(2n) 5 指数时间复杂度算法的困难度： 问题描述 输入n个元素，其所需花费的时间至少是Ω (2n) 范例 如果n=10000，表示要执行210000个步骤 这样的时间数值是非常大，即使使用超级电脑可能也要跑上好几天才能执行完 指数灾难：计算量的指数增长 6 一个问题是简单或困难的判断： 往往只有一线之隔，有时用直觉的方式难以判断 范例 在一个加权图中，找出顶点x到顶点y的最短路径 可用贪心算法来解决 在一个没有循环的加权图中，找出顶点x到顶点y的最长路径 还没找到有效率之算法 判断问题:是或否的问题（yes-no question） 简单：是否存在一条从顶点x到顶点y的路径，使其路径的权值小于M？ 困难(？)：“是否存在一条从顶点x到顶点y的路径，使其路径的权值大于M？ 7 2. P类：属于P的问题 定义:P（deterministic polynomial time） 所有可以被决定型算法（deterministic algorithms）在多项式时间（polynomial time）内解决的问题之集合 决定型（deterministic） 不管在任何时间点，这个算法在做任何事时，该算法的下一步只有一件事可以做 目前我们实际使用的电脑其执行模式就是这个样子，这也是近代计算机科学最根本的理论基础 范例:排序的问题 插入排序算法T(n)=O(n2) 有效率的算法即属于P 某问题有n个输入，该问题的处理时间跟n的多项式成比例，即存在一个常数k，对任何n，T(n)=O(nk) 8 非决定型(nondeterministic)的电脑： 定义 当一个算法必须从数个选项中做选择，而且它拥有可以“猜”中正确的那个选项之能力。 比目前我们实际上所使用的决定型模式之电脑，还有更强大的功能 为了方便接下来的讨论，我们可以将非决定型机器上执行的算法，想像成它会“同时”对每个选项先“猜”一个解答，然后再“确认”这个解答到底对不对 10 4.典型的NP问题 问题1 图着色问题 判定问题：是否存在不超过k种颜色的着色方案? 优化问题：求图的最小着色数和着色方案 问题2 作业调度问题 判定问题：是否存在代价不超过k的作业调度? 优化问题：求最小代价调度 11 问题3 Bin packing问题：假设有n种物品，它们的尺寸分别为s1,…,sn，0si≤1另有任意多个箱子(Bins)，箱子的容量为1， 判定问题：任意给定k，是否存在一种装箱方法使用的箱子数≤k？ 优化问题：求使用最小箱数的装箱方法 12 问题4 背包问题 判定问题：是否存在效益值至少为k的可行子集? 优化问题：(见上一章) 问题5 子集和数问题s1,s2,┅,sn,C 判定问题：是否存在和数等于C的子集? 优化问题：求≤C的最大子集和数. 可归约为背包问题: pi=wi. 13 问题6 CNF(合取范式)——可满足问题(SAT) 判定问题：是否存在真假赋值使得该CNF为真. 合取范式例: (x11∧ x12∧ x13) ∨ (x21∧ x22 ) ∨ (x31∧ x32 ∧ x33) 问题7 Hamiltonian 回路 判定问题 问题8 TSP(旅行商)问题 判定问题：任意给定一整数k，是否存在一长度不超过k的Hamiltonian回路？ 优化问题 14 问题9:顶点覆盖:无向图中的每一条边都被某些节点关联 判定问题：给定无向图G和正整数k,是否存在一k节点覆盖. 优化问题：最小节点覆盖 问题10: 给定一无向图G, k-独立集;最大独立集. 问题11: 给定一无向图G , k-集团;最大集团. 问题10和11可互相转化: 边互补图 目标函数取整数值时,优化值问题和判定问题等价我们可用二分查找从判定问题解得到优化值问题的解 15 5. P与NP的关系 任何一个属于P的问题，也一定属于NP的问题 是否有某个问题是属于NP，但是不属于P呢？ 范例：最长路径“是或否” 的问题 选择某一条路径，在多项式时间内“确认”其值是否大于M，就是属于NP 但是到目前为止，仍找不到任何多项式时间的算法来解决它(不属