计算机领域典型问题.ppt

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