第9章 NP完全理论

算法设计与分析授课教师：王秋芬办公地点：7307Email:[e-mail]第九章NP完全理论目录易解问题和难解问题P类和NP类问题NP完全问题NP完全问题的近似算法教学目标理解易解问题和难解问题理解P类与NP类的概念理解NP完全问题的概念理解近似算法的性能比及相对误差的概念通过实例理解NP完全问题的近似算法学习NP完全理论的意义今天，NP-complete一词已经成为算法设计者在求解规模大而又复杂困难的问题时所面临的某种难以逾越的深渊的象征。2000年初，美国克雷数学研究所的科学顾问委员会选定了七个“千年大奖问题”，该研究所的董事会决定建立七百万美元的大奖基金，每个“千年大奖问题”的解决都可获得百万美元的奖励。克雷数学研究所“千年大奖问题”的选定，其目的不是为了形成新世纪数学发展的新方向，而是集中在数学家们梦寐以求而期待解决的重大难题上。NP完全问题排在百万美元大奖的首位，足见它的显赫地位和无穷魅力。现在，人们已经认识到，在科学和很多工程技术领域里，常常遇到的许多有重要意义而又没有得到很好解决的难题是NP完全问题。另外，由于人们的新发现，这类问题的数目不断增加。易解问题和难解问题人们将存在多项式时间算法的问题称为易解问题，将需要在指数时间内解决的问题称为难解问题。目前，已经得到证明的难解问题只有两类：不可判定问题和非决定的难处理问题值得注意的是，通常人们在实际中遇到的那些难解的且有重要实用意义的许多问题都是可判定的（即可求解），且都能用非决定的计算机在多项式时间内求解。不过，人们还不知道，是否能用决定的计算机在多项式时间内求解这些问题，这类问题正是NP完全性理论要研究的主要对象。P类问题★定义2如果对于某个判定问题‘，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到是或否的答案，则该判定问题’是一个P类问题。从定义2可以看出，P类问题是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。例如最短路径判定问题(SHORTESTPATH)就属于P类问题。NP类问题★定义4如果对于某个判定问题，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个不确定算法，得到是或否的答案，则该判定问题是一个NP类问题。从定义4可以看出，NP类问题是一类能够用不确定算法在多项式时间内求解的判定问题。对于NP类判定问题，重要的是它必须存在一个确定算法，能够以多项式时间来验证在猜测阶段所产生的答案。P类问题和NP类问题的关系（1）P类问题可以用多项式时间的确定性算法来进行判定或求解。（2）NP类问题可以用多项式时间的不确定性算法来进行判定或求解，关键是存在一个确定算法，能够以多项式的时间来验证在猜测阶段所产生的答案。大多数研究者相信NP类是比P类要大得多的集合NP完全问题NP完全问题是NP类问题的一个子类，是更为复杂的问题。该类问题有一种奇特的性质：如果一个NP完全问题能在多项式时间内得到解决，那么NP类中的每个问题都可以在多项式时间内得到解决，即P=NP成立！。这是因为，任何一个NP问题均可以在多项式时间内变换成NP完全问题。多项式变换技术★定义5令是一个判定问题，如果：（1）NP，即问题属于NP类问题（2）对NP中的所有问题‘，都有'∝p则称判定问题是一个NP完全问题，简记为NPC。如果问题Q1的任何一个实例，都能在多项式时间内转化成问题Q2的相应实例，从而使得问题Q1的解可以在多项式时间内利用问题Q2相应实例的解求出，称问题Q1是可多项式变换为问题Q2的，记为Q1∝pQ2，其中p表示在多项式时间内完成输入和输出的转换。多项式变换关系是可传递的。典型的NP完全问题Cook在他1971年的论文中指出：所谓的合取范式可满足性问题就是NP完全问题。几个典型的NP完全问题。（1）图着色问题COLORING（2）路径问题LONG-PATH（3）顶点覆盖问题VERTEX-COVER（4）子集和问题SUBSET-SUM（5）哈密尔顿回路问题HAM-CYCLE（6）旅行商问题TSP（7）装箱问题BIN-PACKINGNP完全问题的近似解法一般来说，近似算法所适应的问题是最优化问题，即要求在满足约束条件的前提下，使某个目标函数值达到最大或者最小。对于一个规模为n的问题，近似算法应该满足下面两个基本的要求：（1）算法的时间复杂性：要求算法能在n的多项式时间内完成。（2）解的近似程度：算法的近似解应满足一定的精度。通常，用来衡量精度的标准有近似比和相对误差。顶点覆盖问题算法的设计思想：以无向图G为输入，计算出G的近似最优顶点覆盖。用集合Cset来存储顶点覆盖中的各顶点。初始时Cset为空，边集E1=E，然后不断从边集E1中选取一条边(u，v)，将边的端点u和v加入Cset中，并将E1中与顶点u和v相邻接的所有边删去，直至Cset已覆盖E1中所有边，即E1为空时算法停止。显然，最后得到的是顶点集Cset是无向图G的一个顶点覆盖，由于每次把尽量多的相邻边从边集E1中删除，可以期望Cset中的顶点数尽量少，但不能保证Cset中的顶点数最少。顶点覆盖问题的近似算法的性能比为2。装箱问题设有n个物品w1,w2,…,wn和若干个体积均为C的箱子b1,b2,…,bk,…。n个物品的体积分别为s1,s2,…,sn且有si≤C(1≤i≤n)。要求把所有物品分别装入箱子且物品不能分割，使得占用箱子数最少的装箱方案。算法设计方案：首次适宜法（近似比小于2）、最适宜法（近似比小于2）、首次适宜降序法和最适应降序法旅行商问题问题描述：给定一个无向带权图G=(V，E)，对每一个边(u，v)E，都有一个非负的常数费用c(u，v)0，求G中费用最小的哈密尔顿回路。可以把旅行商问题分为两种类型：如果图G中的顶点在一个平面上，任意两个顶点之间的距离为欧几里德距离。那么，对于图中的任意3个顶点u、v、wV，其费用函数具有三角不等式性质：c(u，v)≤c(u，w)+c(w，v)。通常把具有这种性质的旅行商问题称为欧几里德旅行商问题，反之，把不具有这种性质的旅行商问题称为一般的旅行商问题。欧几里德旅行商问题的近似算法设计算法的设计思想：在图中任选一个顶点u，用Prim算法构造图G的以u为根的最小耗费生成树T，然后用深度优先搜索算法遍历最小耗费生成树T，取得按前序遍历顺序存放的顶点序列L，则L中顺序存放的顶点号即为欧几里德旅行商问题的解。算法的近似比小于2.集合覆盖问题集合覆盖问题是对许多常见的组合问题的抽象。例如，假设X表示解决某一问题所需的各种技巧的集合，且给定一个可用来解决该问题的人的集合，其中每个人掌握若干种技巧。希望从这些人的集合中选出尽可能少的人组成一个委员会，使得X中的每一种技巧，都可以在委员会中找到掌握该技巧的人。这个问题的实质就是一个集合覆盖问题。算法设计令集合U存放每一阶段中尚未被覆盖的X中元素，集合C包含了当前已构造的覆盖。算法的求解步骤如下：（1）初始化，令U=X，C为空集；（2）首先选择子集族F中覆盖了尽可能多的未被覆盖元素的子集S；（3）将U中被S覆盖的元素删去，并将S加入C；（4）如果集合U不为空，重复步骤（2）和（3）。否则，算法结束，此时C中包含了覆盖X的F的一个子集族。容易证明，该算法的近似比为ln|X|+1。感兴趣的读者可自行分析。