河北大学数学与计算机学院计算机导论课件第8章 计算机领域的典型问题.ppt

第8章 计算机领域的典型问题 8.1 图论问题 8.2 算法复杂性问题 8.3 计算机智能问题 8.4 并发控制问题 8.5 本章小结 8.1 图论问题 歌尼斯堡七桥问题 哈密尔顿回路问题 中国邮路问题 8.1.1 歌尼斯堡七桥问题 8.1.1 歌尼斯堡七桥问题 欧拉对哥尼斯堡七桥问题进行了研究 1736年，欧拉论证了该问题无解。 从一点出发不重复地走遍7座桥，最后又回到原来出发点是不可能的。 欧拉对了问题进行了抽象 描述：用4个字母A、B、 C、D代表4个城区，并用 7条边表示7座桥。 8.1.1 歌尼斯堡七桥问题 欧拉的3条判定规则 如果通奇数座桥的地方不止两个，满足要求的路径是找不到的。 如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路径。 如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路径都能实现。 8.1.1 歌尼斯堡七桥问题 欧拉的研究工作奠定了图论的基础 涉及到的后续课程。 离散数学。 数据结构。 应用领域。 计算机网络性能分析。 交通运输网络调度。 地下管网配置。 8.1.2 哈密顿回路问题 问题描述（周游世界游戏） 找一条从某个城市出发，经过每个城市恰好一次，最后回到出发地的路径。 8.1.2 哈密顿回路问题 哈密顿回路与欧拉回路的区别 哈密顿回路问题是访问每个顶点一次，而欧拉回路问题是访问每条边一次。 对于一个图是否存在欧拉回路，已给出充要条件；而对于一个图是否存在哈密顿回路至今仍未找到充要条件。 8.1.3 中国邮路问题 问题描述 一个邮递员应如何选择一条路线，使他能够从邮局出发，走遍他负责送信的所有街道，最后回到邮局，并且所走的路程最短。 归结为图论问题：给定一个连通无向图，求该图的一条经过每条边至少一次的最短回路。 对于欧拉图，找到一条欧拉回路即可。对于非欧拉图，才是中国邮路问题的研究重点。 8.2 算法复杂性问题 汉诺塔问题 旅行商问题 NP完全问题 8.2.1 汉诺塔问题 问题描述 将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上。 8.2.1 汉诺塔问题 移动规则 每次只能移动一个盘子。 盘子只能在三根柱子上移动，不能放在他处。 在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。 8.2.1 汉诺塔问题 递归思想 将一个较大的问题的求解归约为一个或多个子问题的求解。而这些子问题比原问题简单，且在结构上与原问题相同。 8.2.1 汉诺塔问题 用递归方法求解 移动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 8.2.1 汉诺塔问题 用递归方法求解 每次只能移动一个盘子，要完成汉诺塔的搬迁，需要移动盘子的次数为： 264-1=18 446 744 073 709 551 615 每秒移动一次，需要大约5849亿年的时间。 8.2.2 旅行商问题 问题描述 一旅行商从某城市出发，必须经过每个城市且只能经过一次，最后回到原出发城市。 要求找到一条距离最短的路径（或费用最少的路径）。 原始的解决办法 列出每条可能的路径。 从中选择距离最短的路径。 8.2.2 旅行商问题 遇到的困难 城市个数较多时难以实现。 组合爆炸问题。 可行的解决办法 启发式算法。 近似算法。 8.2.3 NP完全问题 P类问题 将所有可以在多项式时间内求解的问题称为P类问题。 NP类问题 将所有在多项式时间内可以验证的问题称为NP类问题。 NP完全问题 在NP类问题中，某些问题的复杂性与整个类的复杂性有关，如果这些问题中的任意一个能在多项式的时间内求解，则所有NP类问题都能在多项式时间内求解，这些NP类问题称为NP完全问题。 8.3 计算机智能问题 图灵测试 西尔勒中文小屋 博弈问题 8.3.1 图灵测试 机器能思维吗 ？ 8.3.1 图灵测试 图灵测试游戏 游戏的参与者 一个男人、一个女人和一个不限性别的提问者。 游戏目标 提问者通过对其他两人的提问，来鉴别其中的男女。 游戏要求 提问者呆在与其他两个游戏者相隔离的房间里。 提问者和两游戏者之间通过电传打字机进行沟通。 8.3.1 图灵测试