资源描述：
《第7章 算法设计.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章NP完全性理论问题回顾目前所讨论过的多个算法,例如最短路径问题、0-1背包问题、合并排序和最小生成树等算法都是高效或称有效的(能在多项式时间内解决).在所有这些问题中我们的目标都是从一个指数大小的解空间中搜索问题的一个可行解（解空间的子集）(路径和树.).一个有n个节点的图，有nn-2生成树一个图中从节点s到节点t有指数条路径以上这些问题都可通过对候选解进行一一的确认在指数时间内进行求解是否所有的问题都能在多项式时间内解决？有些问题不论耗费多少时间也不能解决。还有些问题是可以解决的，但对任意常数k，他们都不能在O(nk)时间内得到答案多项式时
2、间：简单P超多项式时间：难NPNp完全问题和p问题相似性最短简单路径O(n2)->P,最长简单路径->np欧拉游程->p,哈密尔顿回路->np2-CNF可满足性与3-CNF可满足性可满足性称一个布尔公式为k和取范式或k-CNF，如果他是用AND连接若干个OR子句，且每个子句中恰有k个布尔变量或其否定形式。(x┐y)(┐z┐x)(┐xz)是若干个2项变量的子句(xy)的联合每个子句仅包含OR操作符子句中仅包含变量或变量的否定形式，如x或┐x对一个布尔CNF公式来说，如果存在着对其变量的某种0和1赋值，使得它的结果值为1的话，则称该布尔CNF公
3、式是可满足的。可满足性是实际生活中一个重要的问题，其应用范围覆盖芯片测试、计算机设计，甚至图形分析和软件工程如何证明和取布尔式的可满足性？可满足性可满足性问题是一个搜索问题.可以通过对每个变量进行一一赋值的方式搜索所有解.如上式的一个可满足赋值x=1,y=0,z=1.对于2-CNF存在着一个多项式时间的算法来确定可满足性但是要确定一个3-CNF公式是否是可满足的这一个问题是NP完全的三类问题P类问题NP类问题NPC类问题（NP完全性问题）非形式化的定义P：类问题包含的是在多项式时间内可解的问题。NP：在多项式时间内”可验证”的问题，此处是指能在多项
4、式时间能求得该问题某一特定解对应的一特定变量值。如2-CNF可满足问题中对变量的一组赋值，我们可以很容易地在多项式时间内，检查这一赋值是否满足布尔表达式NPC：如果一个问题属于NP，且与NP中的任何问题是一样”难的”，则属于NPC类PVsNPP=NP?[Cook1971,Edmonds,Levin,Yablonski,Gödel]问题就在这个问号上，到底是NP等于P，还是NP不等于P。NPP证明其中之一，便可以拿百万美元大奖这个奖还没有人拿到，也就是说，NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。NP里面的N，不
5、是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是对的。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。NP完全问题是世界7大数学难题之一百度百科“千僖难题”之一：P(多项式算法)问题对NP(非多项式算法)问题“千僖难题”之二：霍奇(Hodge)猜想“千僖难题”之三：庞加莱(Poincare)猜想千僖难题”之四：黎曼(Riemann)假设“千僖难题”之五：杨－米尔斯(Yang-Mills)存在性和质量缺口“千僖难题”之六：纳维叶－斯托克斯
6、(Navier-Stokes)方程的存在性与光滑性“千僖难题”之七：贝赫(Birch)和斯维讷通－戴尔(Swinnerton-Dyer)猜想NP完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。优秀的算法设计者在项目起初可行性分析阶段如果能够确定一个NP完全问题，就可以提供充分的理论依据说明其难处理性和可行性的问题。作为一名工程师，如知道要解决的工程存在NP完全问题，更好的做法是花时间开发一种近似算法，或解决某种易处理的问题特例，而不是寻找求得问题确切解的一种快速算法。P类问题抽象问题首先必须对“问题”这一概念进行形式化定义。抽象问题Q为
7、在问题实例集合I和问题解法集合S上的一个二元关系例如最短单元路径问题实例：一个图G和两个顶点u,v解：图中顶点序列抽象判定问题最优化问题与判定问题（decisionproblem）最优化问题：求解问题最优的解值判定问题：判断问题的解是“是”或”否“，即解仅为”是”或否,或0或1的问题）NP完全性理论主要讨论判定问题。抽象的判定问题：从实例集I映射到解集{0,1}上的一个函数最优化问题to判定问题最优化问题可以转换为一个不困难的判定问题。例如：最短单元路径问题,是最优化问题。路径问题（判定问题）：设,判定给定有向图G和
8、顶点u,v一个整数k，在u,v之间是否存在一条包含至多k条边的路径。编码如果要用一个计算机程序来求解抽象问题，就必须用一种
