第七章 算法、复杂性与np-完全性理论

《第七章 算法、复杂性与np-完全性理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章算法、复杂性与NP－完全理论算法、复杂性与NP－完全理论NP－完全性的理论基础是cook在20世纪70年代初建立的，它具有十分重要的理论意义和实用价值，这项工作主要有三点：首先他定义了多项式变换(或归结)。一个问题A能多项地归结为另一个问题B，那么当B有多项式算法时，则A就有多项式算法，这儿应用了多项式运算的封闭性，而归结的方法是数学家们常用的方法。即把一个未解决的问题，千方百计地转换为一个已解决的问题，从而未解决的问题得到解决，这儿cook提出了多项式归结，却有非寻常的意义。其次他定义了判定问题的NP类。这一类问题非常广泛，几乎包含了所有有意义问题，最后，他证明了“Sat

2、isfiability”问题是NP－完全的。即把答案为是的判定问题，其验证过程在非确定性图灵机上实现，而这个验证过程可以用布尔函数描述，众所周知，任一布尔表示式可以转换为合取范式．由于有了第一个NP－完全问题“Satisfiability”。从而引出了一大类NP－完全问题，由此导出了重要结论：如果有一个NP－完全问题有多项式时间算法，则所有的NP问题都有多项式时间算法。关于问题分类和多项式时间算法的讨论，在cook的这篇文章向进之前也有一些零散的讨论。比如Edminds，J．(1965)曾提出过好算法“goodalgorithm”的概念，实际他是指多项式时间的算法；同时他还还指出

3、货郎问题不太可能有好算法，这实际上把问题分为两类。本章将重点介绍NP理论的概念和NP－完全问题证明技术。同时，还介绍了对算法好坏的一些评价标准，以及对NP－难问题的研究思路与方法。本章所涉及的内容是算法研究的基础理论，也是必备的内容，对于数学基础不足的读者可以略去有关NP－完全问题证明一节。7．1问题、算法与复杂性上述几章我们讨论了若干问题及其算法，如线性规划问题，以及求解线性规划问题的单纯形算法和楕球算法等；网络中的最短路问题，以及求解最短路问题的Dijkstra，算法和Floyd算法等；网络中最大流问题及其求最大流问题的若干个算法，以及动态规划方法和割平面法等，现在我们对问题

4、和算法给出明确的定义：一个问题是指需要通过数学计算来回答的提问，通常它包含若干个未知的参数，它所要求的答案有具体的规定和说明。比如货郎问题；它的未知参数是n个城市中每对城市i和j之间的距离dij，或者说一个n×n阶的距离矩阵[dij]；它所要求的答案是n个城市1，2，…，n−1n一个圆排列(π(1)，π(2)，…，π(n))，使∑d+d最小，又比如排序(sorting)π(i)π(i+1)π(n),π(1)i=1问题：给定n个整数a1，a2，…，an，将它们由小到大排列起来．这个问题的参数为ai，i＝1，2，…，n．要求的答案就是把这n个数排成一排，使这个排列是非降的。又如线性规

5、划问题：TmaxxCXAX=bX≥0其中A为m×n的有理数矩阵，C和b分别为n和m维有理数列向量，它们均是未知的，T要求的答案为满足约束条件且使CX最大的n维列向量X．一个问题，如果它的部分未知参数的取值范围加以限制，那么它就称为这个问题的子问题。例如在货郎问题中，如果城市之间的距离满足距离三角不等式，即任意三个城市i，j，k，有di，j＋dj，k≥di，k，那么此时称它为满足距离三角不等式的货郎问题，它是货郎问题的子问题，又如运输问题、最小费用流问题都是线性规划问题的子问题，而最短路问题又是最183小费用流问题的子问题。一个问题，如果它的所有参数的值给定后，则它就变为该问题的一

6、个实例。因此，一个问题就是由它的无穷多个实例组成，比如货郎问题，图7．1．1所示的图就是它的一个实例图7．1．1一个实例的规模(或大小)是指把该实例的数据翻译为计算机所能接受的符号串的长度，如图7．1．1中的图，称之为货郎问题的一个实例，如果我们用符号集{C，I，7，1，0，1}中的符号来描述该实例，那么可以写为：“C[1]C[10]C[11]C[100]

7、

8、10

9、11

10、100

11、

12、101

13、10

14、

15、110”其规模为44，即符号串的长度为44，这里的数字用2进制表示C[10]表示城市2，头两个∥之间一节表示城市C[1]与城市C[10]，C[11]和C[100]之间的距离．下一节表示城

16、市C[10]到城市C[11]和C[100]的距离．最后一节表示城市C[11]到城市C[100]的距离。一些个正整数n的规模为[log2，n]，它表示大于等于log2n的最小整数，线性规划：TmaxCXAX＝bX≥0的规模为mnmnL=m⋅n+∑∑∑log(1+

17、aij

18、)+log(1+

19、bi

20、)+∑log(1+

21、Cj

22、)i==11j=1ij=1+m+n其中A＝(aij)为m×n阶的有理数矩阵，b和C分别为m维和n维的有理向量。一个图G＝(V，E)通常可用它的∣V∣∣×V∣阶的邻接