第五讲：易解问题与难解问题

1、 本章首先介绍一个对问题进行抽象的典型实例哥尼斯堡七桥问题。然后，通过“梵天塔”问题和“停机问题”分别介绍学科中的可计算问题和不可计算问题。从“梵天塔”问题再引出算法复杂性中的难解性问题、P类问题和NP类问题，证比求易算法，PNP是否成立的问题。1 哥尼斯堡七桥问题17世纪的东普鲁士有一座哥尼斯堡城，城中有一座奈佛夫岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来。通过这7座桥到各城区游玩，问题：寻找走遍这7座桥的路径，要求过每座桥只许走一次，最后又回到原出发点。问题的抽象1736年，大数学家列昂纳德欧拉（L.Euler）发表了

2、关于“哥尼斯堡七桥问题”的论文。他抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题了。 D C B A 欧拉回路欧拉给出了哥尼斯堡七桥问题 的证明，还用数学方法给出了三条判定规则(判定每座桥恰好走过一次,不一定回到原点, 即对欧拉路径的判定)：如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。根据第3点,可以得出,任一连通图存在欧拉回路的充分必要条件是所有

3、顶点均有偶数度.哈密尔顿回路问题问题：在某个图G中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点，最后又回到原出发点。“哈密尔顿回路问题”与“欧拉回路问题”的不同点“哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。图论的形成和发展欧拉的论文为图论的形成奠定了基础。图论已广泛地应用于计算学科运筹学信息论控制论等学科图论已成为我们对现实问题进行抽象的一个强有力的数学工具。图论在计算学科中的作用越来越大，图论本身也得到了充分的发展。2 可计算问

4、题与不可计算问题 计算学科的问题，无非就是计算问题，从大的方面来说，分可计算问题与不可计算问题。可计算问题是存在算法可解的问题，不可计算问题是不存在算法可解的问题。 为便于理解，下面，分别以梵天塔（Hanoi，又译为汉诺）问题和停机问题来介绍可计算问题与不可计算问题。2.1排序问题随机给出n个数，要求对它们进行排序。比如：8，2，7，6，4，12对于排序问题，有多种算法。一种选择排序算法是：从n个数中挑出最小的数，再从n-1个数中挑出第二小的数.那么，在这些众多的算法中，如何来比较谁的速度更快？事后分析：机器的运行时间？事前分析：与问题规模有关的表达式，表示算法中基本操作的执行次数。一种选择排

5、序算法是：从n个数中挑出最小的数，再从n-1个数中挑出第二小的数.时间复杂性与n有关，大概是n+(n-1)+1=1/2(n(n+1)，忽略常数项，取最大的指数，记为O(n2)。最快的算法是快速排序算法，时间复杂度为O(nlogn)。2.2 梵天塔问题相传印度教的天神梵天在创造地球这一世界时，建了一座神庙，神庙里竖有三根宝石柱子，柱子由一个铜座支撑。梵天将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔（如图2.3所示），即所谓的梵天塔（又称汉诺塔）。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下3条规则

6、：每次只能移动一个盘子；盘子只能在三根柱子上来回移动，不能放在他处；在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。12递归算法(重点掌握）递归是一种特别有用的工具,不仅在数学中广泛应用,在日常生活中也常常遇到。以下使用递归算法来解决梵塔问题。13递归算法在数学中几个熟知的数学定义：在数学中几个熟知的数学定义：1)!1(01!) 1 (nnnnn(2) (2) 若若t1,t2t1,t2是树，则是树，则 也是树也是树1101) 3(111nCCnmnCnmnmnm14递归递归算法包括递归算法包括递推递推和和回归回归两部分：两部分：递推递推就是为了得到问题的解就是为了得到问题的解,将

7、它推到比原问题更简单的问题求解。将它推到比原问题更简单的问题求解。例如：例如：n!=f(n),为了计算为了计算f(n),将它推到比原问题更简单的问题将它推到比原问题更简单的问题f(n-1),即即f(n)=f(n-1)*n,而计算而计算f(n-1)比计算比计算f(n)简单简单,因为因为f(n-1)比比f(n)更加接更加接近已知解近已知解0!=1使用递推要注意使用递推要注意（1）递推应有终止之时）递推应有终止之时,例如当例如当n=0时时,0!=1为递推终止条件为递推终止条件,所谓终止所谓终止条件就是指在此条件下问题的解时明确的条件就是指在此条件下问题的解时明确的,缺少终止条件会使算法失缺少终止条件

8、会使算法失败。败。（2）简单问题表示离递推终止条件更接近的问题。简单的问题与原）简单问题表示离递推终止条件更接近的问题。简单的问题与原问题其解的算法是一致的问题其解的算法是一致的,其差别主要反映在参数上其差别主要反映在参数上,例如例如,f(n-1)比计比计算算f(n)更简单更简单,因为因为f(n-1)比比f(n)参数少参数少1。参数变化使问题递推到有明。参数变化使问题递推到有明确解。确解。15递归算法回归回归指当简单问题得到解后指当简单问题得到解后,回归到原问题的解上来。例如回归到原问题的解上来。例如,当计算完当计算完(n-1)!后后,回归计算回归计算n*(n-1)!,即得到即得到n!的值。的

9、值。使用回归要注意使用回归要注意（1）当回归到原问题的解时）当回归到原问题的解时,算法中所涉及的处理对象算法中所涉及的处理对象是关于当前问题的是关于当前问题的,即递归算法所涉及的参数与局部处即递归算法所涉及的参数与局部处理对象是有层次的。当解一问题的时候理对象是有层次的。当解一问题的时候,有它的一套参有它的一套参数与局部处理对象。当递推进入一个数与局部处理对象。当递推进入一个简单问题简单问题的时候。的时候。这套参数与局部对象便隐藏起来这套参数与局部对象便隐藏起来,在解简单问题的时候在解简单问题的时候又有它自己的一套。当回归时又有它自己的一套。当回归时,原问题的一套参数与局原问题的一套参数与局部

10、处理对象又活跃起来了。部处理对象又活跃起来了。（2）回归到原问题已经得到问题的解）回归到原问题已经得到问题的解,回归并不引起其回归并不引起其他动作。他动作。16递归的例子计算n!根据公式 n!=1 当n=0 =n*(n-1)! 当n!=0函数参数为nint f(int n) if (!n) return 1; else return (n*f(n-1); 17递归的例子斐波那契数列(fibonacci)f(0)=0f(1)=1f(n)=f(n-1)+f(n-2) (n=2)int f(int n) if (!n) return 0; elseif (n=1) return 1 ; else r

11、eturn(f(n-1)+f(n-2);18梵塔问题算法分析：算法分析：用用A A、B B、C C分别表示三根针分别表示三根针将将n n个盘由个盘由A A移到移到C C上的操作步骤为：上的操作步骤为：（1 1）将）将A A上的上的n-1n-1个盘借助个盘借助C C移到移到B B上上（2 2）把）把A A上剩下的一个盘由上剩下的一个盘由A A移到移到C C上上（3 3）将）将B B上的上的n-1n-1个盘借助个盘借助A A移到移到C C上上这样处理后这样处理后, ,问题的规模减少问题的规模减少1 1。当。当n=1n=1的的时候，就可以直接处理了。时候，就可以直接处理了。19穷举演算n = 3A

12、B CA B CA B CA B C( 1 )( 2 ) A TO C( 3 ) A TO B(4) C TO B20穷举演算(续） A B C( 5 ) A TO C A B CA B CA B C( 6 ) B TO A (7 ) B TO C (8 ) A TO C 21梵塔问题:子程序/* 程序HANOI.C: 梵塔问题-*/#include #define N 3void move(int from, int to) printf(From %c to %cn, from, to);void hanoi(int n, int p1, int p2, int p3) if(n=1) m

13、ove(p1, p3); else hanoi(n-1, p1, p3, p2); move(p1, p3); hanoi(n-1, p2, p1, p3); /* 测试用主函数 */ main() hanoi(N, A, B, C);当n=64时，移动次数=？花费时间=？ h(n)=2h(n-1)+1 = 2(2h(n-2)+1)+1=22h(n-2)+2+1 = 23h(n-3)+22+2+1 =2nh(0)+2n-1+22+2+1 = 2n-1+22+2+1=2n-1需要移动盘子的次数为： 264-1=18446744073709551615假定每秒移动一次，一年有31536000秒，则

14、僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。这样的问题也称为难解问题，虽然理论上可以解决，但是在n值比较大的情况下，计算时间太大。对于此类问题，人类也一直在寻找是否有更快的计算算法。2.3 算法复杂性中的难解性问题、P类问题和NP类问题 算法复杂性包括算法的空间以及时间两方面的复杂性问题，梵天塔问题主要讲的是算法的时间复杂性。 关于梵天塔问题算法的时间复杂度，可以用一个指数函数O(2n)来表示，显然，当n很大（如10000）时，计算机是无法处理的。相反，当算法的时间复杂度的表示函数是一个多项式，如

15、O(n2)时，则可以处理。因此，一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。 在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定PNP。2.4 证比求易算法 为了更好地理解计算复杂性的有

16、关概念，我国学者洪加威曾经讲了一个被人称为“证比求易算法”的童话，用来帮助读者理解计算复杂性的有关概念，大致内容如下。 从前，有一个酷爱数学的年轻国王艾述向邻国一位聪明美丽的公主秋碧贞楠求婚。公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。 国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。公主说：“我再给你一次机会，如果还求不出，将

17、来你只好做我的证婚人了。” 国王立即回国，并向时任宰相的大数学家孔唤石求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位，他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。顺序算法和并行算法国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解

18、性问题，其实这是一种误解。当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。阿达尔定律设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，Sp为并行计算机系统最大的加速能力，则 设f=1%，p，则Sp=100。串行执行操作仅占全部操作1%，解题速度最多也只能提高一百倍。对难解性问题而言，提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。2.5 P NP ？ P类问题存在多项式时间的算法的一类问题；NP类问题非多项式时间算法解的一类问题。像梵塔问题、推销员旅行问题、（命题表达