算法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完全问题》请在金锄头文库上搜索。
最新房屋买卖合同格式
三年级语文上册小摄影师教材分析人教新课标版教案
沈阳市母婴安全保障项目商业计划书(范文参考)
采购部年终总结(3篇).doc
纳税计划案例精讲和分析(全套)李占英85全套精讲完整视频
北京理工大学21秋《企业文化》复习考核试题库答案参考套卷12
新课标2015年高一历史暑假作业1《历史》必修二经济史
佣金协议模板
大班语言教案《新奇的衣服》
JAVA套接字编程分析
期货委托协议
中国医科大学21秋《卫生信息管理学》在线作业三答案参考66
实用的工作方案模板集锦六篇
深基坑支护质量监理细则通用
九年级地理复习课教案doc日本东南亚
股份公司成立合作协议书
幼儿园教师个人工作总结范文2023(3篇).doc
有关班主任促进差生转化的方法初探
完成白音库伦插入3#道岔施工方案
员工购房借款合同
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页