算法10_NP完全问题
33页1、算法设计与分析,张怡婷Email:,第10章 NP完全问题,学习要点:确定算法和不确定算法判定问题和最优化问题的关系可满足性问题P类问题和NP类问题NP难度(NP hard)和NP完全(NP complete)问题Cook定理典型的NP完全(或NP难度)问题的证明,章节内容:10.1 基本概念10.2.1 Cook定理10.3 一些典型的NP完全问题,10.1 基本概念,将能在多项式时间内求解的问题视为易处理问题(tractable problem)。至今尚未找到多项式时间算法求解的问题视为难处理问题(intractable problem)。NP完全问题或NP难度(NP hard)问题如:指数时间算法无论消耗多少计算机时间和空间也不能求解的称为不可判定(undecidable)的。不存在任何算法求解,如果任意一个NP难度问题存在一个多项式时间算法,那么所有NP完全问题都可以在多项式时间内求解。一个NP完全问题可以在多项式时间内求解,当且仅当所有其他的NP完全问题都可以在多项式时间内求解。,10.1.1 不确定算法和不确定机,不确定算法的抽象计算模型:算法在抽象机上运行与计算机系统的性
2、能无关;算法的执行表现为执行一个基本运算序列;基本运算的执行时间是有限常量;,Choice(S):任意选择集合S的一个元素。Failure():发出不成功完成信号后算法终止。Success():发出成功完成信号后算法终止。,例10-1 在n个元素的数组a中查找给定元素x,如果x在其中,则确定使aj=x的下标j,否则输出-1。,不确定搜索算法:void Search(int a,T x) int j=Choice(0,n-1);/从0,1,.,n-1中任意选取一个值 if(aj=x) coutj;Success();/不确定算法成功终止 cout-1; Failure();/不确定算法失败终止,若算法执行中需作出一系列的Choice函数选择,当且仅当Choice的任何一组选择都不会导致成功信号时,算法在O(1)时间不成功终止。,如果一个判定问题实例的解为真,Choice函数每一次总能在O(1)时间内做出导致成功的正确选择。,包含不确定选择语句,并能按上述方式执行一个算法的机器称为不确定机(non deterministic machine)。,在不确定机上执行的算法称为不确定算法(non
3、 deterministic algorithm)。,不确定机的执行方式,可理解为不受限制的并行计算:不确定机执行不确定算法时,每当Choice函数进行选择时,就好像复制了多个程序副本,每一种可能的选择产生一个副本,所有副本同时执行。一旦一个副本成功完成,将立即终止所有其他副本的计算。如果存在至少一种成功完成的选择,一台不确定机总能做出最佳选择,以最短的程序步数完成计算,并成功终止。不确定机能及时判断算法的某次执行不存在任何导致成功完成的选择,并使算法在一个单位时间内输出“不成功”信息后终止。,显然,这种机器是虚构的,是一种概念性计算模型!,不确定搜索算法:void Search(int a,T x) int j=Choice(0,n-1); if(aj=x) coutj;Success(); cout-1; Failure();,定义10-1 (不确定算法时间复杂度)一个不确定算法所需的时间是指对任意一个输入,当存在一个选择序列导致成功完成时,达到成功完成所需的最少程序步。在不可能成功完成的情况下,所需时间总是O(1)。,例10-2 将n个元素的序列排成有序序列。,不确定排序算法:v
4、oid NSort(int a,int n) int bmSize,i,j; for (i=0;ibi+1) Failure();/若存在两元素逆序,则失败 Success();/Choice函数的n次正确选择,算法成功,判定问题和最优化问题,一个只要求产生“0”或“1”作为输出的问题称为判定问题(decision problem)。,许多最优化问题都可以得到与其相对应的判定问题,且两者往往存在计算上的相关性:,一个判定问题能够在多项式时间内求解,当且仅当它相应的最优化问题可以在多项式时间内求解。,如果判定问题不能在多项式时间内求解,那么它相应的最优化问题也不能在多项式时间内求解。,例10-3 最大集团及其判定问题无向图G=(V,E)的一个完全子图称为该图的一个集团,集团的规模用集团的顶点数衡量。,最大集团问题:确定图G的最大集团规模的问题。,最大集团判定问题:判定图G是否存在一个规模至少为k的集团。(k为给定正整数),若最大集团问题能在多项式时间O(g(n)内求解。当且仅当对应的判定问题能在多项式时间O(f(n)内求解。,一方面:只需以k=1,2,.,n,最多n次调用最大集团判定算法
《算法10_NP完全问题》由会员壹****1分享,可在线阅读,更多相关《算法10_NP完全问题》请在金锄头文库上搜索。
部分的讲函数的等高线
冶金专业顶岗实习报告
提升教师专业成长的途径
小学语文教学设计-水上飞机
容积和容积单位练习课导学案
珍惜水资源主题演讲稿范文450字左右
公司岗位分析调查问卷
北京航空航天大学21秋《组织行为学》平时作业二参考答案4
人力资源市场从业人员职业资格考试
疟疾防治知识
通化导热散热技术创新项目可行性研究报告模板范文
我国纺织品行业发展现状
南京关于成立IGBT公司可行性报告模板参考
乘客信息管理系统公司风险管理制度
12定额计算规则
超棒瘦身食谱 7天狂减6斤docx
保养维修服务合同
公司规划发展部工作思路.doc
2022年小学生的自我介绍作文600字四篇
比较全的一套智能家居设计方案
2021-12-31 51页
2021-12-30 11页
2021-12-30 12页
2021-12-30 12页
2021-12-30 14页
2021-12-30 12页
2021-12-30 29页
2021-12-30 11页
2021-12-30 16页
2021-12-19 32页