《计算机领域典型问题》由会员分享，可在线阅读，更多相关《计算机领域典型问题（55页珍藏版）》请在金锄头文库上搜索。
1、补充知识 计算机领域典型问题,在人类社会的发展过程中，人们提出过许多具有深远意义的科学问题，其中对计算机学科一些分支领域的形成和发展起了重要的作用。另外，在计算机学科的发展过程中，为了便于对计算机科学中有关问题和概念的本质的理解，人们还给出了不少反映该学科某一方面本质特征的典型实例，在这里一并归于计算机学科的典型问题。计算机学科典型问题的提出及研究，不仅有助于我们深刻地理解计算机学科，而且还对学科的发展有着十分重要的推动作用。,下面分别对图论中有代表性的哥尼斯堡七桥问题，算法与算法复杂性领域中有代表性的汉诺（Hanoi ）塔问题，算法复杂性中的难解性问题，证比求易算法，旅行商问题与组合爆炸问题
2、，哲学家共餐问题,图灵测试问题，博弈问题等问题及其相关内容进行分析。,补充知识 计算机领域典型问题,1歌尼斯堡七桥问题与哈密尔顿回路问题 2汉诺塔问题 3算法复杂性中的难解性问题 4哲学家共餐问题 5旅行商问题 6图灵测试问题 7搏弈问题,1 歌尼斯堡七桥问题与哈密尔顿回路问题,18世纪中叶，当时东普鲁士有一座哥尼斯堡（Konigsberg）城，城中有一条贯穿全市的普雷格尔（Pregol）河，河中央有座小岛，叫奈佛夫（Kneiphof）岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来。,图1 哥尼斯堡七桥地理位置示意图,当时该城
3、市的人们热衷一个难题：一个人怎样不重复地走完七桥，最后回到出发地点？即寻找走遍这7座桥，且只许走过每座桥一次，最后又回到原出发点的路径。试验者都没有解决这个难题。1736年，瑞士数学家列昂纳德欧拉（L.Euler）发表图论的首篇论文，论证了该问题无解，即从一点出发不重复地走遍七桥，最后又回到原来出发点是不可能的。他论证所用的图为图2所示。后人为了纪念数学家欧拉，将这个难题称为“哥尼斯堡七桥问题”。,图2 哥尼斯堡七桥问题示意图,为了解决哥尼斯堡七桥问题，欧拉用4个字母A、B、C、D代表4个城区，并用7条线表示7座桥，如图2所示。在图中，只有4个点和7条线，这样做是基于该问题本质的考虑，抽象出问
4、题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象成为一个数学问题，即经过图中每边一次且仅一次的回路问题了。欧拉在论文中论证了这样的回路是不存在的，后来，人们把有这样回路的图称为欧拉图。,将其有经过所有边的简单生成回路的图称为欧拉图 欧拉不仅给出了哥尼斯堡七桥问题的证明，还将问题进行了一般化处理，即对给定的任意一个河道图与任意多座桥，判定可能不可能每座桥恰好走过一次，并用数学方法给出了3条判定规则：,（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的； （2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线； （3）如果没有一个地方
5、是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。,欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。,在图论中除了欧拉回路以外，还有一个著名的“哈密尔顿回路问题”。十九世纪爱尔兰数学家哈密尔顿(Hamilton)发明了一种叫做周游世界的数学游戏。它的玩法是：给你一个正十二面体，它有二十个顶点，把每个顶点看做一个城市，把正十二面体的三十条棱看成连接这些城市的路。请你找一条从某城市出发，经过每个
6、城市恰好一次，并且最后回到出发点的路线。我们把正十二面体投影到平面上，在图3中标出了一种走法，即从城市1出发，经过2，3，20，最后回到1。,“哈密尔顿回路问题”与“欧拉回路问题”看上去十分相似，然而又是完全不同的两个问题。“哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。,2汉诺塔问题,传说在古代印度的贝拿勒斯神庙里安放了一块黄铜座，座上竖有三根宝石柱子。在第一根宝石柱上，按照从小到大、自上而下的顺序放有64个直径大小不一的金盘子，形成一座金塔，如
7、图44所示，即所谓的汉诺塔（又称梵天塔）。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下3条规则：,（1）每次只能移动一个盘子；（2）盘子只能在三根柱子上来回移动，不能放在他处；（3）在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。图4汉诺塔问题示意图64个盘子63个盘子据说当这64个盘子全部移到第三根柱子上后，世界末日就要到了。这就是著名的汉诺塔塔问题。,图4汉诺塔问题示意图,用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，经过调试和运行，从而完成
8、该问题的求解。从实际问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题主要的、本质的内容，最终实现对该问题的正确认识。,汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算机学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。,根据递归方法，我们可以将64个盘子的汉诺塔问题转化为求解63个盘子的汉诺塔问题，如果63个盘子的汉诺塔问题能够解决，则可以将63个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将63个盘子从第二个柱子移动到第三个柱子上。,如图4所示，则可以解决
9、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,因此，要完成汉诺塔的搬迁，
10、需要移动盘子的次数为：264-1=18446744073709551615 如果每秒移动一次，一年有31536000秒，则僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。,3算法复杂性中的难解性问题,算法分析是计算机科学的一项主要工作。为了进行算法比较，我们必须给出算法效率的某种衡量标准。 假设M是一种算法，并设n为输入数据的规模。实施M所占用的时间和空间是衡量该算法效率的两个主要指标。时间由“操作”次数衡量。比如，对于排序和查找，我们对比较次数计数。空间由实施该算法所需的最大内存来衡量。,算法M的复
11、杂性是一个函数(n)，它对于输人数据的规模n给出运行该算法所需时间与所需存储空间。执行一个算法所需存储空间通常就是数据规模的倍数。因此，除非特殊情况，“复杂性”将指运行算法的时间。,对于时间复杂性函数(n)。它通常不仅仅与输入数据的规模有关，还与特定的数据有关。例如，在一篇英文短文中查找第一次出现的3个字母的单词W。那么，如果W为定冠词“the”，则W很可能在短文的开头部分出现，于是(n)值将会比较小；如果W是单词“axe，”，则W甚至可能不会在短文中出现，所以(n)可能会很大。,因此，考虑对于适当的情况，求出复杂性函数(n)。在复杂性理论中研究得最多的两种情况是：(1)最坏情况 对于任何可能
12、的输入，(n)的最大值。(2)平均情况 (n)的期望值。,假定M是一个算法，并设n为输入数据的大小。显然M的复杂性(n)随着n的增大而增大。通常我们需要考察的是(n)的增长率，这常常由(n)与某标准函数相比较而得，例如log2n n， n log2n， n2， n3， 2n 等等，都可被用作为标准函数，这些函数是按其增长率列出的：对数函数log2n增长最慢，指数函数2n增长最快，而多项式函数nc的增长率随其指数c的增大而变快。,将复杂性函数与一个标准函数相比较的一种方法是利用“大O”记号，我们给出它的定义：设(x)与g(x)为定义于R或R的子集上的任意两个函数。我们说“(x)与g(x)同阶”，
13、记作(x)O(g(g)。,如果存在实数k和正常数C使得对于所有的xk有|(x)| C |g(x)|。 如 n2+n+1=O(n2)，该表达式表示，当n足够大时表达式左边约等于n2。 常见的大O表示形式有：O(1)称为常数级；O(logn)称为对数级；O(n)称为线性级；,O(nc)称为多项式级；O(cn)称为指数级；O(n!)称为阶乘级。用以上表示方法，在汉诺塔问题中，需要移动的盘子次数为h(n)= 2n-1，则该问题的算法时间复杂度表示为O(2n)。,一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是在计
14、算复杂性中，将这一类问题称为难解性问题。为了更好地理解计算及其复杂性的有关概念，我国学者洪加威曾经讲了一个被人称为“证比求易算法”的童话，用来帮助读者理解计算复杂性的有关概念，具体内容如下。,很久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有名的数学家孔唤石当宰相。邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，便亲自登门求婚。公主说：“你如果向我求婚，请你先求出48 770 428 433 377 171的一个真因子，一天之内交卷。” 艾述听罢，心中暗喜，心想：我从2开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？,艾述国王十分精于计算，
15、他一秒钟就算完一个数。可是，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。,公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了”。国王立即回国，召见宰相孔唤石，大数学家在仔细地思考后认为这个数为17位，如果这个数可以分成两个真因子的乘积，则最小的一个真因子不会超过9位。于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，
16、赏黄金万两。,于是，国王发动全国上下的民众，再度求婚，终于取得成功。在“证比求易算法”的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后来由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。,当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。下面，用阿达尔（G.Amdahl）定律来说明这个问题。,设f为求解某个问题的计算中存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，Sp为并行计算机系统最大的加速能力（单位：倍），则,设f=1%，p，则Sp=100。这说明即使在并行计算机系统中有无穷多个处理器，解决这个串行执行操作仅占全部操作1%的问题，其解题速度与单处理器的计算机相比最多也只能提高一百倍。因此，对难解性问题而言，单纯的提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。,
