计算机导论（第5版） 课件 第11章-计算机领域的典型问题

计算机导论第11章

计算机领域的典型问题目录CONTENTS03并发控制问题01图论问题02算法复杂性问题图论问题哥尼斯堡七桥问题；哈密顿回路问题；中国邮路问题/01歌尼斯堡七桥问题问题描述在18世纪中叶，东普鲁士的哥尼斯堡城中有7座桥连接3个城区和1个岛区。城中人们时常讨论的一个话题：一个人怎样不重复地走完7座桥，最后还能回到原出发地点？

歌尼斯堡七桥问题欧拉对哥尼斯堡七桥问题进行了研究1736年，欧拉论证了该问题无解。欧拉的结论：从一点出发不重复地走遍7座桥，最后又回到原来出发点是不可能的。欧拉对问题进行了抽象：用4个字母A、B、C、D代表4个城区，并用7条边表示7座桥。歌尼斯堡七桥问题欧拉给出了3条判定规则如果通奇数座桥的地方不止两个，满足要求的路径是找不到的。如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到经过所有桥一次的路径。如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路径都能实现。歌尼斯堡七桥问题欧拉图经过图中每条边一次且仅一次的路径称为欧拉路径。如果欧拉路径的起点和终点为图中的同一个顶点，这时的欧拉路径称为欧拉回路。包含有欧拉回路的图称为欧拉图。哈密顿回路问题问题描述（周游世界游戏）找一条从某个城市出发，经过每个城市恰好一次，最后回到出发地的路径（哈密顿回路）。哈密顿回路问题哈密顿回路与欧拉回路的区别哈密顿回路是访问图的每个顶点一次，而欧拉回路是访问图的每条边一次。对于一个图是否存在欧拉回路，已给出充要条件（欧拉的判定规则）；而对于一个图是否存在哈密顿回路，至今仍未找到充要条件。中国邮路问题问题描述一个邮递员应如何选择一条路线，使他能够从邮局出发，走遍他负责送信的所有街道，最后回到邮局，并且所走的路程最短。归结为图论问题：给定一个连通无向图，求该图的一条经过每条边至少一次的最短回路。对于欧拉图，找到一条欧拉回路即可。对于非欧拉图，才是中国邮路问题的研究重点。算法复杂性问题汉诺塔问题；旅行商问题；NP完全问题/02汉诺塔问题问题描述将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上。汉诺塔问题盘子移动规则每次只能移动一个盘子。盘子只能在三根柱子上移动，不能放在他处。在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。汉诺塔问题递归思想将一个较大规模的问题的求解归约为一个或多个子问题的求解。这些子问题比原问题简单，且在结构上与原问题相同。汉诺塔问题用递归方法求解移动n个盘子的汉诺塔问题，需要移动盘子的次数是n-1个盘子的汉诺塔问题需要移动盘子次数的2倍加1，即h(n)=2h(n-1)+1。汉诺塔问题用递归方法求解（时间复杂度为O(2n)）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如果每秒移动一次，需要大约5849亿年的时间。汉诺塔问题用递归方法求解旅行商问题问题描述一旅行商从某城市出发，必须经过每个城市且只能经过一次，最后回到原出发城市。要求找到一条距离最短的路径（或费用最少的路径）。简单问题的解决办法（4个城市）列出每条可能的路径。从中选择距离最短的路径。旅行商问题遇到的困难城市个数较多时难以实现，出现组合爆炸问题。当城市个数为n时，组合路径数为(n-1)!，算法的复杂度为O(n!)。如果n=20，则组合路径数则为（20-1)！≈1.216×1017。若计算机每秒能计算出1亿条路径的长度，计算完所有路径的长度也需要38.6年的时间。可行的解决办法最近邻算法：每次选一个和所在城市最近的城市。得到的结果不是最短路径，是一个比较短的路径，但求解问题的复杂度大大降低。NP完全问题P类问题：将所有可以在多项式时间内求解的问题称为P类问题。NP类问题：将所有在多项式时间内可以验证的问题称为NP类问题。NP完全问题：在NP类问题中，某些问题的复杂性与整个类的复杂性有关，如果这些问题中的任意一个能在多项式的时间内求解，则所有NP类问题都能在多项式时间内求解，这些NP类问题称为NP完全问题。并发控制问题生产者-消费者问题；哲学家共餐问题/03生产者-消费者问题问题描述有n个生产者和m个消费者，在生产者和消费者之间设置了一个能存放k个产品的货架。只要货架未满，生产者pi生产的产品就可以放入货架，每次放入一个产品；只要货架非空，消费者cj就可以货架取走产品消费，每次取走一个。所有生产者的产品生产和消费者的产品消费都可以按自己的意愿进行，即相互之间是独立的。生产者-消费者问题约束条件不允许消费者从空货架取产品，现实中也是取不到的。不允许生产者向一个已装满产品的货架中再放入产品。应用背景是对操作系统中并发进程同步的一种抽象描述，多个进程虽然看起来是按异步方式执行的，但相互有关的进程应有一种协调机制。哲学家共餐问题问题描述围坐在圆桌旁的5位哲学家的生活除了用餐（吃面条）就是思考问题。用餐时需要左、右手各拿起一支筷子。用餐后将筷子放回原处，继续思考问题。哲学家共餐问题一位哲学家的活动进程表示思考问题；饿了停止思考，左手拿起一支筷子（拿不到就等)；右手拿起一支筷子（拿不到就等)；进餐（用两支筷子吃面条)；放下右手筷子；放下左手筷子；重新回到思考问题状态。哲学家共餐问题可能出现的问题当5位哲学家都同时拿起左手边筷子时，则5位哲学家都将拿不到右手边的筷子，并处于等待状态，导致5位哲学家都将无法进餐，此时称为死锁状态。将哲学家的活动进程修改一下，变为当右手边的筷子拿不到时，就放下左手边的筷子。可能在一个瞬间，5位哲学家都同时拿起左手边的筷子，则自然拿不到右手边的筷子，于是都同时放下左手的筷子，等一会，又同时拿起左手边的筷子，如此这样永远重复下去，则所有的哲学家仍然