[理学]图论2.ppt

P, NP 和 NP-C问题 定义P, NP 和 NP-C中的问题类 分别例举 P, NP-C 里的一些问题. Turing机 图灵(A.M.Turing,1912-1954)： 幼年早熟，剑桥大学毕业不久即发表可计算理论的革命性著作，第二次世界大战中设计了一台破译希特勒军事密码的机器，使纳粹的军事机密屡屡被英国破译．１９３６年，他提出”Turing机”这一重要的数学概念，回答了什么是计算这个看似简单，实则十分深刻的问题，Turing机的精确定义是基于作计算时人的实际动作的模拟上． P, NP 和 NP-C问题 O(n3) 的算法不是坏算法，因为它还可以在一个能接受的时间内计算出一个较大规模的问题． 如果一个算法的最坏时间复杂度为O(p(n)),则称这个算法在多项式时间内可解决该问题,其中p(n)是n的多项式. 易解的问题(在多项式时间内能解决)和不易解的问题(在多项式时间内不能解决) 还没有找到有效算法，但也没有人能证明这样的算法不存在的问题类型． P, NP 和 NP-C问题 存在多项式时间算法解决该问题吗? 回答: yes no 可以证明所有算法都是指数时间的. 可以证明根本不存在算法来解决该问题. don’t know. 但如果能找到这样的算法,则它也能提供在多项式时间解决其他许多问题的一种方法 P, NP 和 NP-C问题 优化问题(Optimization problem): 构造一个最大化或最小化某个目标函数的解 判定问题(Decision problem) : 回答为是或否的问题. 如: 哈密尔顿圈(Hamiltonian circles): 无向图中的哈密尔顿圈是经过该图每个顶点正好一次的圈. 该判定问题为: 给定的无向图有哈密尔顿圈吗? 问题举例 许多问题既有判定问题版本,也有优化问题版本 旅行推销员问题 优化问题: 已给一个加权图,求最小权的哈密尔顿圈. 判定问题:已给一个加权图和一个整数k, 是否存在权不超过k的哈密尔顿圈? 背包问题 : 假设我们有一个容量为W (正整数) 的背包和 n 件重量为w1, …, wn, ,价值为 v1, …, vn 的物品,其中w1, …, wn,和 v1, …, vn 是正整数. 优化问题: 求能装入背包的物品集的子集,使该子集的总价值达到最大. 判定问题: 给定 k, 是否存在能装入背包的物品集的子集,其总价值至少为k? P类 P : 存在多项式时间算法解决的判定问题 为什么把多项式时间的存在性作为准则? 如果不, 非常无效 很好的封闭性 在强意义下与机器无关 什么是一个判定问题的可解性? 多项式时间之内可解/可判定 可解/可判定,但不易解 不可解决/不可判定的问题: 如, 停机问题 没有找到多项式时间算法,也没有证明不存在这样的算法. NP类 非严格地说, NP是一类判定问题, 任意设定一个输入对应的解, 能在多项式时间检测其是否真是一个解 严格说, NP: 能由非确定性多项式(nondeterministic polynomial )(NP)时间算法解决的判定问题 P 与 NP之间的关系 P ? NP P = NP? (NP ? P?) NP中的问题能在多项式时间之内解决吗? 倾向于 P ? NP NP-C问题 NP-C是一个术语,用来描述NP中最难的判定问题 如果一个NP-C问题有多项式时间算法,则NP中所有问题均有多项式时间算法. - 如 哈米尔顿圈问题(Hamiltonian cycle) 旅行推销员问题(Traveling salesman) 背包问题(Knapsack) 装箱问题(Bin packing) 图着色问题(Graph coloring) NP-C的非严格定义 非严格地,一个 NP-C问题是NP中任何其他问题一样难的问题,因为由定义,NP中任何其他问题都能在多项式时间内转化为该问题. 一个判定问题D1 被认为能在多项式时间内转化为判定问题D2,如果存在一个函数t把D1 的实例变换为D2 的实例使得 1. t 把 D1 的所有yes实例映射为D2 的 yes实例,把 D1 的所有no实例映射为D2 的 no实例 2. t 可用多项式时间算法计算 NP-C的严格定义 一个判定问题D被认为是 NP-C问题,如果 1. 它属于 NP类. 2. NP中每个问题都能在多项式时间只能转化为D. NP-C问题类被称为NPC. Cook定理 (1971): 发现了第1个 NP-C问题, CNF-满足问题. 证明一个判定问题是NPC问题，需要证明 　　１．这个问题是NP类 　　２.证明一个已知的NP-C问题能在多项式时间之内转化为该问题 总 结 算法的时间复杂度——从输入数据到计算出结果所需要的