计算机科学典型问题示例

计算机科学典型问题示例计算机科学典型问题示例•哥尼斯堡七桥问题寻找走遍这7座桥且只许走过每座桥一次，最后又回到原出发点的路径计算机科学典型问题示例•哥尼斯堡七桥问题•两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，把它们看作是4个点；•7座桥是7条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，任意画7条线来表示它们。欧拉将七桥问题抽象成了一个“一笔画”问题。怎样不重复地通过7座桥，变成了怎样不重复地画出一个几何图形的问题。原先，人们是要求找出一条不重复的路线，欧拉接下来着手判断：这种不重复的路线究竟存在不存在？由于这么改变了一下提问的角度，欧拉抓住了问题的实质。欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：每当你用笔画一条线进入中间的一个点时，你还必须画一条线离开这个点。否则，整个图形就不可能用一笔画出。也就是说，单独考察图中的任何一个点（除起点和终点外），它都应该与偶数条线相连；如果起点与终点重合，那么，连这个点也应该与偶数条线相连。计算机科学典型问题示例•哥尼斯堡七桥问题计算机科学典型问题示例•哥尼斯堡七桥问题结论（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的；（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线；（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。•欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。汉诺塔问题1）每次只能移动一个盘子；2）盘子只能在三根柱子上来回移动不能放在他处；3）在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。•用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，经过调试和运行，从而完成该问题的求解。从实际问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题主要的、本质的内容，最终实现对该问题的正确认识。•汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算机学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。•根据递归方法，我们可以将64个盘子的汉诺塔问题转化为求解63个盘子的汉诺塔问题，如果63个盘子的汉诺塔问题能够解决，则可以将63个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将63个盘子从第二个柱子移动到第三个柱子上。汉诺塔问题示意图•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年的时间。证比求易算法问题算法分析是计算机科学的一项主要工作。为了进行算法比较，我们必须给出算法效率的某种衡量标准。很久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有名的数学家孔唤石当宰相。邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，便亲自登门求婚。公主说：“你如果向我求婚，请你先求出48770428433377171的一个真因子，一天之内交卷。”艾述听罢，心中暗喜，心想：我从2开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？艾述国王十分精于计算，他一秒钟就算完一个数。可是，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223092827是它的一个真因子。国王很快就验证了这个数确能除尽48770428433377171。公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了”。国王立即回国，召见宰相孔唤石，大数学家在仔细地思考后认为这个数为17位，如果这个数可以分成两个真因子的乘积，则最小的一个真因子不会超过9位。于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏黄金万两。于是，国王发动全国上下的民众，再度求婚，终于取得成功。在“证比求易算法”的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后来由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。国王有众多百姓的帮助，求亲成功是自然的事。但是，如果换成是一个贫民百姓的小伙子去求婚，那就困难了。不过，小伙子可以从国王求亲取得成功所采用的并行算法中得到一个启发，那就是：他可以随便猜一个数，然后验证这个数。当然，这样做成功的可能性很小，不过，万一小伙子运气好猜着了呢？由于一个数和它的因子之间存在一些有规律的联系，因此，数论知识水平较高的人猜中的可能性就大。在算法计算复杂性的研究中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题，由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，确定性算法是非确定性算法的一个特例，因此P⊂NP。对于大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于NP类问题。现在计算机科学研究中一个悬而未决的重要问题是P=?NP。到目前为止，已经发现了一批可计算但有相当难度的问题是属于NP类问题，并且常通过证明一个问题与已知属于NP类中的某个问题等价，将其归入NP类问题。计算机科学典型问题示例•哲学家共餐问题哲学家的生活进程1.思考问题2.饿了停止思考，左手拿一支筷子（拿不到就等）3.右手拿一支筷子（拿不到就等）4.进餐5.放右手筷子6.放左手筷子7.重新回到思考问题的状态1哲学家的生活进程的极端情况：1.当所有哲学家都同时拿起左手筷子时，则所有哲学家都拿不到右手的筷子，并处于等待状态，则哲学家将都无法进餐，最终饿死；2.改变进程，如拿不到右手筷子则放下左手筷子。在某一瞬可能所有的哲学家都拿起左手的筷子，因拿不到右手的筷子又都同时放下左手的筷子，如此下去，所有的哲学家同样无法进餐。哲学家进餐问题在计算机科学中所反映的问题：•程序并发执行时进程同步的问题：死锁（Deadlock）和饥饿（Starvation）•为了提高系统的处理能力和机器的利用率，并法程序被广泛地使用，因此必须彻底解决并发进程中的死锁和饥饿问题DeadlockStarvationStarvationStarvation旅行商问题•旅行商问题（TravelingSalesmanProblem，简称TSP）是威廉·哈密尔顿（W.R.Hamilton）爵士和英国数学家克克曼（T.P.Kirkman）于19世纪初提出的一个数学问题。这是一个典型的NP完全性问题。其大意是：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。人们在考虑解决这个问题时，一般首先想到的最原始的一种方法是：列出每一条可供选择的路线（即对给定的城市进行排列组合），计算出每条路线的总里程，最后从中选出一条最短的路线。假设现在给定的4个城市分别为A、B、C和D，各城市之间的距离为已知数，如图a、图b所示。从图中可以看到，可供选择的路线共有6条，从中很快可以选出一条总距离最短的路线。ABCD256424图a城市交通图A265BCD244442BDCCBD224444ACCBDBD522665图b组合路径图设城市数目为n时，那么组合路径数则为（n-1）！。很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。假设现在城市的数目增为20个，组合路径数则为（20-1）！≈1.216×1017，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。图灵测试问题•在计算机学科诞生后，为解决人工智能中一些激烈争论的问题，图灵和西尔勒又分别提出了能反映人工智能本质特征的两个著名的哲学问题，即“图灵测试”和西尔勒的“中文屋子”，沿着图灵等人对“智能”的理解，人们在人工智能领域取得了长足的进展，其中“深蓝（DeepBlue）”战胜国际象棋大师卡斯帕罗夫（G.Kasparov）就是一个很好的例证。•图灵于1950年在英国《Mind》杂志上发表了《ComputingMachineryandIntelligence》一文，文中提出了“机器能思维吗？”这样一个问题，并给出了一个被后人称之为“图灵测试（TuringTest）”的模仿游戏。•这个游戏由3个人来完成：一个男人（A），一个女人（B），一个性别不限的提问者（C）。提问者（C）呆在与其他两个游戏者相隔离的房间里。游戏的目标是让提问者通过对其他两人的提问来鉴别其中哪个是男人，哪个是女人。为了避免提问者通过他们的声音、语调轻易地作出判断，最好是在提问者和两游戏者之间通过一台电传打字机来进行沟通。提问者只被告知两个人的代号为X和Y，游戏的最后他要作出“X是A，Y是B”或“X是B，Y是A”的判断。现在，把上面这个游戏中的男人（A）换成一部机器来扮演，如果提问者在与机器、女人的游戏中作出的错误判断与在男人、女人之间的游戏中作出错误判断的次数是相同的，那么，就可以判定这部机器是能够思维的。图灵关于“图灵测试”的论文发表后引发了很多的争论，以后的学者在讨论机器思维时大多都要谈到这个游戏。•“图灵测试”只是从功能的角度来判定机器是否能思维，也就是从行为主义角度来对“机器思维”进行定义。尽管图灵对“机器思维”的定义是不够严谨的，但他关于“机器思维”定义的开创性工作对后人的研究具有重要意义，因此，一些学者认为，图灵发表的关于“图灵测试”的论文标志着现代机器思维问题讨论的开始。•根据图灵的预测，到2000年，此类机器能通过测试。现在，在某些特定的领域，如博弈领域，“图灵测试”已取得了成功，1997年，IBM公司研制的计算机“深蓝”就战胜了国际象棋冠军卡斯帕罗夫。•在未来，如果我们能像图灵揭示计算本质那样揭示人类思维的本质，即“能行”思维，那么制造真正思维机器的日子也就不长了。可惜要对人类思维的本质进行描述，还是相当遥远的事情。搏弈问题•博弈问题属于人工智能中一个重要的研究领域。从狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质的游戏；从广义上讲，博弈就是对策或斗智。计算机中的博弈问题，一直是人工智能领域研究的重点内容之一。•1913年，数学家策墨洛（E.Zermelo）在第五届国际数学会议上发表了《关于集合论在象棋博弈理论中的应用》（OnanApplicationof