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

《计算机科学典型问题示例.ppt》由会员分享，可在线阅读，更多相关《计算机科学典型问题示例.ppt（48页珍藏版）》请在三一办公上搜索。

1、计算机科学典型问题示例,计算机科学典型问题示例,哥尼斯堡七桥问题,寻找走遍这7座桥且只许走过每座桥一次，最后又回到原出发点的路径,计算机科学典型问题示例,哥尼斯堡七桥问题,两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，把它们看作是4个点；7座桥是7条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，任意画7条线来表示它们。,欧拉将七桥问题抽象成了一个“一笔画”问题。怎样不重复地通过7座桥，变成了怎样不重复地画出一个几何图形的问题。原先，人们是要求找出一条不重复的路线，欧拉接下来着手判断：这种不重复的路线究竟存在不存在？由于这么改变了一下提问的角度，欧

2、拉抓住了问题的实质。欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：每当你用笔画一条线进入中间的一个点时，你还必须画一条线离开这个点。否则，整个图形就不可能用一笔画出。也就是说，单独考察图中的任何一个点（除起点和终点外），它都应该与偶数条线相连；如果起点与终点重合，那么，连这个点也应该与偶数条线相连。,计算机科学典型问题示例,哥尼斯堡七桥问题,计算机科学典型问题示例,哥尼斯堡七桥问题,结论（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的；（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线；（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的

3、路线都能实现。,欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。,汉诺塔问题,1）每次只能移动一个盘子；2）盘子只能在三根柱子上来回移动不能放在他处；3）在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上 天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。,用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，

4、经过调试和运行，从而完成该问题的求解。从实际问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题主要的、本质的内容，最终实现对该问题的正确认识。,汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算机学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。,根据递归方法，我们可以将64个盘子的汉诺塔问题转化为求解63个盘子的汉诺塔问题，如果63个盘子的汉诺塔问题能够解决，则可以将63个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将63个盘子从第二个柱子移动到第三个柱子上。

5、,汉诺塔问题示意图,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,因此，要完成汉诺塔的搬迁，需要移动盘子

6、的次数为：264 如果每秒移动一次，一年有31536000秒，则僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。,证比求易算法问题,算法分析是计算机科学的一项主要工作。为了进行算法比较，我们必须给出算法效率的某种衡量标准。,很久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有名的数学家孔唤石当宰相。邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，便亲自登门求婚。公主说：“你如果向我求婚，请你先求出48 770 428 433 377 171的一个真因子，一天之内交卷。

7、”艾述听罢，心中暗喜，心想：我从2开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？,艾述国王十分精于计算，他一秒钟就算完一个数。可是，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。,公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了”。国王立即回国，召见宰相孔唤石，大数学家在仔细地思考后认为这个数为17位，如果这个数可以分成两个真因子的乘积，则最小的一个真因子不会超过9位。于是他给国王出了一个主意：按自然数的顺序

8、给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏黄金万两。,于是，国王发动全国上下的民众，再度求婚，终于取得成功。在“证比求易算法”的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后来由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。,国王有众多百姓的帮助，求亲成功是自然的事。但是，如果换成是一个贫民百姓的小伙子去求婚，那就

9、困难了。不过，小伙子可以从国王求亲取得成功所采用的并行算法中得到一个启发，那就是：他可以随便猜一个数，然后验证这个数。当然，这样做成功的可能性很小，不过，万一小伙子运气好猜着了呢？由于一个数和它的因子之间存在一些有规律的联系，因此，数论知识水平较高的人猜中的可能性就大。,在算法计算复杂性的研究中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题，由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，确定性算法是非确定性算法的一个特例，因此PNP。,对于大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于NP类问题

10、。现在计算机科学研究中一个悬而未决的重要问题是P=?NP。到目前为止，已经发现了一批可计算但有相当难度的问题是属于NP类问题，并且常通过证明一个问题与已知属于NP类中的某个问题等价，将其归入NP类问题。,计算机科学典型问题示例,哲学家共餐问题,哲学家的生活进程思考问题饿了停止思考，左手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等）进餐放右手筷子放左手筷子重新回到思考问题的状态1,哲学家的生活进程的极端情况：当所有哲学家都同时拿起左手筷子时，则所有哲学家都拿不到右手的筷子，并处于等待状态，则哲学家将都无法进餐，最终饿死；改变进程，如拿不到右手筷子则放下左手筷子。在某一瞬可能所有的哲学家都拿

11、起左手的筷子，因拿不到右手的筷子又都同时放下左手的筷子，如此下去，所有的哲学家同样无法进餐。,哲学家进餐问题在计算机科学中所反映的问题：程序并发执行时进程同步的问题：死锁（Deadlock）和饥饿（Starvation）为了提高系统的处理能力和机器的利用率，并法程序被广泛地使用，因此必须彻底解决并发进程中的死锁和饥饿问题,Deadlock,Starvation,Starvation,Starvation,旅行商问题,旅行商问题（Traveling Salesman Problem，简称TSP）是威廉哈密尔顿（）爵士和英国数学家克克曼（）于19世纪初提出的一个数学问题。这是一个典型的NP完全性问

12、题。其大意是：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。,人们在考虑解决这个问题时，一般首先想到的最原始的一种方法是：列出每一条可供选择的路线（即对给定的城市进行排列组合），计算出每条路线的总里程，最后从中选出一条最短的路线。假设现在给定的4个城市分别为A、B、C和D，各城市之间的距离为已知数，如图a、图b所示。从图中可以看到，可供选择的路线共有6条，从中很快可以选出一条总距离最短的路线。,设城市数目为n时，那么组合路径数则为（n-1）！。很显然

13、，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。假设现在城市的数目增为20个，组合路径数则为（20-1）！1.2161017，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。,图灵测试问题,在计算机学科诞生后，为解决人工智能中一些激烈争论的问题，图灵和西尔勒又分别提出了能反映人工智能本质特征的两个著名的哲学问题，即“图灵测试”和西尔勒的“中文屋子”，沿着图灵等人对“智能”的理解，人们在人工智能领域取得了长足的进展，其中“深蓝（Deep Blue

14、）”战胜国际象棋大师卡斯帕罗夫（G.Kasparov）就是一个很好的例证。,图灵于1950年在英国 Mind杂志上发表了Computing Machinery and Intelligence一文，文中提出了“机器能思维吗？”这样一个问题，并给出了一个被后人称之为“图灵测试（Turing Test）”的模仿游戏。,这个游戏由3个人来完成：一个男人（A），一个女人（B），一个性别不限的提问者（C）。提问者（C）呆在与其他两个游戏者相隔离的房间里。游戏的目标是让提问者通过对其他两人的提问来鉴别其中哪个是男人，哪个是女人。为了避免提问者通过他们的声音、语调轻易地作出判断，最好是在提问者和两游戏者之间

15、通过一台电传打字机来进行沟通。提问者只被告知两个人的代号为X和Y，游戏的最后他要作出“X是A，Y是B”或“X是B，Y是A”的判断。,现在，把上面这个游戏中的男人（A）换成一部机器来扮演，如果提问者在与机器、女人的游戏中作出的错误判断与在男人、女人之间的游戏中作出错误判断的次数是相同的，那么，就可以判定这部机器是能够思维的。图灵关于“图灵测试”的论文发表后引发了很多的争论，以后的学者在讨论机器思维时大多都要谈到这个游戏。,“图灵测试”只是从功能的角度来判定机器是否能思维，也就是从行为主义角度来对“机器思维”进行定义。尽管图灵对“机器思维”的定义是不够严谨的，但他关于“机器思维”定义的开创性工作对

16、后人的研究具有重要意义，因此，一些学者认为，图灵发表的关于“图灵测试”的论文标志着现代机器思维问题讨论的开始。,根据图灵的预测，到2000年，此类机器能通过测试。现在，在某些特定的领域，如博弈领域，“图灵测试”已取得了成功，1997年，IBM公司研制的计算机“深蓝”就战胜了国际象棋冠军卡斯帕罗夫。,在未来，如果我们能像图灵揭示计算本质那样揭示人类思维的本质，即“能行”思维，那么制造真正思维机器的日子也就不长了。可惜要对人类思维的本质进行描述，还是相当遥远的事情。,搏弈问题,博弈问题属于人工智能中一个重要的研究领域。从狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质的游戏；从广义上讲，博弈

17、就是对策或斗智。计算机中的博弈问题，一直是人工智能领域研究的重点内容之一。,1913年，数学家策墨洛（E.Zermelo）在第五届国际数学会议上发表了关于集合论在象棋博弈理论中的应用（On an Application of Set Theory to Game of Chess）的著名论文，第一次把数学和象棋联系起来，从此，现代数学出现了一个新的理论，即博弈论。1950年，“信息论”创始人香农（A.Shannon）发表了国际象棋与机器（A ChessPlaying Machine）一文，并阐述了用计算机编制下棋程序的可能性。,1956年夏天，由麦卡锡（J.McCarthy）和香农等人共同发起

18、的，在美国达特茅斯（Dartmouth）大学举行的夏季学术讨论会上，第一次正式使用了“人工智能”这一术语，该次会议的召开对人工智能的发展起到了极大的推动作用。,当时，IBM公司的工程师塞缪尔（A.Samuel）也被邀请参加了“达特茅斯”会议，塞缪尔的研究专长正是电脑下棋。早在1952年，塞缪尔就运用博弈理论和状态空间搜索技术成功地研制了世界上第一个跳棋程序。该程序经不断地完善于1959年击败了它的设计者塞缪尔本人，1962年，它又击败了美国一个州的冠军。,1970年开始，ACM每年举办一次计算机国际象棋锦标赛直到1994年（1992年中断过一次），每年产生一个计算机国际象棋赛冠军，1991年，

19、冠军由IBM的“深思（Deep Thought）”获得。ACM的这些工作极大地推动了博弈问题的深入研究，并促进了人工智能领域的发展。北京时间1997年5月初，在美国纽约公平大厦，“深蓝”与国际象棋冠军卡斯帕罗夫交战，前者以两胜一负三平战胜后者。,“深蓝”是美国IBM公司研制的一台高性能并行计算机，它由256（32 node*8）个专为国际象棋比赛设计的微处理器组成，据估计，该系统每秒可计算2亿步棋。“深蓝”的前身是“深思”，始建于1985年。1989年，卡斯帕罗夫首战“深思”，后者败北。1996年，在“深思”基础上研制出的“深蓝”曾再次与卡斯帕罗夫交战，并以2：4负于对手。国际象棋、西洋跳棋与

20、围棋、中国象棋一样都属于双人完备博弈。,所谓双人完备博弈就是两位选手对垒，轮流走步，其中一方完全知道另一方已经走过的棋步以及未来可能的走步，对弈的结果要么是一方赢（另一方输），要么是和局。对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。博弈树类似于状态图和问题求解搜索中使用的搜索树。搜索树上的第一个结点对应一个棋局，树的分支表示棋的走步，根结点表示棋局的开始，叶节点表示棋局的结束。,一个棋局的结果可以是赢、输或者和局。对于一个思考缜密的棋局来说，其博弈树是非常大的，就国际象棋来说，有10120个结点（棋局总数），而对中国象棋来说，估计有10160个结点，围棋更复杂，盘面状态达10768。计算机要装下如此大的博弈树，并在合理的时间内进行详细的搜索是不可能的。因此，如何将搜索树修改到一个合理的范围，是一个值得研究的问题，“深蓝”就是这类研究的成果之一。,