chapter9NP完全问题.ppt

* HeJing(2011) School of Software School of Software, YunNan University 任课教师：何婧 Email: hejing@ynu.edu.cn Chapter 9 简介 一个问题的计算量是多少才能将其评估为真正的难题？ 如果一个问题不可能在少于指数时间内解决，则该问题可以认为是不易处理的难题。 求解问题所需要的时间是指数 或超指数函数： 2n或n! 特例：2n在n达到59之前 都小于n10 例2：货郎担问题（Traveling salesman problem) 给定n个城市，任意两个城市间有路相连，一个货郎从一个城市出发，不重复的遍历所有的城市并回到起点，求一条路程最短的路径。 加权完全图　　　　 ， ， 　　　 ，求Hamilton圈　 ，使得 计算复杂度：　　　　 判定问题与最优化问题 判定问题与最优化问题 输入：一个整数序列S 问题：在S中存在两个相等的元素吗？ 输入：一个整数序列S 问题：寻找在S中出现频率最高的元素 在NP问题的研究中，判定问题更容易分析 确定性算法与不确定性算法 确定性算法 设A是求解问题B的一个算法,如果在展示问题B的一个实例时,在整个执行过程中每一步都只有一个选择,则称A是确定性算法.因此如果对于同样的输入,实例一遍又一遍地执行,它的输出从不改变.通常我们在写程序时,用到的都是一些确定性算法,比如说排序算法,查找算法等. 确定性算法与不确定性算法 不确定性算法 猜测阶段:在这个阶段产生一个任意字任串Y,它可能对应于输入实例的一个解,也可以不对应解.事实上,它甚至可能不是所求解的合适形式,它可能在不确定性算法的不同次运行中不同.它仅仅要求在多项式步数内产生这个串. 验证阶段:在这个阶段,一个确定性算法验证两件事.首先,它检查产生的解串Y是否有合适的形式,如果不是,则算法停下并回答NO;另一方面,如果Y是合适形式,那么算法继续检查它是否是问题实例X的解,如果它确实是实例X的解,那么它停下并且回答YES,否则它停下并回答NO.我们也要求这个阶段在多项式步数内完成. P问题 P问题、NP问题与NP完全问题（NPC问题） P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间O(nk)内判定或解出，那么这个问题就属于P问题。 判定问题的P类问题 排序问题 不相交集问题 最短路径问题 2着色问题 NP问题 P问题、NP问题与NP完全问题（NPC问题） 有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。 显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。 NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解. NPC问题 P问题、NP问题与NP完全问题（NPC问题） NP完全问题是求NP中判定问题的一个子类.NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！ 哈密顿回路问题：给定一个无向图G，它有哈密顿回路吗 旅行商问题：给出一个n个城市的集合，且给出城市间的距离。对于一个整数k，是否存在最长为k的周游路线，每个城市恰好访问一次。 哈密顿回路问题是一个NPC问题，可以证明旅行商问题也是一个NPC问题。 * HeJing(2011) School of Software School of Software, YunNan University