计算机组成原理第1章剖析说课讲解.ppt

《计算机组成原理第1章剖析说课讲解.ppt》由会员分享，可在线阅读，更多相关《计算机组成原理第1章剖析说课讲解.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机组成原理第1章剖析教学安排教学安排3.3.3.3.习题讨论课习题讨论课习题讨论课习题讨论课 本学期内任选一道习题或实验题讲解自己的算本学期内任选一道习题或实验题讲解自己的算本学期内任选一道习题或实验题讲解自己的算本学期内任选一道习题或实验题讲解自己的算法，要求：法，要求：法，要求：法，要求：主动报讲解题号（至少提前一周）主动报讲解题号（至少提前一周）主动报讲解题号（至少提前一周）主动报讲解题号（至少提前一周）讲主要思路和创新点讲主要思路和创新点讲主要思路和创新点讲主要思路和创新点 有有有有pptpptpptppt 5 5 5 5分钟以内分钟以内分钟以内分钟以内 多人讲同一道题注意突出与别

2、人的差别多人讲同一道题注意突出与别人的差别多人讲同一道题注意突出与别人的差别多人讲同一道题注意突出与别人的差别 讲完后相关文档、程序或讲完后相关文档、程序或讲完后相关文档、程序或讲完后相关文档、程序或demodemodemodemo提交服务器提交服务器提交服务器提交服务器算法在计算机科学中的地位算法在计算机科学中的地位Computer science is the Computer science is the study of algorithmsstudy of algorithms,including:including:1.Their formal and mathematical p

3、roperties1.Their formal and mathematical properties2.Their hardware realizations2.Their hardware realizations3.Their linguistic realizations3.Their linguistic realizations4.Their applications4.Their applicationsGibbs,N.E.,and Tucker,A.B.“A Model Curriculum for a Liberal Arts Degree in Computer Scien

4、ce,”Comm.of the ACM,vol.29,no.3(March 1986).课程目标和内容课程目标和内容设设设设计计计计算算算算法法法法表表表表示示示示算算算算法法法法分分分分析析析析算算算算法法法法实实实实现现现现算算算算法法法法测测测测试试试试算算算算法法法法确确确确认认认认算算算算法法法法掌握算法复杂性和常用算法的基本理论知识掌握算法复杂性和常用算法的基本理论知识掌握算法复杂性和常用算法的基本理论知识掌握算法复杂性和常用算法的基本理论知识掌握算法分析和设计的基本方法掌握算法分析和设计的基本方法掌握算法分析和设计的基本方法掌握算法分析和设计的基本方法锻炼逻辑思维能力，培养运用算

5、法理论解决实际锻炼逻辑思维能力，培养运用算法理论解决实际锻炼逻辑思维能力，培养运用算法理论解决实际锻炼逻辑思维能力，培养运用算法理论解决实际问题的能力问题的能力问题的能力问题的能力课程目标和内容课程目标和内容1.算法概述算法概述2.递归与分治策略递归与分治策略3.动态规划动态规划4.贪心算法贪心算法5.回溯法回溯法6.分支限界法分支限界法7.随机化算法随机化算法8.近似算法近似算法课程参考书目课程参考书目算法设计与分析算法设计与分析算法设计与分析算法设计与分析（第（第（第（第2 2版）版）版）版）王晓东王晓东王晓东王晓东 编著编著编著编著清华大学出版社（清华大学出版社（清华大学出版社（清华大学

6、出版社（JavaJava描述）描述）描述）描述）算法导论算法导论算法导论算法导论（第（第（第（第2 2版）版）版）版）Thomas H.Cormer,Charles E.LeisersonThomas H.Cormer,Charles E.Leiserson等著等著等著等著潘金贵潘金贵潘金贵潘金贵 顾铁成等译顾铁成等译顾铁成等译顾铁成等译机械工业出版社机械工业出版社机械工业出版社机械工业出版社第第1章章 算法概述算法概述学习要点学习要点:理解算法的概念。理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法的计

7、算复杂性概念。掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述。掌握用掌握用C+语言描述算法的方法。语言描述算法的方法。了解了解NP类问题的基本概念。类问题的基本概念。第第1章章 算法概述算法概述1.1 基本概念基本概念1.2 算法复杂性分析算法复杂性分析1.3 用用c+描述算法描述算法1.4 算法分析方法算法分析方法1.5 NP完全性理论完全性理论1.1 基本概念基本概念-算法算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是算法是若干指令的有穷序列若干指令的有穷序列，满足性质：，满足性质：(1)输入输入：有：有外部提供的量

8、外部提供的量作为算法的输入。作为算法的输入。(2)输出输出：算法产生：算法产生至少一个量至少一个量作为输出。作为输出。(3)确定性确定性：组成算法的每条指令是：组成算法的每条指令是清晰，无歧义清晰，无歧义的。的。(4)有限性有限性：算法中每条指令的执行：算法中每条指令的执行次数是有限的次数是有限的，执行，执行每条指令的每条指令的时间也是有限的时间也是有限的。1.1 基本概念基本概念-程序程序(Program)程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)。例如例如操作系统操作系统，是一个在无限循环中执行的程

9、序，因，是一个在无限循环中执行的程序，因而不是一个算法。而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。该子程序得到输出结果后便终止。Algorithm+Data Structure=Program -Nikiklaus WirthAlgorithm+Data Structure=Program -Nikiklaus Wirth1.1 基本概念基本概念-问题求解问题求解(Problem Solving)理解问题

10、理解问题精确解或近似解精确解或近似解选择数据结构选择数据结构算法设计策略算法设计策略设计算法设计算法1.2 算法复杂性分析算法复杂性分析 算法复杂性算法复杂性=算法所需要的计算机资源算法所需要的计算机资源算法的时间复杂性算法的时间复杂性T(n)；算法的空间复杂性算法的空间复杂性S(n)。其中其中n是问题的规模（输入大小）。是问题的规模（输入大小）。1.2.1 算法的时间复杂性算法的时间复杂性（1）最坏情况最坏情况下的时间复杂性下的时间复杂性 Tmax(n)=max T(I)|size(I)=n（2）最好情况最好情况下的时间复杂性下的时间复杂性 Tmin(n)=min T(I)|size(I)=

11、n（3）平均情况平均情况下的时间复杂性下的时间复杂性 Tavg(n)=其中其中I是问题的规模为是问题的规模为n的实例，的实例，p(I)是实是实 例例I出现的概率。出现的概率。1.2.2.1 算法渐近复杂性算法渐近复杂性T(n),as n;(T(n)-t(n)/T(n)0，as n;t(n)是是T(n)的渐近性态，为算法的渐近复杂性。的渐近性态，为算法的渐近复杂性。在数学上，在数学上，t(n)是是T(n)的渐近表达式，是的渐近表达式，是T(n)略去低阶略去低阶项留下的主项。它比项留下的主项。它比T(n)简单。简单。1.2.2.2 渐近分析的记号渐近分析的记号在下面的讨论中，对所有在下面的讨论中，

12、对所有n，f(n)0，g(n)0。（1）渐近上界记号渐近上界记号O O(g(n)=f(n)|存在正常数存在正常数c和和n0使得对所有使得对所有n n0有：有：0 f(n)cg(n)比如：比如：3N+10=O(N),4N2+3N-1=O(N2),logN=O(N)（2）渐近下界记号渐近下界记号 (g(n)=f(n)|存在正常数存在正常数c和和n0使得对所有使得对所有n n0有：有：0 cg(n)f(n)比如：比如：3N+10=(1),4N2+3N-1=(N2),NlogN=(logN)（3）非紧上界记号非紧上界记号o o(g(n)=f(n)|对于任何正常数对于任何正常数c0，存在正数和存在正数和

13、n0 0使得对所有使得对所有n n0有：有：0 f(n)0，存在正数和存在正数和n0 0使得对所有使得对所有n n0有：有：0 cg(n)f(n)等价于等价于 f(n)/g(n)，as n。f(n)(g(n)g(n)o(f(n)比如：比如：4N2+3N-1=(N),N!=(N2)（5）紧渐近界记号紧渐近界记号 (g(n)=f(n)|存在正常数c1,c2和n0使得对所有n n0有：c1g(n)f(n)c2g(n)比如：比如：4N2+3N-1=(N2),logN2+2=(logN)定理定理1：(g(n)=O(g(n)(g(n)f(n)=(g(n)的确切意义是：f(n)(g(n)。一般情况下，等式和

14、不等式中的渐近记号(g(n)表示(g(n)中的某个函数。例如：2n2+3n+1=2n2+(n)表示 2n2+3n+1=2n2+f(n)，其中f(n)是(n)中某个函数。等式和不等式中渐近记号O,o,和的意义是类似的。渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义渐近分析中函数比较渐近分析中函数比较f(n)=O(g(n)a b;f(n)=(g(n)a b;f(n)=(g(n)a=b;f(n)=o(g(n)a b.1.2.2.3 渐近分析记号的若干性质渐近分析记号的若干性质（1）传递性：）传递性：f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=O(g

15、(n)，g(n)=O(h(n)f(n)=O(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=o(g(n)，g(n)=o(h(n)f(n)=o(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；（2）反身性：）反身性：f(n)=(f(n)；f(n)=O(f(n)；f(n)=(f(n).（3）对称性：）对称性：f(n)=(g(n)g(n)=(f(n).（4）互对称性：）互对称性：f(n)=O(g(n)g(n)=(f(n)；f(n)=o(g(n)g(n)=(f(n)；（5）算术运算：）算术运算：O(f(n)+O(g(n)=O(maxf(n)

16、,g(n)；O(f(n)+O(g(n)=O(f(n)+g(n)；O(f(n)*O(g(n)=O(f(n)*g(n)；O(cf(n)=O(f(n)；g(n)=O(f(n)O(f(n)+O(g(n)=O(f(n)。规则O(f(n)+O(g(n)=O(maxf(n),g(n)的证明：证明：对于任意f1(n)O(f(n)，存在正常数c1和自然数n1，使得对所有n n1，有f1(n)c1f(n)。类似地，对于任意g1(n)O(g(n)，存在正常数c2和自然数n2，使得对所有n n2，有g1(n)c2g(n)。令c3=maxc1,c2，n3=maxn1,n2，h(n)=maxf(n),g(n)。则对所有的

17、 n n3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)c32 maxf(n),g(n)=2c3h(n)=O(maxf(n),g(n).1.2.3 算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数（1）单调函数）单调函数单调递增：m n f(m)f(n);单调递减：m n f(m)f(n);严格单调递增：m n f(m)f(n);严格单调递减：m f(n).（2）取整函数）取整函数 x ：不大于x的最大整数；x ：不小于x的最小整数。取整函数的若干性质取整函数的若干性质 x-1 x x x 0，有：，有：n/a /b =n/ab

18、 ;n/a /b =n/ab ;a/b (a+(b-1)/b;a/b (a-(b-1)/b;f(x)=x ,g(x)=x 为为单调递增函数。单调递增函数。（3）多项式函数）多项式函数 p(n)=a0+a1n+a2n2+adnd；ad0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；多项式有界；f(n)=O(1)f(n)c;k d p(n)=O(nk);k d p(n)=(nk);k d p(n)=o(nk);k 0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman =am+n;a1 an为单调递增函数;a1 nb=o(an)ex 1+x;|

19、x|1 1+x ex 1+x+x2;ex=1+x+(x2),as x0;（5）对数函数）对数函数 log n=log2n;lg n=log10n;ln n=logen;logkn=(log n)k;log log n=log(log n);for a0,b0,c0|x|1 for x -1,for any a 0,logbn=o(na)（6）阶乘函数）阶乘函数1.2.4 算法分析中常见的复杂性函数算法分析中常见的复杂性函数小规模数据小规模数据中等规模数据中等规模数据1.3 用用c+描述算法描述算法（1）选择语句：）选择语句：（1.1)if 语句：语句：（1.2)？语句：？语句：if(expre

20、ssion)statement;else statement;exp1?exp2:exp3 y=x9?100:200;等价于：if(x9)y=100;else y=200;switch(expression)case 1:statement sequence;break;case 2:statement sequence;break;default:statement sequence;（1.3)switch语句：语句：（2）迭代语句：）迭代语句：（2.1)for 循环：循环：for(init;condition;inc)statement;（2.2)while 循环：循环：while(con

21、dition)statement;（2.3)do-while 循环：循环：do statement;while(condition);（3）跳转语句：）跳转语句：（3.1)return语句：语句：return expression;（3.2)goto语句：语句：goto label;label:（4）函数：）函数：return-type function name(para-list)body of the function int max(int x,int y)return xy?x:y;template Type max(Type x,Type y)return xy?x:y;int i

22、=max(1,2)；double x=max(1.0,2.0)；（5）模板）模板template：（6）动态存储分配）动态存储分配（6.1）运算符）运算符new 运算符new用于动态存储分配。new返回一个指向所分配空间的指针。例：int x；y=new int；y=10；也可将上述各语句作适当合并如下：int y=new int；y=10；或 int y=new int(10)；或 int y；y=new int(10)；（6.2）一维数组）一维数组 为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。例：例：fl

23、oat x=new floatn；创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。然后可用x0，x1，xn-1来访问每个数组元素。（6.3）运算符）运算符delete 当动态分配的存储空间已不再需要时应及时释放所占用的空间。用运算符delete来释放由new分配的空间。例：例：delete y；delete x；分别释放分配给y的空间和分配给一维数组x的空间。（6.4）动态二维数组）动态二维数组 创建类型为Type的动态工作数组，这个数组有rows行和cols列。template void Make2DArray(Type*&x,int ro

24、ws,int cols)x=new Type*rows;for(int i=0;irows;i+)xi=new Typecols;当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。释放空间后将x置为0，以防继续访问已被释放的空间。template void Delete2DArray(Type*&x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0;1.4 算法分析方法算法分析方法例：顺序搜索算法例：顺序搜索算法templateint seqSear

25、ch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;（1）Tmax(n)=max T(I)|size(I)=n=O(n)（2）Tmin(n)=min T(I)|size(I)=n=O(1)（3）在平均情况下，假设：(a)搜索成功的概率为p(0 p 1)；(b)在数组的每个位置i(0 i n)搜索成功的概率相同，均为 p/n。1.4 算法分析的基本法则算法分析的基本法则非递归算法：非递归算法：（1）for/while 循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句

26、计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。templatevoid insertion_sort(Type*a,int n)Type key;/cost times for(int i=1;i=0&ajkey)/c4 sum of ti aj+1=aj;/c5 sum of(ti-1)j-;/c6 sum of(ti-1)aj+1=key;/c7 n-1 在最好情况下，ti=1,for 1 i n;在最坏情况下，ti i+1,for 1 i n;对于输入数据ai=n-i(逆序),i=0,1,n-1，算法insertion_sort 达到其最坏情形。因

27、此，由此可见，Tmax(n)=(n2)最优算法最优算法问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。堆排序算法是最优算法。递归算法复杂性分析递归算法复杂性分析 int factorial(int n)if(n=0)return 1;return n*factorial(n-1);递归的蒙娜丽莎递归的蒙娜丽莎1.5.1P类与NP类问题n易处理的问题:可由多项式时间算法多项式时间算法求解的问题 难处理的问题:需要超多项式时间超多项式时间才能求解的问题 不可解问题：任

28、何计算机无论耗费多少时间也不能解决不能解决的问题 例如：“图灵停机问题图灵停机问题”“Keyboard not found.press F1 to continue”n有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。在图灵机计算模型下，这类问题的计算复杂性至今未知。1.5 NP完全性理论完全性理论图灵机图灵机1.5 NP完全性理论完全性理论图灵机M的时间复杂性时间复杂性T(n)是它处理所有长度为是它处理所有长度为n的的输入所需的最大计算步数输入所需的最大计算步数。如果对某个长度为n的输

29、入，图灵机不停机，T(n)对这个n值无定义。图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)存在一些不可解问题不可解问题：图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)图灵机停机问题的不可判定性:能否给出一个判断任意一个图灵机是否停机的一般方法?答案是NO.这个问题实际上是问:是否存在一台万能的图灵机 H,把任意一台图灵机 M 输入给 H,它都能判定 M 最终是否停机,输出一个明确的 yes 或 no 的答案?可以利用反证法来证明这样的H不可能存在.假定存在一个能够判定任意

30、一台图灵机是否停机的万能图灵机H(M),如果M最终停机,H输出 halt;如果M不停机,H输出 loop.我们把H当作子程序,构造如下程序P:function P(M)if(H(M)=loop)return halt;else if(H(M)=halt)while(true);/loop forever 因为 P本身也是一台图灵机,所以我们可以把 P 输入给它自己,然后问 P(P)是否停机.按照程序P的流程,如果P不停机无限循环,那么它就停机,输出halt;如果P停机,那么它就无限循环,不停机;这样无论如何我们都将得到一个矛盾,所以假设前提不成立,即不存在这样的H.或者说,图灵机停机问题是不可

31、判定图灵机停机问题是不可判定的(undecidable).图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)另外还有两个本质上相似的悖论：理发师悖论理发师悖论：村子里有个理发师，这个理发师有条原则是，对于村里所有人，当且仅当这个人不自己理发，理发师就给这个人理发。如果这个人自己理发，理发师就不给这个人理发。无法回答的问题是，理发师给自己理发么？停机测试悖论停机测试悖论：计算机里有个测试程序，这个测试程序的原则是，对于计算机里所有程序，当且仅当这个程序不递归调用自己(输出停机)，测试程序就调用它(对应不停机)。如果这个程序递归调用自己（对

32、应不停机），测试程序就不调用它（对应停机）。无法回答的问题是，测试程序递归调用自己么？图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)1.5.1P类与NP类问题n 非确定性问题：有些问题的答案无法直接计算得到，只能通过间接的“猜算”来得到结果。n 而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验

33、算的话，就叫完全多项式非确定问题完全多项式非确定问题。旅行售货员问题旅行售货员问题（Traveling Salesman Problem）n最优化形式的最优化形式的TSP问题问题：n判定形式的判定形式的TSP问题问题：对于给定的带权图G=(V,E)的一个正数d，要求判定图G中是否存在总费用不超过d的周游路线。101234302065410设G=(V,E)是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。TSP要求在图G中找出费用最小的周游路线。较难较难较易较易n P类问题类问题：可以在多项式时间内求解的判定问题。确定性计算模型下的易解问题类。确定性计

34、算模型下的易解问题类。n 非确定性算法非确定性算法：将问题求解分为猜测和验证两个阶段。猜测：给出问题的一个猜测非确定性验证：验证猜测阶段给出解的正确性确定性n NP类问题类问题：非确定性多项式时间可解非确定性多项式时间可解的判定问题。非确定性计算模型下的易验证问题类。非确定性计算模型下的易验证问题类。n 非确定性图灵机计算模型非确定性图灵机计算模型NDTM(Nondeterministic Turing Machine)：在NDTM模型下，许多问题可以在多项式时间内求解NP问题(Nondeterministic Polynomial)1.5.1 P类与类与NP类问题类问题PNPNPCNP-Ha

35、rd关系nP：可以在多项式时间解决的问题nNP：目前没有多项式时间解决的算法，但是如果给出一个候选答案，可以在多项式时间里验证这个答案是不是正确的。nNPC：满足两个性质：1.可在多项式时间验证候选答案（是NP问题）；2.任何一个NP问题可在多项式时间内规约到该问题。nNP-Hard：任何一个NP问题可在多项式时间内规约到该问题，但无法证明问题本身是无法证明问题本身是NP问题问题。NP-Hard至少和NP问题一样难。1.5.2NP完全问题（完全问题（NPC）nPNP。n直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。n大多数的计算机科学家认为N

36、P类中包含了不属于P类的语言，即PNP。nNP完全问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。n目前还没有一个NP完全问题有多项式时间算法。逻辑电路问题-给定一个逻辑电路，问是否存在一种输入使输出为True。一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和导线组成。1.5.3 一些典型的NP完全问题存在输出不可能为True的逻辑电路：1.5.3 一些典型的NP完全问题逻辑电路问题显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明

37、过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。1.5.3 一些典型的NP完全问题 定理定理8-7(Cook8-7(Cook定理定理)：布尔表达式的可满足性问题SAT是NP完全的。-第一个第一个NPCNPC问题问题证明：SAT的一个实例是k个布尔变量 ，的m个布尔表达式 ，若存在各布尔变量 (1ik)的0，1赋值，使每个布尔表达式 (1im)都取值1，则称布尔表达式 是可满足可满足的。SATNP是很明显的。对于任给的布尔变

38、量 ，的0，1赋值，容易在多项式时间内验证相应的 的取值是否为1。因此，SATNP。现在只要证明对任意的LNP有LpSAT即可（略）1.5.3一些典型的NP完全问题1.5.3 一些典型的NP完全问题部分NP完全问题树布尔表达式的可满足问题布尔表达式的可满足问题合取范式的可满足问题合取范式的可满足问题三元合取范式的可满足问题三元合取范式的可满足问题哈密顿回路问题哈密顿回路问题旅行售货商问题旅行售货商问题团问题团问题顶点覆盖问题顶点覆盖问题子集和问题子集和问题64（1）合取范式的可满足性问题（合取范式的可满足性问题（CNF-SATCNF-SAT）问题描述：问题描述：给定一个合取范式，判定它是否可满

39、足。如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如：就是一个合取范式，而 就不是合取范式。（2）3元合取范式的可满足性问题（元合取范式的可满足性问题（3-SAT）问题描述：问题描述：给定一个3元合取范式，判定它是否可满足。1.5.3 一些典型的NP完全问题65（3）团问题（团问题（CLIQUECLIQUE）问题描述问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，VV，|V|=k，且对任意u，wV有(u，w)E。（4）顶点覆盖问题（顶点覆盖问题（VERTE

40、X-COVERVERTEX-COVER）问题描述：问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在VV，|V|=k，使得对于任意(u，v)E有uV或vV。如果存在这样的V，就称V为图G的一个大小为k顶点覆盖。1.5.3 一些典型的NP完全问题 66（5）子集和问题（子集和问题（SUBSET-SUMSUBSET-SUM）问题描述问题描述：给定整数集合S和一个整数t，判定是否存在S的一个子集SS，使得S中整数的和为t。例如，若S=1，4，16，64，256，1040，1041，1093，1284，1344且t=3754，则子集S=1，16，64，256，1040，1093，128

41、4是一个解。（6）哈密顿回路问题（哈密顿回路问题（HAM-CYCLE）问题描述：问题描述：给定无向图G=(V，E)，判定其是否含有一哈密顿回路。1.5.3 一些典型的NP完全问题（7）旅行售货员问题（旅行售货员问题（TSP）问题描述：问题描述：给定一个无向完全图G=(V，E)及定义在VV上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k。迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。(1)只对问题的特殊实例特殊实例求解(2)用动态规划法动态规划法或分支限界法分支限界法求解(3)用概率算法概率算法求

42、解(4)只求近似解近似解(5)用启发式方法启发式方法求解 1.5.4 NP完全问题的近似算法A joke:nThe boss wants to produce programs to solve the following two problemsn Euler circuit problem:n given a graph G,find a way to go through each edge exactly once.nHamilton circuit problem:n given a graph G,find a way to go through each vertex exact

43、ly once.nThe two problems seem to be very similar.nPerson A takes the first problem and person B takes the second.nOutcome:Person A quickly completes the program,whereas person B works 24 hours per day and is fired after a few months.Euler Circuit and Hamilton Circuit A joke(continued):nWhy?nobody i

44、n the company has taken this course.nExplanation:nEuler circuit problem can be easily solved in polynomial time.nHamilton circuit problem is proved to be NP-hard.nSo far,nobody in the world can give a polynomial time algorithm for a NP-hard problem.nConjecture:there does not exist polynomial time algorithm for this problem.此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢