第7章 计算机领域典型问题.ppt

第7章 计算机领域典型问题 在人类社会的发展过程中，人们提出过许多具有深远意义的科学问题，其中对计算机学科一些分支领域的形成和发展起了重要的作用。另外，在计算机学科的发展过程中，为了便于对计算机科学中有关问题和概念的本质的理解，人们还给出了不少反映该学科某一方面本质特征的典型实例，在这里一并归于计算机学科的典型问题。 计算机学科典型问题的提出及研究，不仅有助于我们深刻地理解计算机学科，而且还对学科的发展有着十分重要的推动作用。 下面分别对图论中有代表性的哥尼斯堡七桥问题，算法与算法复杂性领域中有代表性的汉诺（Hanoi ）塔问题，算法复杂性中的难解性问题，证比求易算法，旅行商问题与组合爆炸问题，哲学家共餐问题,图灵测试问题，博弈问题等问题及其相关内容进行分析。计算机学科中其它的典型问题，请读者参考有关资料。 第7章 计算机领域典型问题 7.1歌尼斯堡七桥问题与哈密尔顿回路问题 7.2汉诺塔问题 7.3算法复杂性中的难解性问题 7.4哲学家共餐问题 7.5旅行商问题 7.6图灵测试问题 7.7搏弈问题 7.1 歌尼斯堡七桥问题与 哈密尔顿回路问题 18世纪中叶，当时东普鲁士有一座哥尼斯堡（Konigsberg）城，城中有一条贯穿全市的普雷格尔（Pregol）河，河中央有座小岛，叫奈佛夫（Kneiphof）岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来，如图7.1所示。 当时该城市的人们热衷一个难题：一个人怎样不重复地走完七桥，最后回到出发地点？即寻找走遍这7座桥，且只许走过每座桥一次，最后又回到原出发点的路径。试验者都没有解决这个难题。1736年，瑞士数学家列昂纳德·欧拉（L.Euler）发表图论的首篇论文，论证了该问题无解，即从一点出发不重复地走遍七桥，最后又回到原来出发点是不可能的。他论证所用的图为图7.2所示。后人为了纪念数学家欧拉，将这个难题称为“哥尼斯堡七桥问题”。 为了解决哥尼斯堡七桥问题，欧拉用4个字母A、B、C、D代表4个城区，并用7条线表示7座桥，如图7.2所示。在图中，只有4个点和7条线，这样做是基于该问题本质的考虑，抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象成为一个数学问题，即经过图中每边一次且仅一次的回路问题了。欧拉在论文中论证了这样的回路是不存在的，后来，人们把有这样回路的图称为欧拉图。 将其有经过所有边的简单生成回路的图称为欧拉图 欧拉不仅给出了哥尼斯堡七桥问题的证明，还将问题进行了一般化处理，即对给定的任意一个河道图与任意多座桥，判定可能不可能每座桥恰好走过一次，并用数学方法给出了3条判定规则： （1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的； （2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线； （3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。 欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。 在图论中除了欧拉回路以外，还有一个著名的“哈密尔顿回路问题”。十九世纪爱尔兰数学家哈密尔顿(Hamilton)发明了一种叫做周游世界的数学游戏。它的玩法是：给你一个正十二面体，它有二十个顶点，把每个顶点看做一个城市，把正十二面体的三十条棱看成连接这些城市的路。请你找一条从某城市出发，经过每个城市恰好一次，并且最后回到出发点的路线。我们把正十二面体投影到平面上，在图7.3中标出了一种走法，即从城市1出发，经过2，3，…，20，最后回到1。 “哈密尔顿回路问题”与“欧拉回路问题”看上去十分相似，然而又是完全不同的两个问题。“哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。 7.2汉诺塔问题 传说在古代印度的贝拿勒斯神庙里安放了一块黄铜座，座上竖有三根宝石柱子。在第一根宝石柱上，按照从小到大、自上而下的顺序放有64个直径大小不一的金盘子，形成一座金塔，如图4－4所示，即所谓的汉诺塔（又称梵天塔）。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到