计算机科学典型问题示例精选PPT.ppt

计算机科学典型问题示例计算机科学典型问题示例第1页，此课件共47页哦计算机科学典型问题示例计算机科学典型问题示例 哥尼斯堡七桥问题哥尼斯堡七桥问题 寻找走遍这寻找走遍这7 7座桥且只许走过每座桥一次，最后又回座桥且只许走过每座桥一次，最后又回到原出发点的路径到原出发点的路径 第2页，此课件共47页哦计算机科学典型问题示例计算机科学典型问题示例 哥尼斯堡七桥问题哥尼斯堡七桥问题 两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，把它们看作是形状均与问题本身无关。因此，把它们看作是4 4个点；个点；7 7座桥是座桥是7 7条必须经过的路线，它们的长短、曲直，也与问题本身无关。条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，任意画因此，任意画7 7条线来表示它们。条线来表示它们。第3页，此课件共47页哦欧欧拉拉将将七七桥桥问问题题抽抽象象成成了了一一个个“一一笔笔画画”问问题题。怎怎样样不不重重复复地地通通过过7 7座座桥桥，变变成成了了怎怎样样不不重重复复地地画出一个几何图形的问题。画出一个几何图形的问题。原原先先，人人们们是是要要求求找找出出一一条条不不重重复复的的路路线线，欧欧拉拉接接下下来来着着手手判判断断：这这种种不不重重复复的的路路线线究究竟竟存存在在不不存在？由于这么改变了一下提问的角度，欧拉抓住了问题的实质。存在？由于这么改变了一下提问的角度，欧拉抓住了问题的实质。欧欧拉拉发发现现，凡凡是是能能用用一一笔笔画画成成的的图图形形，都都有有这这样样一一个个特特点点：每每当当你你用用笔笔画画一一条条线线进进入入中中间间的的一一个个点点时时，你你还还必必须须画画一一条条线线离离开开这这个个点点。否否则则，整整个个图图形形就就不不可可能能用用一一笔笔画画出出。也也就就是是说说，单单独独考考察察图图中中的的任任何何一一个个点点（除除起起点点和和终终点点外外），它它都都应应该该与与偶偶数数条条线线相相连连；如如果果起点与终点重合，那么，连这个点也应该与偶数条线相连。起点与终点重合，那么，连这个点也应该与偶数条线相连。计算机科学典型问题示例 哥尼斯堡七桥问题 第4页，此课件共47页哦计算机科学典型问题示例 哥尼斯堡七桥问题 结论结论（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的；（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线；（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。第5页，此课件共47页哦欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。本身也得到了充分的发展。第6页，此课件共47页哦汉诺塔问题1 1）每每次次只只能能移移动动一一个个盘盘子子；2 2）盘盘子子只只能能在在三三根根柱柱子子上上来来回回移移动动不不能能放放在在他他处处 ；3 3）在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上 天神说，当这天神说，当这6464个盘子全部移到第三根柱子上后，世界末日就要到了。个盘子全部移到第三根柱子上后，世界末日就要到了。第7页，此课件共47页哦用计算机求解一个实际问题，首先要从这个实际问题中抽象出一用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，经过调试和运行，从而完成该问题的求解。从实际问编写程序，经过调试和运行，从而完成该问题的求解。从实际问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题主要的、本质的内容，最终实现对该问题的正确认识。题主要的、本质的内容，最终实现对该问题的正确认识。第8页，此课件共47页哦汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算机学科中的一个重要概念。所谓递归，就是将一个较大的问题归机学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。而这些子问题比原问题简单，约为一个或多个子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。且在结构上与原问题相同。第9页，此课件共47页哦根据递归方法，我们可以将根据递归方法，我们可以将6464个盘子的汉诺塔问题转化为求解个盘子的汉诺塔问题转化为求解6363个盘子的汉诺塔问题，如果个盘子的汉诺塔问题，如果6363个盘子的汉诺塔问题能够解决，则个盘子的汉诺塔问题能够解决，则可以将可以将6363个盘子先移动到第二个柱子上，再将最后一个盘子直接个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将移动到第三个柱子上，最后又一次将6363个盘子从第二个柱子移动个盘子从第二个柱子移动到第三个柱子上。到第三个柱子上。第10页，此课件共47页哦汉诺塔问题示意图汉诺塔问题示意图第11页，此课件共47页哦6363个盘子的汉诺塔求解问题可以转化为个盘子的汉诺塔求解问题可以转化为6262个盘子的汉诺塔求解问个盘子的汉诺塔求解问题，题，6262个盘子的汉诺塔求解问题又可以转化为个盘子的汉诺塔求解问题又可以转化为6161个盘子的汉诺塔个盘子的汉诺塔求解问题，直到求解问题，直到1 1个盘子的汉诺塔求解问题。再由个盘子的汉诺塔求解问题。再由1 1个盘子的汉诺个盘子的汉诺塔的解求出塔的解求出2 2个盘子的汉诺塔，直到解出个盘子的汉诺塔，直到解出6464个盘子的汉诺塔问题。个盘子的汉诺塔问题。第12页，此课件共47页哦按照上面的算法，按照上面的算法，n n个盘子的汉诺塔问题需要移动的盘子数是个盘子的汉诺塔问题需要移动的盘子数是n n-1-1个盘子的汉诺塔问题需个盘子的汉诺塔问题需要移动的盘子数的要移动的盘子数的2 2倍加倍加1 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第13页，此课件共47页哦 因此，要完成汉诺塔的搬迁，需要移动盘子的次数为：因此，要完成汉诺塔的搬迁，需要移动盘子的次数为：2 26464-1=18446744073709551615-1=18446744073709551615 如果每秒移动一次，一年有如果每秒移动一次，一年有3153600031536000秒，则僧侣们一刻不停地来回秒，则僧侣们一刻不停地来回搬动，也需要花费大约搬动，也需要花费大约58495849亿年的时间。假定计算机以每秒亿年的时间。假定计算机以每秒10001000万万个盘子的速度进行搬迁，则需要花费大约个盘子的速度进行搬迁，则需要花费大约5849058490年的时间。年的时间。第14页，此课件共47页哦证比求易算法问题证比求易算法问题 算法分析是计算机科学的一项主要工作。为了进行算法比较，我们必须给出算法效率的某种衡量标准。第15页，此课件共47页哦很久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有很久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有名的数学家孔唤石当宰相。名的数学家孔唤石当宰相。邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，便亲自登门求婚。便亲自登门求婚。公主说：公主说：“你如果向我求婚，请你先求出你如果向我求婚，请你先求出48 770 428 433 377 17148 770 428 433 377 171的一个真因子，一的一个真因子，一天之内交卷。天之内交卷。”艾述听罢，心中暗喜，心想：我从艾述听罢，心中暗喜，心想：我从2 2开始，一个一个地试，看看能不开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？能除尽这个数，还怕找不到这个真因子吗？第16页，此课件共47页哦艾述国王十分精于计算，他一秒钟就算完一个数。可是，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。第17页，此课件共47页哦公主说：公主说：“我再给你一次机会，如果还求不出，将来你只好我再给你一次机会，如果还求不出，将来你只好做我的证婚人了做我的证婚人了”。国王立即回国，召见宰相孔唤石，大数学家。国王立即回国，召见宰相孔唤石，大数学家在仔细地思考后认为这个数为在仔细地思考后认为这个数为1717位，如果这个数可以分成两个真位，如果这个数可以分成两个真因子的乘积，则最小的一个真因子不会超过因子的乘积，则最小的一个真因子不会超过9 9位。于是他给国王出位。于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏黄金万两。自己的编号去除这个数，除尽了立即上报，赏黄金万两。第18页，此课件共47页哦于是，国王发动全国上下的民众，再度求婚，终于取得成功。于是，国王发动全国上下的民众，再度求婚，终于取得成功。在在“证比求易算法证比求易算法”的故事中，国王最先使用的是一种顺序算的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后来由宰相提出的是一种并行算法，其复杂性表现在时间方面，后来由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。从而解决难解性问题，其实这是一种误解。第19页，此课件共47页哦国王有众多百姓的帮助，求亲成功是自然的事。但是，如果国王有众多百姓的帮助，求亲成功是自然的事。但是，如果换成是一个贫民百姓的小伙子去求婚，那就困难了。不过，小伙换成是一个贫民百姓的小伙子去求婚，那就困难了。不过，小伙子可以从国王求亲取得成功所采用的并行算法中得到一个启发，子可以从国王求亲取得成功所采用的并行算法中得到一个启发，那就是：他可以随便猜一个数，然后验证这个数。当然，这样做那就是：他可以随便猜一个数，然后验证这个数。当然，这样做成功的可能性很小，不过，万一小伙子运气好猜着了呢？由于一成功的可能性很小，不过，万一小伙子运气好猜着了呢？由于一个数和它的因子之间存在一些有规律的联系，因此，数论知识水个数和它的因子之间存在一些有规律的联系，因此，数论知识水平较高的人猜中的可能性就大。平较高的人猜中的可能性就大。第20页，此课件共47页哦在算法计算复杂性的研究中，将所有可以在多项式时间内求在算法计算复杂性的研究中，将所有可以在多项式时间内求解的问题称为解的问题称为P P类问题，而将所有在多项式时间内可以验证的问题类问题，而将所有在多项式时间内可以验证的问题称为称为NPNP类问题，由于类问题，由于P P类问题采用的是确定性算法，类问题采用的是确定性算法，NPNP类问题采用类问题采用的是非确定性算法，确定性算法是非确定性算法的一个特例，因的是非确定性算法，确定性算法是非确定性算法的一个特例，因此此P P NPNP。第21页，此课件共47页哦对于大多数实际问题来说，找到一个解可能很难，检验一个对于大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于解常常比较容易，所以都属于NPNP类问题。现在计算机科学研究中类问题。现在计算机科学研究中一个悬而未决的重要问题是一个悬而未决的重要问题是P=?NPP=?NP。到目前为止，已经发现了一批。到目前为止，已经发现了一批可计算但有相当难度的问题是属于可计算但有相当难度的问题是属于NPNP类问题，并且常通过证明一类问题，并且常通过证明一个问题与已知属于个问题与已知属于NPNP类中的某个问题等价，将其归入类中的某个问题等价，将其归入NPNP类问题。类问题。第22页，此课件共47页哦计算机科学典型问题示例计算机科学典型问题示例 哲学家共餐问题哲学家共餐问题 第23页，此课件共47页哦哲学家的生活进程哲学家的生活进程1.1.思考问题思考问题2.2.饿了停止思考，左手拿一支筷子（拿不到就等）饿了停止思考，左手拿一支筷子（拿不到就等）3.3.右手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等）4.4.进餐进餐5.5.放右手筷子放右手筷子6.6.放左手筷子放左手筷子7.7.重新回到思考问题的状态重新回到思考问题的状态1 1第24页，此课件共47页哦哲学家的生活进程的极端情况：哲学家的生活进程的极端情况：1.当所有哲学家都同时拿起左手筷子时，则所有哲学家都拿不到右手的筷子，并当所有哲学家都同时拿起左手筷子时，则所有哲学家都拿不到右手的筷子，并处于等待状态，则哲学家将都无法进餐，最终饿死；处于等待状态，则哲学家将都无法进餐，最终饿死；2.改变进程，如拿不到右手筷子则放下左手筷子。在某一瞬可能所有的哲学家都改变进程，如拿不到右手筷子则放下左手筷子。在某一瞬可能所有的哲学家都拿起左手的筷子，因拿不到右手的筷子又都同时放下左手的筷子，如此下去，拿起左手的筷子，因拿不到右手的筷子又都同时放下左手的筷子，如此下去，所有的哲学家同样无法进餐。所有的哲学家同样无法进餐。哲学家进餐问题在计算机科学中所反映的问题：程序并发执行时进程同步的问题：死锁（Deadlock）和饥饿（Starvation）为了提高系统的处理能力和机器的利用率，并法程序被广泛地使用，因此必须彻底解决并发进程中的死锁和饥饿问题第25页，此课件共47页哦 Deadlock第26页，此课件共47页哦Starvation第27页，此课件共47页哦Starvation第28页，此课件共47页哦Starvation第29页，此课件共47页哦旅行商问题旅行商问题旅行商问题（旅行商问题（Traveling Salesman ProblemTraveling Salesman Problem，简称，简称TSPTSP）是威廉）是威廉哈哈密尔顿（密尔顿（W.R.HamiltonW.R.Hamilton）爵士和英国数学家克克曼（）爵士和英国数学家克克曼（T.P.KirkmanT.P.Kirkman）于于1919世纪初提出的一个数学问题。这是一个典型的世纪初提出的一个数学问题。这是一个典型的NPNP完全性问题。其完全性问题。其大意是：有若干个城市，任何两个城市之间的距离都是确定的，现要大意是：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。使其旅行的费用最少。第30页，此课件共47页哦人们在考虑解决这个问题时，一般首先想到的最原始的一种人们在考虑解决这个问题时，一般首先想到的最原始的一种方法是：列出每一条可供选择的路线（即对给定的城市进行排列方法是：列出每一条可供选择的路线（即对给定的城市进行排列组合），计算出每条路线的总里程，最后从中选出一条最短的路组合），计算出每条路线的总里程，最后从中选出一条最短的路线。假设现在给定的线。假设现在给定的4 4个城市分别为个城市分别为A A、B B、C C和和D D，各城市之间的距，各城市之间的距离为已知数，如图离为已知数，如图a a、图、图b b所示。从图中可以看到，可供选择的路所示。从图中可以看到，可供选择的路线共有线共有6 6条，从中很快可以选出一条总距离最短的路线。条，从中很快可以选出一条总距离最短的路线。第31页，此课件共47页哦ABCD256424图图a a 城市交通图城市交通图A265BCD244442BDCCBD224444ACCBDBD522665图图b b 组合路径图组合路径图第32页，此课件共47页哦设城市数目为设城市数目为n n时，那么组合路径数则为（时，那么组合路径数则为（n n-1-1）！。很显然，）！。很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级急剧增长，以至达到无法目的不断增大，组合路线数将呈指数级急剧增长，以至达到无法计算的地步，这就是所谓的计算的地步，这就是所谓的“组合爆炸问题组合爆炸问题”。假设现在城市的。假设现在城市的数目增为数目增为2020个，组合路径数则为（个，组合路径数则为（20-120-1）！）！1.216101.216101717，如此，如此庞大的组合数目，若计算机以每秒检索庞大的组合数目，若计算机以每秒检索10001000万条路线的速度计算，万条路线的速度计算，也需要花上也需要花上386386年的时间。年的时间。第33页，此课件共47页哦 图灵测试问题 在计算机学科诞生后，为解决人工智能中一些激烈争论的问题，图在计算机学科诞生后，为解决人工智能中一些激烈争论的问题，图灵和西尔勒又分别提出了能反映人工智能本质特征的两个著名的哲学灵和西尔勒又分别提出了能反映人工智能本质特征的两个著名的哲学问题，即问题，即“图灵测试图灵测试”和西尔勒的和西尔勒的“中文屋子中文屋子”，沿着图灵等人对，沿着图灵等人对“智能智能”的理解，人们在人工智能领域取得了长足的进展，其中的理解，人们在人工智能领域取得了长足的进展，其中“深蓝深蓝（Deep BlueDeep Blue）”战胜国际象棋大师卡斯帕罗夫（战胜国际象棋大师卡斯帕罗夫（G.KasparovG.Kasparov）就是一）就是一个很好的例证。个很好的例证。第34页，此课件共47页哦 图灵于图灵于19501950年在英国年在英国 MindMind杂志上发表了杂志上发表了ComputingComputing Machinery and IntelligenceMachinery and Intelligence一文，文中提出了一文，文中提出了“机器能思机器能思维吗？维吗？”这样一个问题，并给出了一个被后人称之为这样一个问题，并给出了一个被后人称之为“图灵测图灵测试（试（Turing TestTuring Test）”的模仿游戏。的模仿游戏。第35页，此课件共47页哦 这个游戏由这个游戏由3 3个人来完成：一个男人（个人来完成：一个男人（A A），一个女人（），一个女人（B B），），一个性别不限的提问者（一个性别不限的提问者（C C）。提问者（）。提问者（C C）呆在与其他两个游）呆在与其他两个游戏者相隔离的房间里。游戏的目标是让提问者通过对其他两人戏者相隔离的房间里。游戏的目标是让提问者通过对其他两人的提问来鉴别其中哪个是男人，哪个是女人。为了避免提问者的提问来鉴别其中哪个是男人，哪个是女人。为了避免提问者通过他们的声音、语调轻易地作出判断，最好是在提问者和两通过他们的声音、语调轻易地作出判断，最好是在提问者和两游戏者之间通过一台电传打字机来进行沟通。提问者只被告知游戏者之间通过一台电传打字机来进行沟通。提问者只被告知两个人的代号为两个人的代号为X X和和Y Y，游戏的最后他要作出，游戏的最后他要作出“X“X是是A A，Y Y是是B”B”或或“X“X是是B B，Y Y是是A”A”的判断。的判断。第36页，此课件共47页哦 现在，把上面这个游戏中的男人（现在，把上面这个游戏中的男人（A A）换成一部机器来扮演，如）换成一部机器来扮演，如果提问者在与机器、女人的游戏中作出的错误判断与在男人、女果提问者在与机器、女人的游戏中作出的错误判断与在男人、女人之间的游戏中作出错误判断的次数是相同的，那么，就可以判人之间的游戏中作出错误判断的次数是相同的，那么，就可以判定这部机器是能够思维的。定这部机器是能够思维的。图灵关于图灵关于“图灵测试图灵测试”的论文发表后引发了很多的争论，的论文发表后引发了很多的争论，以后的学者在讨论机器思维时大多都要谈到这个游戏。以后的学者在讨论机器思维时大多都要谈到这个游戏。第37页，此课件共47页哦 “图灵测试图灵测试”只是从功能的角度来判定机器是否能思维，也就只是从功能的角度来判定机器是否能思维，也就是从行为主义角度来对是从行为主义角度来对“机器思维机器思维”进行定义。尽管图灵对进行定义。尽管图灵对“机器思维机器思维”的定义是不够严谨的，但他关于的定义是不够严谨的，但他关于“机器思维机器思维”定义定义的开创性工作对后人的研究具有重要意义，因此，一些学者认的开创性工作对后人的研究具有重要意义，因此，一些学者认为，图灵发表的关于为，图灵发表的关于“图灵测试图灵测试”的论文标志着现代机器思维的论文标志着现代机器思维问题讨论的开始。问题讨论的开始。第38页，此课件共47页哦 根据图灵的预测，到根据图灵的预测，到20002000年，此类机器能通过测试。现在，年，此类机器能通过测试。现在，在某些特定的领域，如博弈领域，在某些特定的领域，如博弈领域，“图灵测试图灵测试”已取得了成功，已取得了成功，19971997年，年，IBMIBM公司研制的计算机公司研制的计算机“深蓝深蓝”就战胜了国际象棋冠就战胜了国际象棋冠军卡斯帕罗夫。军卡斯帕罗夫。第39页，此课件共47页哦 在未来，如果我们能像图灵揭示计算本质那样揭示人类思维的在未来，如果我们能像图灵揭示计算本质那样揭示人类思维的本质，即本质，即“能行能行”思维，那么制造真正思维机器的日子也就不长思维，那么制造真正思维机器的日子也就不长了。可惜要对人类思维的本质进行描述，还是相当遥远的事情。了。可惜要对人类思维的本质进行描述，还是相当遥远的事情。第40页，此课件共47页哦 搏弈问题搏弈问题 博弈问题属于人工智能中一个重要的研究领域。从狭义博弈问题属于人工智能中一个重要的研究领域。从狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质的游戏；从广义上讲，博弈就是对策或斗智。计算机中的的游戏；从广义上讲，博弈就是对策或斗智。计算机中的博弈问题，一直是人工智能领域研究的重点内容之一。博弈问题，一直是人工智能领域研究的重点内容之一。第41页，此课件共47页哦 19131913年，数学家策墨洛（年，数学家策墨洛（E.ZermeloE.Zermelo）在第五届国际数学会议）在第五届国际数学会议上发表了关于集合论在象棋博弈理论中的应用（上发表了关于集合论在象棋博弈理论中的应用（On an On an Application of Set Theory to Game of ChessApplication of Set Theory to Game of Chess）的著名论文，）的著名论文，第一次把数学和象棋联系起来，从此，现代数学出现了一个新的第一次把数学和象棋联系起来，从此，现代数学出现了一个新的理论，即博弈论。理论，即博弈论。1950 1950年，年，“信息论信息论”创始人香农（创始人香农（A.ShannonA.Shannon）发表了国）发表了国际象棋与机器（际象棋与机器（A ChessA ChessPlaying MachinePlaying Machine）一文，并阐述了）一文，并阐述了用计算机编制下棋程序的可能性。用计算机编制下棋程序的可能性。第42页，此课件共47页哦 19561956年夏天，由麦卡锡（年夏天，由麦卡锡（J.McCarthyJ.McCarthy）和香农等人共同发起的，）和香农等人共同发起的，在美国达特茅斯（在美国达特茅斯（DartmouthDartmouth）大学举行的夏季学术讨论会上，第）大学举行的夏季学术讨论会上，第一次正式使用了一次正式使用了“人工智能人工智能”这一术语，该次会议的召开对人工智这一术语，该次会议的召开对人工智能的发展起到了极大的推动作用。能的发展起到了极大的推动作用。第43页，此课件共47页哦 当时，当时，IBMIBM公司的工程师塞缪尔（公司的工程师塞缪尔（A.SamuelA.Samuel）也被邀请参加了）也被邀请参加了“达特茅斯达特茅斯”会议，塞缪尔的研究专长正是电脑下棋。早在会议，塞缪尔的研究专长正是电脑下棋。早在19521952年，塞缪尔就运用博弈理论和状态空间搜索技术成功地研年，塞缪尔就运用博弈理论和状态空间搜索技术成功地研制了世界上第一个跳棋程序。该程序经不断地完善于制了世界上第一个跳棋程序。该程序经不断地完善于19591959年击年击败了它的设计者塞缪尔本人，败了它的设计者塞缪尔本人，19621962年，它又击败了美国一个州年，它又击败了美国一个州的冠军的冠军 。第44页，此课件共47页哦 19701970年开始，年开始，ACMACM每年举办一次计算机国际象棋锦标赛直到每年举办一次计算机国际象棋锦标赛直到19941994年（年（19921992年中断过一次），每年产生一个计算机国际象棋赛冠军，年中断过一次），每年产生一个计算机国际象棋赛冠军，19911991年，冠军年，冠军由由IBMIBM的的“深思深思（Deep ThoughtDeep Thought）”获得。获得。ACMACM的这些工作极大地推的这些工作极大地推动了博弈问题的深入研究，并促进了人工智能领域的发展。北京时间动了博弈问题的深入研究，并促进了人工智能领域的发展。北京时间19971997年年5 5月初，在美国纽约公平大厦，月初，在美国纽约公平大厦，“深蓝深蓝”与国际象棋冠军卡斯帕罗与国际象棋冠军卡斯帕罗夫交战，前者以两胜一负三平战胜后者。夫交战，前者以两胜一负三平战胜后者。第45页，此课件共47页哦 “深蓝深蓝”是美国是美国IBMIBM公司研制的一台高性能并行计算机，它由公司研制的一台高性能并行计算机，它由256256（32 node*832 node*8）个专为国际象棋比赛设计的微处理器组成，据）个专为国际象棋比赛设计的微处理器组成，据估计，该系统每秒可计算估计，该系统每秒可计算2 2亿步棋。亿步棋。“深蓝深蓝”的前身是的前身是“深思深思”，始建于，始建于19851985年。年。19891989年，卡斯帕罗夫首战年，卡斯帕罗夫首战“深思深思”，后者败北。，后者败北。19961996年，在年，在“深思深思”基础上研制出的基础上研制出的“深蓝深蓝”曾再次与卡斯帕罗曾再次与卡斯帕罗夫交战，并以夫交战，并以2 2：4 4负于对手。国际象棋、西洋跳棋与围棋、中国负于对手。国际象棋、西洋跳棋与围棋、中国象棋一样都属于双人完备博弈。象棋一样都属于双人完备博弈。第46页，此课件共47页哦 所谓双人完备博弈就是两位选手对垒，轮流走步，其中一方完全知道所谓双人完备博弈就是两位选手对垒，轮流走步，其中一方完全知道另一方已经走过的棋步以及未来可能的走步，对弈的结果要么是一方赢另一方已经走过的棋步以及未来可能的走步，对弈的结果要么是一方赢（另一方输），要么是和局。对于任何一种双人完备博弈，都可以用一（另一方输），要么是和局。对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。博弈个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。博弈树类似于状态图和问题求解搜索中使用的搜索树。搜索树上的第一个结树类似于状态图和问题求解搜索中使用的搜索树。搜索树上的第一个结点对应一个棋局，树的分支表示棋的走步，根结点表示棋局的开始，叶点对应一个棋局，树的分支表示棋的走步，根结点表示棋局的开始，叶节点表示棋局的结束。节点表示棋局的结束。第47页，此课件共47页哦