Chapter-9 NP完全问题专用课件.pptVIP

南京理工大学 9.5 NPI类问题 NP类问题中还有一些问题，人们不知道是属于P类还是属于NP完全问题，还有待于证明其归属。 这些问题是NP完全问题的可能性非常小，也因为不相信他们在P中，我们人为地增加另一问题类来接纳这类问题，这个类称为NPI(NP-Intermediate)类。 NP完全问题 NP类问题 P类问题 ? ? 南京理工大学 关于NPI类问题的评述 NPI类是一个人为定义的、动态的概念，随着人们对问题研究的深入，许多NPI类问题逐渐被明白无误地证明他们原本属于P类问题或NP完全问题。 例如：线性规划问题、素数判定问题等，在二者没有被证明他们均属于P类问题之前，人们一直将他们归于NPI类问题。 南京理工大学 一个例子 线性规划问题 设A∈Rm×n, x∈Rn, b∈Rm， 在满足Ax=b，x≥0约束下， 使目标函数cTx达到最大值，其中c∈Rn. 长期以来，线性规划问题没有多项式时间解法，也无法证明它是NP完全问题。直到20世纪80年代，这个问题得到解决，发现了多项式时间算法。 NP完全问题 线性规划问题 P类问题 ? ? 南京理工大学 另一个例子 素数判定问题 给一个整数，判定其是素数 还是合数。 经过一个重要的理论突破，印度M. Agrawal 教授和他的学生N. Kayal 和N. Saxena于2002年宣布发现一个多项式时间算法。(PRIMES is in P, Annals of Mathematics, 160 (2004), 781–793) NP完全问题 素数判定问题 P类问题 ? ? 南京理工大学 9.6 P、NP、co-NP、NPI类之间的区别与联系 南京理工大学 NP完全问题是计算机难以处理的，但是实际中经常遇 到，我们无法回避这些问题。因此，人们提出了解决NP完全问题的各种方法： 采用先进的算法设计技术 问题规模不是很大时，采用动态规划法、回溯法、分枝限界法等。 近似算法 很多问题的解允许有一定的误差，只要给出的解是合理的、可接受的。 9.7 NP完全问题的计算机处理技术简介 南京理工大学 NP完全问题的计算机处理技术简介 随机算法 例如随机采样算法，穷举+挑一 vs. 随机化采样，?(n) 或以较小的错误概率为代价，获得计算时间的大幅减少。 并行计算 利用多台CPU共同完成一项计算，虽然从原理上说，增强计算性能并不能从根本上解决NP完全问题，但这也是解决NP完全问题的措施之一。近年来的成就如129位(bit)大整数的分解、“深蓝”下棋程序等。 南京理工大学 NP完全问题的计算机处理技术简介 智能算法 遗传算法 人工神经网络 模拟退火算法 禁忌有哪些信誉好的足球投注网站算法 DNA计算 人工免疫算法 蚁群算法 （蚁群算法小游戏） /complex/temp/ant/ant.htm Swarm Intelligence: a new journal dedicated to reporting on developments in the discipline of swarm intelligence. Published by Springer. Editor-in-Chief: Marco Dorigo. 南京理工大学 祝你成功！ 南京理工大学 南京理工大学 9 NP完全问题NP Complete Problem 南京理工大学 本章内容提要 易解问题与难解问题 P类问题和NP类问题 NP完全问题 co-NP类问题 NPI类问题 P、NP、co-NP、NPI类之间的区别与联系 NP完全问题的计算机处理技术简介 形而上者谓之道， 形而形而下者谓之器 --《易经·系辞 》 南京理工大学 9.1 引言 9.1.1 易解问题与难解问题 如果对一个问题∏存在一个算法，时间复杂性为O(nk)，其中n是问题规模，k是一个非负整数，则称问题∏存在多项式时间算法。这类算法在可以接受的时间内实现问题求解， e.g., 排序、串匹配、矩阵相乘。 现实世界里还存在很多问题至今没有找到多项式时间算法，计算时间是指数和超指数函数（如2n和n!），随着问题规模的增长而快速增长。 通常将前者看作是易解问题，后者看作难解问题。 南京理工大学 9.1.2 易解问题与难解问题的主要区别 在学术界已达成这样的共识：把多项式时间复杂性作为易解问题与难解问题的分界线，主要原因有： 1) 多项式函数与指数函数的增长率有本质差别 问题规模n 多项式函数 指数函数 logn n nlogn n2 n3 2n n! 1 0 1 0.0 1 1 2 1 10 3.3 10 33.2 100 1000 1024 3628800 20