《计算机领域典型问题》由会员分享，可在线阅读，更多相关《计算机领域典型问题（55页珍藏版）》请在金锄头文库上搜索。
1、 计算机领域典型问题 在在人人类类社社会会的的发发展展过过程程中中，人人们们提提出出过过许许多多具具有有深深远远意意义义的的科科学学问问题题，其其中中对对计计算算机机学学科科一一些些分分支支领领域域的的形形成成和和发发展展起起了了重重要要的的作作用用。另另外外，在在计计算算机机学学科科的的发发展展过过程程中中，为为了了便便于于对对计计算算机机科科学学中中有有关关问问题题和和概概念念的的本本质质的的理理解解，人人们们还还给给出出了了不不少少反反映映该该学学科科某某一一方方面面本本质质特特征征的的典典型实例，在这里一并归于计算机学科的典型问题。型实例，在这里一并归于计算机学科的典型问题。 计计算算
2、机机学学科科典典型型问问题题的的提提出出及及研研究究，不不仅仅有有助助于于我我们们深深刻刻地地理理解解计计算算机机学学科科，而而且且还还对对学学科科的的发发展展有有着着十十分分重要的推动作用。重要的推动作用。 n下面分别对图论中有代表性的哥尼斯堡下面分别对图论中有代表性的哥尼斯堡七桥问题，算法与算法复杂性领域中有七桥问题，算法与算法复杂性领域中有代表性的汉诺（代表性的汉诺（Hanoi Hanoi ）塔问题，算法）塔问题，算法复杂性中的难解性问题，证比求易算法，复杂性中的难解性问题，证比求易算法，旅行商问题与组合爆炸问题，哲学家共旅行商问题与组合爆炸问题，哲学家共餐问题餐问题, ,图灵测试问题，
3、博弈问题等问图灵测试问题，博弈问题等问题及其相关内容进行分析。题及其相关内容进行分析。补充知识补充知识 计算机领域典型问计算机领域典型问题题n1歌尼斯堡七桥问题与哈密尔顿回路问题歌尼斯堡七桥问题与哈密尔顿回路问题n2汉诺塔问题汉诺塔问题n3算法复杂性中的难解性问题算法复杂性中的难解性问题n4哲学家共餐问题哲学家共餐问题n5旅行商问题旅行商问题n6图灵测试问题图灵测试问题n7搏弈问题搏弈问题1 歌尼斯堡七桥问题与哈密尔顿回路问题n 1818世世纪纪中中叶叶，当当时时东东普普鲁鲁士士有有一一座座哥哥尼尼斯斯堡堡（KonigsbergKonigsberg）城城，城城中中有有一一条条贯贯穿穿全全市市的
4、的普普雷雷格格尔尔（PregolPregol）河河，河河中中央央有有座座小小岛岛，叫叫奈奈佛佛夫夫（KneiphofKneiphof）岛岛，普普雷雷格格尔尔河河的的两两条条支支流流环环绕绕其其旁旁，并并将将整整个个城城市市分分成成北北区区、东区、南区和岛区东区、南区和岛区4 4个区域，全城共有个区域，全城共有7 7座桥将座桥将4 4个城区相连起来。个城区相连起来。 北区北区东区东区岛区岛区 南区南区图图1 1 哥尼斯堡七桥地理位置示意图哥尼斯堡七桥地理位置示意图n当当时时该该城城市市的的人人们们热热衷衷一一个个难难题题：一一个个人人怎怎样样不不重重复复地地走走完完七七桥桥，最最后后回回到到出出
5、发发地地点点？即即寻寻找找走走遍遍这这7 7座座桥桥，且且只只许许走走过过每每座座桥桥一一次次，最最后后又又回回到到原原出出发发点点的的路路径径。试试验验者者都都没没有有解解决决这这个个难难题题。17361736年年，瑞瑞士士数数学学家家列列昂昂纳纳德德欧欧拉拉（L.EulerL.Euler）发发表表图图论论的的首首篇篇论论文文，论论证证了了该该问问题题无无解解，即即从从一一点点出出发发不不重重复复地地走走遍遍七七桥桥，最最后后又又回回到到原原来来出出发发点点是是不不可可能能的的。他他论论证证所所用用的的图图为为图图2 2所所示示。后后人人为为了了纪纪念念数数学学家家欧欧拉拉，将将这这个个难难
6、题题称称为为“哥哥尼尼斯斯堡堡七七桥问题桥问题”。图图2 2 哥哥尼尼斯斯堡堡七七桥桥问问题题示意图示意图CBDAn为了解决哥尼斯堡七桥问题，欧拉用为了解决哥尼斯堡七桥问题，欧拉用4 4个字母个字母A A、B B、C C、D D代表代表4 4个城个城区，并用区，并用7 7条线表示条线表示7 7座桥，如图座桥，如图2 2所示。在图中，只有所示。在图中，只有4 4个点和个点和7 7条线，条线，这样做是基于该问题本质的考虑，抽象出问题最本质的东西，忽视这样做是基于该问题本质的考虑，抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽问题非本质的东西（如桥的长度等），
7、从而将哥尼斯堡七桥问题抽象成为一个数学问题，即经过图中每边一次且仅一次的回路问题了。象成为一个数学问题，即经过图中每边一次且仅一次的回路问题了。欧拉在论文中论证了这样的回路是不存在的，后来，人们把有这样欧拉在论文中论证了这样的回路是不存在的，后来，人们把有这样回路的图称为欧拉图。回路的图称为欧拉图。 n将其有经过所有边的简单生成回路的图称为欧拉图将其有经过所有边的简单生成回路的图称为欧拉图n欧拉不仅给出了哥尼斯堡七桥问题的证明，还将问题进行了一般化欧拉不仅给出了哥尼斯堡七桥问题的证明，还将问题进行了一般化处理，即对给定的任意一个河道图与任意多座桥，判定可能不可处理，即对给定的任意一个河道图与任
8、意多座桥，判定可能不可能每座桥恰好走过一次，并用数学方法给出了能每座桥恰好走过一次，并用数学方法给出了3 3条判定规则：条判定规则：（1 1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的；的；（2 2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线；找到所要求的路线；（3 3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。要求的路线都能实现。 欧拉的论文为图论的形成奠定了基
9、础。今天，图论已广泛地应用欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。充分的发展。 n在图论中除了欧拉回路以外，在图论中除了欧拉回路以外，还有一个著名的还有一个著名的“哈密尔顿回哈密尔顿回路问题路问题”。十九世纪爱尔
10、兰数。十九世纪爱尔兰数学家哈密尔顿学家哈密尔顿(Hamilton)(Hamilton)发明发明了一种叫做周游世界的数学游了一种叫做周游世界的数学游戏。它的玩法是：给你一个正戏。它的玩法是：给你一个正十二面体，它有二十个顶点，十二面体，它有二十个顶点，把每个顶点看做一个城市，把把每个顶点看做一个城市，把正十二面体的三十条棱看成连正十二面体的三十条棱看成连接这些城市的路。请你找一条接这些城市的路。请你找一条从某城市出发，经过每个城市从某城市出发，经过每个城市恰好一次，并且最后回到出发恰好一次，并且最后回到出发点的路线。我们把正十二面体点的路线。我们把正十二面体投影到平面上，在图投影到平面上，在图3
11、 3中标出了中标出了一种走法，即从城市一种走法，即从城市1 1出发，经出发，经过过2 2，3 3，2020，最后回到，最后回到1 1。2019181716111213151098123146547图图3 3周游世界游戏示意图周游世界游戏示意图n “ “哈密尔顿回路问题哈密尔顿回路问题”与与“欧拉回路问题欧拉回路问题”看上去十分相似，然而又是完全不同的两个问题。看上去十分相似，然而又是完全不同的两个问题。“哈密尔顿回路问题哈密尔顿回路问题”是访问每个结点一次，而是访问每个结点一次，而“欧拉回路问题欧拉回路问题”是访问每条边一次。对图是访问每条边一次。对图G G是否是否存在存在“欧拉回路欧拉回路”
12、前面已给出充分必要条件，而前面已给出充分必要条件，而对图对图G G是否存在是否存在“哈密尔顿回路哈密尔顿回路”至今仍未找到满至今仍未找到满足该问题的充分必要条件。足该问题的充分必要条件。 2汉诺塔问题n 传说在古代印度的贝拿勒斯神庙里安放了一块黄传说在古代印度的贝拿勒斯神庙里安放了一块黄铜座，座上竖有三根宝石柱子。在第一根宝石柱上，按照铜座，座上竖有三根宝石柱子。在第一根宝石柱上，按照从小到大、自上而下的顺序放有从小到大、自上而下的顺序放有6464个直径大小不一的金盘个直径大小不一的金盘子，形成一座金塔，如图子，形成一座金塔，如图4 44 4所示，即所谓的汉诺塔（又所示，即所谓的汉诺塔（又称梵
13、天塔）。天神让庙里的僧侣们将第一根柱子上的称梵天塔）。天神让庙里的僧侣们将第一根柱子上的6464个个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下迁移，同时定下3 3条规则：条规则：n n （1 1）每次只能移动一个盘子；）每次只能移动一个盘子；n （2 2）盘子只能在三根柱子上来回移动，不能放在他）盘子只能在三根柱子上来回移动，不能放在他处；处；n （3 3）在移动过程中，三根柱子上的盘子必须始终保）在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。图持大盘在下，小盘在上。图4 4汉诺塔问题示意图汉诺塔问题示意图
14、6464个个盘子盘子6363个盘子个盘子n 据说当这据说当这6464个盘子全部移到第三根柱子上后，世个盘子全部移到第三根柱子上后，世界末日就要到了。这就是著名的汉诺塔塔问题。界末日就要到了。这就是著名的汉诺塔塔问题。图图4 4汉诺塔问题示意图汉诺塔问题示意图64个个盘子盘子63个个盘子盘子n 用计算机求解一个实际问题，首先要从这个实际问题用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，经过调试和运行，从而完成法，最后根据算法编写程序，经过调试和运行，从而完成该问题的求解。
15、从实际问题抽象出一个数学模型的实质，该问题的求解。从实际问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题主要的、本质的内容，其实就是要用数学的方法抽取问题主要的、本质的内容，最终实现对该问题的正确认识。最终实现对该问题的正确认识。n 汉诺塔问题是一个典型的用递归方法来解决的问题。汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算机学科中的一个重要概念。所谓递归，就是将递归是计算机学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。而一个较大的问题归约为一个或多个子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。这些子问题比原
16、问题简单，且在结构上与原问题相同。n 根据递归方法，我们可以将根据递归方法，我们可以将6464个盘子的汉诺塔问题个盘子的汉诺塔问题转化为求解转化为求解6363个盘子的汉诺塔问题，如果个盘子的汉诺塔问题，如果6363个盘子的汉个盘子的汉诺塔问题能够解决，则可以将诺塔问题能够解决，则可以将6363个盘子先移动到第二个个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将最后又一次将6363个盘子从第二个柱子移动到第三个柱子个盘子从第二个柱子移动到第三个柱子上。上。n如图如图4 4所示，则可以解决所示，则可以解决6464个盘子
17、的汉诺塔问题。依个盘子的汉诺塔问题。依此类推，此类推，6363个盘子的汉诺塔求解问题可以转化为个盘子的汉诺塔求解问题可以转化为6262个个盘子的汉诺塔求解问题，盘子的汉诺塔求解问题，6262个盘子的汉诺塔求解问题个盘子的汉诺塔求解问题又可以转化为又可以转化为6161个盘子的汉诺塔求解问题，直到个盘子的汉诺塔求解问题，直到1 1个个盘子的汉诺塔求解问题。再由盘子的汉诺塔求解问题。再由1 1个盘子的汉诺塔的解个盘子的汉诺塔的解求出求出2 2个盘子的汉诺塔，直到解出个盘子的汉诺塔，直到解出6464个盘子的汉诺塔个盘子的汉诺塔问题。问题。 按照上面的算法，按照上面的算法，n n个盘子的汉诺塔问题需要移
18、动的盘子个盘子的汉诺塔问题需要移动的盘子数是数是n-1n-1个盘子的汉诺塔问题需要移动的盘子数的个盘子的汉诺塔问题需要移动的盘子数的2 2倍加倍加1 1。于是于是 h(nh(n)=2h(n-1)+1)=2h(n-1)+1 =2(2h(n-2)+1)+1=22h(n-2)+2+1 =2(2h(n-2)+1)+1=22h(n-2)+2+1 =23h(n-3)+22+2+1 =23h(n-3)+22+2+1 = = =2nh(0)+2n-1+22+2+1 =2nh(0)+2n-1+22+2+1 =2n-1+22+2+1 =2n-1+22+2+1 =2n-1 =2n-1因此，要完成汉诺塔的搬迁，需要移
19、动盘子的次数为：因此，要完成汉诺塔的搬迁，需要移动盘子的次数为： 264-1=18446744073709551615 264-1=18446744073709551615 如果每秒移动一次，一年有如果每秒移动一次，一年有3153600031536000秒，则僧侣们一秒，则僧侣们一刻不停地来回搬动，也需要花费大约刻不停地来回搬动，也需要花费大约58495849亿年的时间。亿年的时间。假定计算机以每秒假定计算机以每秒10001000万个盘子的速度进行搬迁，则万个盘子的速度进行搬迁，则需要花费大约需要花费大约5849058490年的时间。年的时间。3算法复杂性中的难解性问题n算法分析是计算机科学的
20、一项主要工作。为了进行算法比算法分析是计算机科学的一项主要工作。为了进行算法比较，我们必须给出算法效率的某种衡量标准。较，我们必须给出算法效率的某种衡量标准。n假设假设M M是一种算法，并设是一种算法，并设n n为输入数据的规模。实施为输入数据的规模。实施M M所占所占用的时间和空间是衡量该算法效率的两个主要指标。时间用的时间和空间是衡量该算法效率的两个主要指标。时间由由“操作操作”次数衡量。比如，对于排序和查找，我们对比次数衡量。比如，对于排序和查找，我们对比较次数计数。空间由实施该算法所需的最大内存来衡量。较次数计数。空间由实施该算法所需的最大内存来衡量。 n算法算法M M的复杂性是一个函
21、数的复杂性是一个函数(n(n) )，它对于输人数据的规模，它对于输人数据的规模n n给出运行该算法所需时间与所需存储空间。执行一个算法给出运行该算法所需时间与所需存储空间。执行一个算法所需存储空间通常就是数据规模的倍数。因此，除非特殊所需存储空间通常就是数据规模的倍数。因此，除非特殊情况，情况，“复杂性复杂性”将指运行算法的时间。将指运行算法的时间。 对于时间复杂性函数对于时间复杂性函数(n(n) )。它通常不仅仅与输入。它通常不仅仅与输入数据的规模有关，还与特定的数据有关。例如，在一篇数据的规模有关，还与特定的数据有关。例如，在一篇英文短文中查找第一次出现的英文短文中查找第一次出现的3 3个
22、字母的单词个字母的单词W W。那么，。那么，如果如果W W为定冠词为定冠词“the”the”，则，则W W很可能在短文的开头部分出很可能在短文的开头部分出现，于是现，于是(n(n) )值将会比较小；如果值将会比较小；如果W W是单词是单词“axeaxe，”，则则W W甚至可能不会在短文中出现，所以甚至可能不会在短文中出现，所以(n(n) )可能会很大。可能会很大。 因此，考虑对于适当的情况，求出复杂性函数因此，考虑对于适当的情况，求出复杂性函数(n(n) )。在复杂性理论中研究得最多的两种情况是：。在复杂性理论中研究得最多的两种情况是： (1)(1)最坏情况最坏情况 对于任何可能的输入，对于任
23、何可能的输入，(n(n) )的最大值。的最大值。 (2)(2)平均情况平均情况 (n(n) )的期望值。的期望值。 假定假定M M是一个算法，并设是一个算法，并设n n为输入数据的大小。显然为输入数据的大小。显然M M的复的复杂性杂性(n(n) )随着随着n n的增大而增大。通常我们需要考察的是的增大而增大。通常我们需要考察的是(n(n) )的增长率，这常常由的增长率，这常常由(n(n) )与某标准函数相比较而得，与某标准函数相比较而得，例如例如 loglog2 2n nn n， n logn log2 2n n， n n2 2， n n3 3， 2 2n n 等等，都可被用作为标准函数，这些
24、函数是按其增长等等，都可被用作为标准函数，这些函数是按其增长率列出的：对数函数率列出的：对数函数log2nlog2n增长最慢，指数函数增长最慢，指数函数2n2n增长最增长最快，而多项式函数快，而多项式函数ncnc的增长率随其指数的增长率随其指数c c的增大而变快。的增大而变快。 将复杂性函数与一个标准函数相比较的一种方法是利将复杂性函数与一个标准函数相比较的一种方法是利用用“大大O”记号，我们给出它的定义：记号，我们给出它的定义： 设设(x(x) )与与g(xg(x) )为定义于为定义于R R或或R R的子集上的任意两个函的子集上的任意两个函数。我们说数。我们说“(x(x) )与与g(xg(x
25、) )同阶同阶”，记作，记作 (x(x) )O(g(g(g(g)。 如果存在实数如果存在实数k k和正常数和正常数C C使得对于所有的使得对于所有的x xk k有有 | |(x(x)| C |)| C |g(xg(x)|)|。如如 n n2 2+n+1=O(n+n+1=O(n2 2) )，该表达式表示，当，该表达式表示，当n n足够大时表达式左边约足够大时表达式左边约等于等于n n2 2。常见的大常见的大O O表示形式有：表示形式有： O(1)(1)称为常数级；称为常数级； O(logn(logn) )称为对数级；称为对数级； O(n(n) )称为线性级；称为线性级； O(nc(nc) )称为
26、多项式级；称为多项式级； O(c(cn n) )称为指数级；称为指数级； O(n(n!)!)称为阶乘级。称为阶乘级。 用以上表示方法，在汉诺塔问题中，需要移动用以上表示方法，在汉诺塔问题中，需要移动的盘子次数为的盘子次数为h(nh(n)= 2n-1)= 2n-1，则该问题的算法时间复杂，则该问题的算法时间复杂度表示为度表示为O(2n)(2n)。 一个问题求解算法的时间复杂度大于多项式一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随（如指数函数）时，算法的执行时间将随n n的增加而急的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，剧增长，以致即使是中等规模的问
27、题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。于是在计算复杂性中，将这一类问题称为难解性问题。 为了更好地理解计算及其复杂性的有关概念，我为了更好地理解计算及其复杂性的有关概念，我国学者洪加威曾经讲了一个被人称为国学者洪加威曾经讲了一个被人称为“证比求易算法证比求易算法”的童话，用来帮助读者理解计算复杂性的有关概念，具的童话，用来帮助读者理解计算复杂性的有关概念，具体内容如下。体内容如下。 很久以前，有一个年轻的国王，名叫艾述。他酷很久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有名的数学家孔唤石当宰相。爱数学，聘请了当时最有名的数学家孔唤石当宰相。 邻国有一
28、位聪明美丽的公主，名字叫秋碧贞楠。邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，便亲自登门求婚。艾述国王爱上了这位邻国公主，便亲自登门求婚。 公主说：公主说：“你如果向我求婚，请你先求出你如果向我求婚，请你先求出48 770 48 770 428 433 377 171428 433 377 171的一个真因子，一天之内交卷。的一个真因子，一天之内交卷。” ” 艾艾述听罢，心中暗喜，心想：我从述听罢，心中暗喜，心想：我从2 2开始，一个一个地试，开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？看看能不能除尽这个数，还怕找不到这个真因子吗？ 艾述国王十分
29、精于计算，他一秒钟就算完一个数。艾述国王十分精于计算，他一秒钟就算完一个数。可是，他从早到晚，共算了三万多个数，最终还是没有可是，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：结果。国王向公主求情，公主将答案相告：223 092 223 092 827827是它的一个真因子。国王很快就验证了这个数确能是它的一个真因子。国王很快就验证了这个数确能除尽除尽48 770 428 433 377 17148 770 428 433 377 171。公主说：公主说：“我再给你一次机会，如果还求不出，将来你我再给你一次机会，如果还求不出，将来你只好做我的证婚人了只好做我的
30、证婚人了”。国王立即回国，召见宰相孔。国王立即回国，召见宰相孔唤石，大数学家在仔细地思考后认为这个数为唤石，大数学家在仔细地思考后认为这个数为1717位，位，如果这个数可以分成两个真因子的乘积，则最小的一如果这个数可以分成两个真因子的乘积，则最小的一个真因子不会超过个真因子不会超过9 9位。于是他给国王出了一个主意：位。于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏百姓用自己的编号去
31、除这个数，除尽了立即上报，赏黄金万两。黄金万两。 于是，国王发动全国上下的民众，再度求婚，终于取得于是，国王发动全国上下的民众，再度求婚，终于取得成功。成功。 在在“证比求易算法证比求易算法”的故事中，国王最先使用的是一种的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后来由宰相提出的顺序算法，其复杂性表现在时间方面，后来由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着
32、处决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。其实这是一种误解。 当将一个问题分解到多个处理器上解决时，由于算法当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。下面，用阿达尔制了并行计算机系统的加速能力。下面，用阿达尔（G.AmdahlG.Amdahl）定律来说明这个问题。）定律来说明这个问题。 设设f f为求解某个问题的计算中存在的必须串行执行的为
33、求解某个问题的计算中存在的必须串行执行的操作占整个计算的百分比，操作占整个计算的百分比，p p为处理器的数目，为处理器的数目，SpSp为并为并行计算机系统最大的加速能力（单位：倍），则行计算机系统最大的加速能力（单位：倍），则Sp 1f +1- -fp 设设f=1%f=1%，pp，则，则Sp=100Sp=100。这说明即使在并行计。这说明即使在并行计算机系统中有无穷多个处理器，解决这个串行执行操作算机系统中有无穷多个处理器，解决这个串行执行操作仅占全部操作仅占全部操作1%1%的问题，其解题速度与单处理器的计算的问题，其解题速度与单处理器的计算机相比最多也只能提高一百倍。因此，对难解性问题而机相
34、比最多也只能提高一百倍。因此，对难解性问题而言，单纯的提高计算机系统的速度是远远不够的，而降言，单纯的提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。低算法复杂度的数量级才是最关键的问题。 国国王王有有众众多多百百姓姓的的帮帮助助，求求亲亲成成功功是是自自然然的的事事。但但是是，如如果果换换成成是是一一个个贫贫民民百百姓姓的的小小伙伙子子去去求求婚婚，那那就就困困难难了了。不不过过，小小伙伙子子可可以以从从国国王王求求亲亲取取得得成成功功所所采采用用的的并并行行算算法法中中得得到到一一个个启启发发，那那就就是是：他他可可以以随随便便猜猜一一个个数数，然然后后验验证证
35、这这个个数数。当当然然，这这样样做做成成功功的的可可能能性性很很小小，不不过过，万万一一小小伙伙子子运运气气好好猜猜着着了了呢呢？由由于于一一个个数数和和它它的的因因子子之之间间存存在在一一些些有有规规律律的的联联系系，因因此此，数数论论知知识识水水平平较高的人猜中的可能性就大。较高的人猜中的可能性就大。 我们说，这个小伙子使用的算法叫做非确定性算法。我们说，这个小伙子使用的算法叫做非确定性算法。这样的算法需要有一种假想但实际并不存在的非确定性计这样的算法需要有一种假想但实际并不存在的非确定性计算机才能运行，其理论上的计算模型是非确定性图灵机。算机才能运行，其理论上的计算模型是非确定性图灵机。
36、 在算法计算复杂性的研究中，将所有可以在多项式时在算法计算复杂性的研究中，将所有可以在多项式时间内求解的问题称为间内求解的问题称为P P类问题，而将所有在多项式时间内类问题，而将所有在多项式时间内可以验证的问题称为可以验证的问题称为NPNP类问题，由于类问题，由于P P类问题采用的是确类问题采用的是确定性算法，定性算法，NPNP类问题采用的是非确定性算法，确定性算法类问题采用的是非确定性算法，确定性算法是非确定性算法的一个特例，因此是非确定性算法的一个特例，因此P P NPNP。 对于大多数实际问题来说，找到一个解可能很难，检对于大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，
37、所以都属于验一个解常常比较容易，所以都属于NPNP类问题。现在计算类问题。现在计算机科学研究中一个悬而未决的重要问题是机科学研究中一个悬而未决的重要问题是P=?NPP=?NP。到目前为。到目前为止，已经发现了一批可计算但有相当难度的问题是属于止，已经发现了一批可计算但有相当难度的问题是属于NPNP类问题，并且常通过证明一个问题与已知属于类问题，并且常通过证明一个问题与已知属于NPNP类中的某类中的某个问题等价，将其归入个问题等价，将其归入NPNP类问题。类问题。 不过，该问题是否属于不过，该问题是否属于P P类问题，即是否能找到多项式时类问题，即是否能找到多项式时间计算复杂性算法求解该问题，或
38、证明该问题不存在多项式时间计算复杂性算法求解该问题，或证明该问题不存在多项式时间计算复杂性算法求解，至今尚未解决。间计算复杂性算法求解，至今尚未解决。2020世纪世纪7070年代初，库年代初，库克（克（S.A.CookS.A.Cook）和卡尔普（）和卡尔普（R.M.KarpR.M.Karp）在）在P=?NPP=?NP问题上取得重问题上取得重大进展，指出大进展，指出NPNP类中有一小类问题具有以下性质：迄今为止，类中有一小类问题具有以下性质：迄今为止，这些问题多数还没有人找到多项式时间计算复杂性算法。但是，这些问题多数还没有人找到多项式时间计算复杂性算法。但是，一旦其中的一个问题找到了多项式时间
39、计算复杂性算法，这个一旦其中的一个问题找到了多项式时间计算复杂性算法，这个类中的其他问题也能找到多项式时间计算复杂算法，那么就可类中的其他问题也能找到多项式时间计算复杂算法，那么就可以断定以断定P=NPP=NP。 即如果确属于这个类中的某个问题被证明不存在多项式时间即如果确属于这个类中的某个问题被证明不存在多项式时间计算复杂性算法，那么，就等于证明了计算复杂性算法，那么，就等于证明了PNPPNP。通常，将这类。通常，将这类问题称为问题称为NPNP完全问题。完全问题。 19821982年，库克因其在计算复杂性理论方面（主要是在年，库克因其在计算复杂性理论方面（主要是在NPNP完完全性理论方面）的
40、奠基性工作而荣获全性理论方面）的奠基性工作而荣获ACMACM图灵奖。图灵奖。 4哲学家共餐问题 对哲学家共餐问对哲学家共餐问题可以作这样的描述题可以作这样的描述( (如图如图5 5所示所示) )：5 5个哲个哲学家围坐在一张圆桌学家围坐在一张圆桌旁，每个人的面前摆旁，每个人的面前摆有一碗面条，碗的两有一碗面条，碗的两旁各摆有一只筷子。旁各摆有一只筷子。 图图5 5哲学家共餐餐桌示意图哲学家共餐餐桌示意图 假设哲学家的生活除了吃饭就是思考问题，而吃饭的假设哲学家的生活除了吃饭就是思考问题，而吃饭的时候需要左手拿一只筷子，右手拿一只筷子，然后开始进餐。时候需要左手拿一只筷子，右手拿一只筷子，然后开
41、始进餐。吃完后又将筷子放回原处，继续思考问题。那么，一个哲学吃完后又将筷子放回原处，继续思考问题。那么，一个哲学家的生活进程可表示为：家的生活进程可表示为： （1 1）思考问题；）思考问题； （2 2）饿了停止思考，左手拿一只筷子（拿不到就等）；）饿了停止思考，左手拿一只筷子（拿不到就等）； （3 3）右手拿一只筷子（拿不到就等）右手拿一只筷子（拿不到就等） ； （4 4）进餐；图）进餐；图5 5哲学家共餐餐桌示意图哲学家共餐餐桌示意图 （5 5）放右手筷子；）放右手筷子； （6 6）放左手筷子；）放左手筷子； （7 7）重新回到思考问题状态（）重新回到思考问题状态（1 1）。）。 问题是：如
42、何协调问题是：如何协调5 5个哲学家的生活进程，使得每一个个哲学家的生活进程，使得每一个哲学家最终都可以进餐。哲学家最终都可以进餐。 考虑下面的两种情况：考虑下面的两种情况：（1 1）按哲学家的活动进程，当所有的哲学家都同时拿起左）按哲学家的活动进程，当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，最终饿死。处于等待状态，那么哲学家都将无法进餐，最终饿死。（2 2）将哲学家的活动进程修改一下，变为当右手的筷子拿）将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子，
43、这种情况是不是就没有问不到时，就放下左手的筷子，这种情况是不是就没有问题？不一定，因为可能在一个瞬间，所有的哲学家都同题？不一定，因为可能在一个瞬间，所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子，等一会，又同时拿起左手的筷子，同时放下左手的筷子，等一会，又同时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家一样都吃不到如此这样永远重复下去，则所有的哲学家一样都吃不到面条。面条。 以上两个方面的问题，其实反映的是程序并发执行以上两个方面的问题，其实反映的是程序并发执行时进程同步的两个问题，一个是死锁（时进程
44、同步的两个问题，一个是死锁（DeadlockDeadlock），另），另一个是饥饿（一个是饥饿（StarvationStarvation）。）。 哲学家共餐问题实际上反映了计算机程序设计中多哲学家共餐问题实际上反映了计算机程序设计中多进程共享单个处理机资源时的并发控制问题。要防止这进程共享单个处理机资源时的并发控制问题。要防止这种情况发生，就必须建立一种机制，既要让每一个哲学种情况发生，就必须建立一种机制，既要让每一个哲学家都能吃到面条，又不能让任何一个哲学家始终拿着一家都能吃到面条，又不能让任何一个哲学家始终拿着一根筷子不放。采用并发程序语言、根筷子不放。采用并发程序语言、PetriPetr
45、i网、网、CSPCSP等工具，等工具，都能很容易地解决这个问题。都能很容易地解决这个问题。 与程序并发执行时进程同步有关的经典问题还有：与程序并发执行时进程同步有关的经典问题还有：读者写者问题（读者写者问题（ReaderReaderWriter ProblemWriter Problem）、理发师睡）、理发师睡眠问题（眠问题（Sleeping Barber ProblemSleeping Barber Problem）等。）等。 5旅行商问题 旅行商问题（旅行商问题（Traveling Salesman ProblemTraveling Salesman Problem，简称，简称TSPTSP
46、）是威廉）是威廉哈密尔顿（哈密尔顿（W.R.HamiltonW.R.Hamilton）爵士和英国数）爵士和英国数学家克克曼（学家克克曼（T.P.KirkmanT.P.Kirkman）于）于1919世纪初提出的一个数学世纪初提出的一个数学问题。这是一个典型的问题。这是一个典型的NPNP完全性问题。其大意是：有若干完全性问题。其大意是：有若干个城市，任何两个城市之间的距离都是确定的，现要求一个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好城市逗留一
47、次，最后回到原出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。一条最短的路线，使其旅行的费用最少。 人们在考虑解决这个问题时，一般首先想到的最原人们在考虑解决这个问题时，一般首先想到的最原始的一种方法是：列出每一条可供选择的路线（即始的一种方法是：列出每一条可供选择的路线（即对给定的城市进行排列组合），计算出每条路线的对给定的城市进行排列组合），计算出每条路线的总里程，最后从中选出一条最短的路线。假设现在总里程，最后从中选出一条最短的路线。假设现在给定的给定的4 4个城市分别为个城市分别为A A、B B、C C和和D D，各城市之间的距，各城市之间的距离为已知数，如图离为已知数，
48、如图6 6、图、图7 7所示。从图中可以看到，所示。从图中可以看到，可供选择的路线共有可供选择的路线共有6 6条，从中很快可以选出一条总条，从中很快可以选出一条总距离最短的路线。距离最短的路线。ABCD256424图图6 6城市交通图城市交通图A265BCD244442BDCCBD224444ACCBDBD522665图图7 7组合路径图组合路径图 设城市数目为设城市数目为n n时，那么组合路径数则为（时，那么组合路径数则为（n-1n-1）！。很）！。很显然，当城市数目不多时要找到最短距离的路线并不难，显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指
49、数级急但随着城市数目的不断增大，组合路线数将呈指数级急剧增长，以至达到无法计算的地步，这就是所谓的剧增长，以至达到无法计算的地步，这就是所谓的“组组合爆炸问题合爆炸问题”。假设现在城市的数目增为。假设现在城市的数目增为2020个，组合路个，组合路径数则为（径数则为（20-120-1）！）！1.21610171.2161017，如此庞大的组合数，如此庞大的组合数目，若计算机以每秒检索目，若计算机以每秒检索10001000万条路线的速度计算，也万条路线的速度计算，也需要花上需要花上386386年的时间。年的时间。 6图灵测试问题 在计算机学科诞生后，为解决人工智能中一些激烈争论在计算机学科诞生后，
50、为解决人工智能中一些激烈争论的问题，图灵和西尔勒又分别提出了能反映人工智能本质的问题，图灵和西尔勒又分别提出了能反映人工智能本质特征的两个著名的哲学问题，即特征的两个著名的哲学问题，即“图灵测试图灵测试”和西尔勒的和西尔勒的“中文屋子中文屋子”，沿着图灵等人对，沿着图灵等人对“智能智能”的理解，人们在的理解，人们在人工智能领域取得了长足的进展，其中人工智能领域取得了长足的进展，其中“深蓝（深蓝（Deep Deep BlueBlue）”战胜国际象棋大师卡斯帕罗夫（战胜国际象棋大师卡斯帕罗夫（G.KasparovG.Kasparov）就）就是一个很好的例证。是一个很好的例证。 图灵于图灵于1950
51、1950年在英国年在英国 Mind Mind杂志上发表了杂志上发表了Computing Machinery and IntelligenceComputing Machinery and Intelligence一文，文一文，文中提出了中提出了“机器能思维吗？机器能思维吗？”这样一个问题，并给出了这样一个问题，并给出了一个被后人称之为一个被后人称之为“图灵测试（图灵测试（Turing TestTuring Test）”的模仿的模仿游戏。游戏。 这个游戏由这个游戏由3 3个人来完成：一个男人（个人来完成：一个男人（A A），一个女），一个女人（人（B B），一个性别不限的提问者（），一个性别不限
52、的提问者（C C）。提问者（）。提问者（C C）呆在与其他两个游戏者相隔离的房间里。游戏的目标是呆在与其他两个游戏者相隔离的房间里。游戏的目标是让提问者通过对其他两人的提问来鉴别其中哪个是男人，让提问者通过对其他两人的提问来鉴别其中哪个是男人，哪个是女人。为了避免提问者通过他们的声音、语调轻哪个是女人。为了避免提问者通过他们的声音、语调轻易地作出判断，最好是在提问者和两游戏者之间通过一易地作出判断，最好是在提问者和两游戏者之间通过一台电传打字机来进行沟通。提问者只被告知两个人的代台电传打字机来进行沟通。提问者只被告知两个人的代号为号为X X和和Y Y，游戏的最后他要作出，游戏的最后他要作出“X
53、 X是是A A，Y Y是是B”B”或或“X X是是B B，Y Y是是A”A”的判断。的判断。 现在，把上面这个游戏中的男人（现在，把上面这个游戏中的男人（A A）换成一部机器来）换成一部机器来扮演，如果提问者在与机器、女人的游戏中作出的错扮演，如果提问者在与机器、女人的游戏中作出的错误判断与在男人、女人之间的游戏中作出错误判断的误判断与在男人、女人之间的游戏中作出错误判断的次数是相同的，那么，就可以判定这部机器是能够思次数是相同的，那么，就可以判定这部机器是能够思维的。维的。 图灵关于图灵关于“图灵测试图灵测试”的论文发表后引发了很多的争的论文发表后引发了很多的争论，以后的学者在讨论机器思维时
54、大多都要谈到这个论，以后的学者在讨论机器思维时大多都要谈到这个游戏。游戏。 “ “图灵测试图灵测试”只是从功能的角度来判定机器是否能思只是从功能的角度来判定机器是否能思维，也就是从行为主义角度来对维，也就是从行为主义角度来对“机器思维机器思维”进行定进行定义。尽管图灵对义。尽管图灵对“机器思维机器思维”的定义是不够严谨的，的定义是不够严谨的，但他关于但他关于“机器思维机器思维”定义的开创性工作对后人的研定义的开创性工作对后人的研究具有重要意义，因此，一些学者认为，图灵发表的究具有重要意义，因此，一些学者认为，图灵发表的关于关于“图灵测试图灵测试”的论文标志着现代机器思维问题讨的论文标志着现代机
55、器思维问题讨论的开始。论的开始。 根据图灵的预测，到根据图灵的预测，到20002000年，此类机器能通过测试。年，此类机器能通过测试。现在，在某些特定的领域，如博弈领域，现在，在某些特定的领域，如博弈领域，“图灵测试图灵测试”已取得了成功，已取得了成功，19971997年，年，IBMIBM公司研制的计算机公司研制的计算机“深蓝深蓝”就战胜了国际象棋冠军卡斯帕罗夫。就战胜了国际象棋冠军卡斯帕罗夫。 在未来，如果我们能像图灵揭示计算本质那样揭示在未来，如果我们能像图灵揭示计算本质那样揭示人类思维的本质，即人类思维的本质，即“能行能行”思维，那么制造真正思思维，那么制造真正思维机器的日子也就不长了。
56、可惜要对人类思维的本质维机器的日子也就不长了。可惜要对人类思维的本质进行描述，还是相当遥远的事情。进行描述，还是相当遥远的事情。 7搏弈问题 博弈问题属于人工智能中一个重要的研究领域。从狭博弈问题属于人工智能中一个重要的研究领域。从狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质的游戏；从广义上讲，博弈就是对策或斗智。赢性质的游戏；从广义上讲，博弈就是对策或斗智。计算机中的博弈问题，一直是人工智能领域研究的重计算机中的博弈问题，一直是人工智能领域研究的重点内容之一。点内容之一。 19131913年，数学家策墨洛（年，数学家策墨洛（E.Zerm
57、eloE.Zermelo）在第五届国）在第五届国际数学会议上发表了际数学会议上发表了关于集合论在象棋博弈理论中关于集合论在象棋博弈理论中的应用的应用（On an Application of Set Theory to On an Application of Set Theory to Game of ChessGame of Chess）的著名论文，第一次把数学和象棋）的著名论文，第一次把数学和象棋联系起来，从此，现代数学出现了一个新的理论，即联系起来，从此，现代数学出现了一个新的理论，即博弈论。博弈论。 19501950年，年，“信息论信息论”创始人香农（创始人香农（A.ShannonA
58、.Shannon）发）发表了表了国际象棋与机器国际象棋与机器（A ChessA ChessPlaying Playing MachineMachine）一文，并阐述了用计算机编制下棋程序的）一文，并阐述了用计算机编制下棋程序的可能性。可能性。 19561956年夏天，由麦卡锡（年夏天，由麦卡锡（J.McCarthyJ.McCarthy）和香农等人）和香农等人共同发起的，在美国达特茅斯（共同发起的，在美国达特茅斯（DartmouthDartmouth）大学举行）大学举行的夏季学术讨论会上，第一次正式使用了的夏季学术讨论会上，第一次正式使用了“人工智能人工智能”这一术语，该次会议的召开对人工智能的
59、发展起到了极这一术语，该次会议的召开对人工智能的发展起到了极大的推动作用。大的推动作用。 当时，当时，IBMIBM公司的工程师塞缪尔（公司的工程师塞缪尔（A. SamuelA. Samuel）也被邀）也被邀请参加了请参加了“达特茅斯达特茅斯”会议，塞缪尔的研究专长正是会议，塞缪尔的研究专长正是电脑下棋。早在电脑下棋。早在19521952年，塞缪尔就运用博弈理论和状年，塞缪尔就运用博弈理论和状态空间搜索技术成功地研制了世界上第一个跳棋程序。态空间搜索技术成功地研制了世界上第一个跳棋程序。该程序经不断地完善于该程序经不断地完善于19591959年击败了它的设计者塞缪年击败了它的设计者塞缪尔本人，尔
60、本人，19621962年，它又击败了美国一个州的冠军年，它又击败了美国一个州的冠军 。 19701970年开始，年开始，ACMACM每年举办一次计算机国际象棋锦标赛直每年举办一次计算机国际象棋锦标赛直到到19941994年（年（19921992年中断过一次），每年产生一个计算机国际年中断过一次），每年产生一个计算机国际象棋赛冠军，象棋赛冠军，19911991年，冠军由年，冠军由IBMIBM的的“深思深思（Deep Deep ThoughtThought）”获得。获得。ACMACM的这些工作极大地推动了博弈问题的这些工作极大地推动了博弈问题的深入研究，并促进了人工智能领域的发展。北京时间的深入研
61、究，并促进了人工智能领域的发展。北京时间19971997年年5 5月初，在美国纽约公平大厦，月初，在美国纽约公平大厦，“深蓝深蓝”与国际象棋冠军与国际象棋冠军卡斯帕罗夫交战，前者以两胜一负三平战胜后者。卡斯帕罗夫交战，前者以两胜一负三平战胜后者。 “ “深蓝深蓝”是美国是美国IBMIBM公司研制的一台高性能并行公司研制的一台高性能并行计算机，它由计算机，它由256256（32 node*832 node*8）个专为国际象棋比赛）个专为国际象棋比赛设计的微处理器组成，据估计，该系统每秒可计算设计的微处理器组成，据估计，该系统每秒可计算2 2亿步棋。亿步棋。“深蓝深蓝”的前身是的前身是“深思深思”
62、，始建于，始建于19851985年。年。19891989年，卡斯帕罗夫首战年，卡斯帕罗夫首战“深思深思”，后者败北。，后者败北。19961996年，在年，在“深思深思”基础上研制出的基础上研制出的“深蓝深蓝”曾再次与卡曾再次与卡斯帕罗夫交战，并以斯帕罗夫交战，并以2 2：4 4负于对手。国际象棋、西洋负于对手。国际象棋、西洋跳棋与围棋、中国象棋一样都属于双人完备博弈。跳棋与围棋、中国象棋一样都属于双人完备博弈。 所谓双人完备博弈就是两位选手对垒，轮流走步，其所谓双人完备博弈就是两位选手对垒，轮流走步，其中一方完全知道另一方已经走过的棋步以及未来可能的走步，中一方完全知道另一方已经走过的棋步以及
63、未来可能的走步，对弈的结果要么是一方赢（另一方输），要么是和局。对于对弈的结果要么是一方赢（另一方输），要么是和局。对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。博弈树类似于状描述，并通过博弈树搜索策略寻找最佳解。博弈树类似于状态图和问题求解搜索中使用的搜索树。搜索树上的第一个结态图和问题求解搜索中使用的搜索树。搜索树上的第一个结点对应一个棋局，树的分支表示棋的走步，根结点表示棋局点对应一个棋局，树的分支表示棋的走步，根结点表示棋局的开始，叶节点表示棋局的结束。的开始，叶节点表示棋局的结束。 一
64、个棋局的结果可以是赢、输或者和局。对于一个一个棋局的结果可以是赢、输或者和局。对于一个思考缜密的棋局来说，其博弈树是非常大的，就国际思考缜密的棋局来说，其博弈树是非常大的，就国际象棋来说，有象棋来说，有1012010120个结点（棋局总数），而对中国个结点（棋局总数），而对中国象棋来说，估计有象棋来说，估计有1016010160个结点，围棋更复杂，盘面个结点，围棋更复杂，盘面状态达状态达1076810768。计算机要装下如此大的博弈树，并在。计算机要装下如此大的博弈树，并在合理的时间内进行详细的搜索是不可能的。因此，如合理的时间内进行详细的搜索是不可能的。因此，如何将搜索树修改到一个合理的范围，是一个值得研究何将搜索树修改到一个合理的范围，是一个值得研究的问题，的问题，“深蓝深蓝”就是这类研究的成果之一。就是这类研究的成果之一。
