np完全问题纯理论.ppt

第十二章 NP完全问题
1
.
什么是好算法？
算法的种类和数量积累到一定程度时，需要对算法进行比较和分类。
什么是好算法？Edmonds，1975年提出了一个被沿用至今的标准。
2
.
Edmonds算法标准
Edmonds算法标准指出具有多项式时间的算法为好
算法。
多项式时间算法：如果П是任意一个问题，对П存
在着一个算法，它的时间复杂性为O(nk),其中n为输
入规模，k为非负整数，就认为存在着一个解问题П
的多项式时间算法。
3
.
以多项式作为分界函数？
原因有两个：
一、常见算法大致分为两类：
一类是多项式时间内可实现的
另一类需要指数时间（O(cn))
多项式时间算法的可实现性远大于指数时间算法。
（参见P8，)
4
.
以多项式作为分界函数？
二、多项式时间算法与计算模型无关
算法的研究依赖于计算模型。在不同类型计算模型上实现算法，计算时间不同。
广义Church—Turing命题：不同计算模型上的计算时间有多项式关系。
多项式与多项式的复合函数是多项式，因此，多项式时间算法与计算模型无关。
5
.
P类问题—易解的问题
是否每个问题都有多项式时间算法？
在考虑问题的计算复杂性时，常把它化为相应的判定
问题考虑。
首先看问题分类及其转换。
6
.
问题分类
一类是判定问题
解只有两种，yes或no。
例：给定图G=(V,E)， 问该图是否有哈密尔顿圈。
一类是优化问题
例：给定图G=(V,E)，假设边的费用为自然数。求该
图的最短哈密尔顿回路。
7
.
问题转换
优化问题可转换为相应的判定问题求解。

例：给定图G=(V,E)，假设边的费用为自然数。给
定k=1,2,..，问是否有长度不超过k的哈密尔
顿回路。
8
.
P类问题
P类：
具有多项式时间算法的判定问题形成一个
计算复杂类，记为P类。

P类—易解的问题
P-Polynomial
思考：已学知识中哪些问题属P类问题？
9
.
NP类问题—难解的问题
具有指数时间算法的问题。
例：货郎担问题(TSP问题)。

n!排列方式。
n=6: 6! = 720
n=19: 19! ≈ *1017
每秒排一次，*109年
每秒排百万次，排3000年
有算法但实现性差。
10
.