计算机领域的典型问题

1、 计算机导论计算机导论(2009)第第8章章 计算机领域的典型问题计算机领域的典型问题8.1 图论问题图论问题 8.2 算法复杂性问题算法复杂性问题 8.3 计算机智能问题计算机智能问题 8.4 并发控制问题并发控制问题8.5 本章小结本章小结 计算机导论计算机导论(2009)8.1 图论问题图论问题 歌尼斯堡七桥问题歌尼斯堡七桥问题哈密尔顿回路问题哈密尔顿回路问题中国邮路问题中国邮路问题 计算机导论计算机导论(2009)8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题问题描述问题描述一个人怎样不重复地走完七座桥，最后还能回到原一个人怎样不重复地走完七座桥，最后还能回到原出发地点？出发地点？ 计算

2、机导论计算机导论(2009)8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题欧拉对欧拉对哥尼斯堡哥尼斯堡七桥问题进行了研究七桥问题进行了研究1736年，欧拉论证了该问题无解。年，欧拉论证了该问题无解。从一点出发不重复地走遍从一点出发不重复地走遍7座桥，最后又回到原来出发点座桥，最后又回到原来出发点是不可能的。是不可能的。欧拉对了问题进行了抽象欧拉对了问题进行了抽象 描述：用描述：用4个字母个字母A、B、 C、D代表代表4个城区，并用个城区，并用 7条边表示条边表示7座桥。座桥。 计算机导论计算机导论(2009)欧拉的欧拉的3 3条判定规则条判定规则如果通奇数座桥的地方不止两个，满足要求的路如果通奇

3、数座桥的地方不止两个，满足要求的路径是找不到的。径是找不到的。如果只有两个地方通奇数座桥，可以从这两个地如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路径。方之一出发，找到所要求的路径。如果没有一个地方是通奇数座桥的，则无论从哪如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路径都能实现。里出发，所要求的路径都能实现。8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题 计算机导论计算机导论(2009)欧拉的研究工作奠定了图论的基础欧拉的研究工作奠定了图论的基础涉及到的后续课程。涉及到的后续课程。离散数学。离散数学。数据结构。数据结构。应用领域。应用领域。计算机网络性能分

4、析。计算机网络性能分析。交通运输网络调度。交通运输网络调度。地下管网配置。地下管网配置。8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题航空网络 计算机导论计算机导论(2009)8.1.2 哈密顿回路问题哈密顿回路问题问题描述（周游世界游戏）问题描述（周游世界游戏）找一条从某个城市出发，经过每个城市恰好一次，找一条从某个城市出发，经过每个城市恰好一次，最后回到出发地的路径。最后回到出发地的路径。 计算机导论计算机导论(2009)哈密顿回路哈密顿回路与与欧拉回路欧拉回路的区别的区别哈密顿回路问题哈密顿回路问题是访问每个顶点一次，而是访问每个顶点一次，而欧拉回路欧拉回路问题问题是访问每条边一次。是访问

5、每条边一次。对于一个图是否存在对于一个图是否存在欧拉回路欧拉回路，已给出充要条件；，已给出充要条件；而对于一个图是否存在而对于一个图是否存在哈密顿回路哈密顿回路至今仍未找到充至今仍未找到充要条件。要条件。8.1.2 哈密顿回路问题哈密顿回路问题 计算机导论计算机导论(2009)问题描述问题描述一个邮递员应如何选择一条路线，使他能够从邮局出发，一个邮递员应如何选择一条路线，使他能够从邮局出发，走遍他负责送信的所有街道，最后回到邮局，并且所走走遍他负责送信的所有街道，最后回到邮局，并且所走的路程最短。的路程最短。归结为图论问题：给定一个连通无向图，求该图的一条归结为图论问题：给定一个连通无向图，求

6、该图的一条经过每条边至少一次的最短回路。经过每条边至少一次的最短回路。对于欧拉图，找到一条欧拉回路即可。对于非欧拉图，对于欧拉图，找到一条欧拉回路即可。对于非欧拉图，才是中国邮路问题的研究重点。才是中国邮路问题的研究重点。 8.1.3 中国邮路问题中国邮路问题 计算机导论计算机导论(2009)8.2 算法复杂性问题算法复杂性问题 汉诺塔问题汉诺塔问题旅行商问题旅行商问题 NP完全问题完全问题 计算机导论计算机导论(2009)8.2.1 汉诺塔问题汉诺塔问题问题描述问题描述将第一根柱子上的将第一根柱子上的64个盘子借助第二根柱子全部移个盘子借助第二根柱子全部移到第三根柱子上。到第三根柱子上。64

7、个盘子63个盘子 计算机导论计算机导论(2009)8.2.1 汉诺塔问题汉诺塔问题移动规则移动规则每次只能移动一个盘子。每次只能移动一个盘子。盘子只能在三根柱子上移动，不能放在他处。盘子只能在三根柱子上移动，不能放在他处。在移动过程中，三根柱子上的盘子必须始终保持在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。大盘在下，小盘在上。 计算机导论计算机导论(2009)递归思想递归思想将一个较大的问题的求解归约为一个或多个子问题将一个较大的问题的求解归约为一个或多个子问题的求解。而这些子问题比原问题简单，且在结构上的求解。而这些子问题比原问题简单，且在结构上与原问题相同。与原问题相同。

8、从前有座山 从前有座山 从前有座山8.2.1 汉诺塔问题汉诺塔问题 计算机导论计算机导论(2009)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 计算机导论计算机导论(2009)8.2.1 汉诺塔问题汉诺

9、塔问题用递归方法求解用递归方法求解每次只能移动一个盘子，要完成汉诺塔的搬迁，每次只能移动一个盘子，要完成汉诺塔的搬迁，需要移动盘子的次数为：需要移动盘子的次数为： 264-1=18 446 744 073 709 551 615每秒移动一次，需要大约每秒移动一次，需要大约5849亿年的时间。亿年的时间。 计算机导论计算机导论(2009)8.2.2 旅行商问题旅行商问题问题描述问题描述一旅行商从某城市出发，必须经过每个城市且只能经过一次，最后回一旅行商从某城市出发，必须经过每个城市且只能经过一次，最后回到原出发城市。到原出发城市。要求找到一条距离最短的路径（或费用最少的路径）。要求找到一条距离最

10、短的路径（或费用最少的路径）。原始的解决办法原始的解决办法列出每条可能的路径。列出每条可能的路径。从中选择距离最短的路径。从中选择距离最短的路径。 计算机导论计算机导论(2009)8.2.2 旅行商问题旅行商问题遇到的困难遇到的困难城市个数较多时难以实现。城市个数较多时难以实现。组合爆炸问题。组合爆炸问题。可行的解决办法可行的解决办法启发式算法。启发式算法。近似算法。近似算法。 计算机导论计算机导论(2009)8.2.3 NP完全问题完全问题P类问题类问题将所有可以在多项式时间内求解的问题称为将所有可以在多项式时间内求解的问题称为P类问题。类问题。 NP类问题类问题将所有在多项式时间内可以验证

11、的问题称为将所有在多项式时间内可以验证的问题称为NP类问题。类问题。 NP完全问题完全问题在在NP类问题中，某些问题的复杂性与整个类的复杂性类问题中，某些问题的复杂性与整个类的复杂性有关，如果这些问题中的任意一个能在多项式的时间有关，如果这些问题中的任意一个能在多项式的时间内求解，则所有内求解，则所有NP类问题都能在多项式时间内求解，类问题都能在多项式时间内求解，这些这些NP类问题称为类问题称为NP完全问题。完全问题。 计算机导论计算机导论(2009)8.3 计算机智能问题计算机智能问题 图灵测试图灵测试西尔勒中文小屋西尔勒中文小屋博弈问题博弈问题 计算机导论计算机导论(2009)8.3.1

12、图灵测试图灵测试机器能思维吗机器能思维吗 ？ 计算机导论计算机导论(2009)8.3.1 图灵测试图灵测试图灵测试游戏图灵测试游戏游戏的参与者游戏的参与者一个男人、一个女人和一个不限性别的提问者。一个男人、一个女人和一个不限性别的提问者。游戏目标游戏目标提问者通过对其他两人的提问，来鉴别其中的男女。提问者通过对其他两人的提问，来鉴别其中的男女。游戏要求游戏要求提问者呆在与其他两个游戏者相隔离的房间里。提问者呆在与其他两个游戏者相隔离的房间里。提问者和两游戏者之间通过电传打字机进行沟通。提问者和两游戏者之间通过电传打字机进行沟通。 计算机导论计算机导论(2009)8.3.1 图灵测试图灵测试图灵

13、测试游戏图灵测试游戏把游戏中的男人换成机器。把游戏中的男人换成机器。若提问者在与机器、女人的游戏中作出的错误判断若提问者在与机器、女人的游戏中作出的错误判断与在男人、女人之间的游戏中作出的错误判断，其与在男人、女人之间的游戏中作出的错误判断，其次数相同或更多，则判定这部机器能够思维。次数相同或更多，则判定这部机器能够思维。根据图灵当时的预测，到根据图灵当时的预测，到2000年能有机器通过这样年能有机器通过这样的测试。有人认为，在的测试。有人认为，在1997年战胜国际象棋大师卡年战胜国际象棋大师卡斯帕罗夫的斯帕罗夫的深蓝深蓝计算机可以看作通过了图灵测试。计算机可以看作通过了图灵测试。 计算机导论

14、计算机导论(2009)8.3.2 西尔勒中文小屋西尔勒中文小屋问题描述问题描述西尔勒被关在一个小屋中，屋子里有序地堆放着足西尔勒被关在一个小屋中，屋子里有序地堆放着足够的中文字符，而他对中文一窍不通。够的中文字符，而他对中文一窍不通。屋外的人递进一串中文字符，同时还附有一本用英屋外的人递进一串中文字符，同时还附有一本用英文编写的处理中文字符的规则，这些规则将递进来文编写的处理中文字符的规则，这些规则将递进来的字符和小屋中的字符之间的转换作了形式化的规的字符和小屋中的字符之间的转换作了形式化的规定。定。西尔勒按照规则对这些字符进行处理后，将一串新西尔勒按照规则对这些字符进行处理后，将一串新的中文

15、字符送出屋外。的中文字符送出屋外。 计算机导论计算机导论(2009)8.3.2 西尔勒中文小屋西尔勒中文小屋问题描述问题描述实际上，送进来的字符串就是屋外人提出的实际上，送进来的字符串就是屋外人提出的问题问题，送出去的字符串就是所提出问题的送出去的字符串就是所提出问题的答案答案。但。但西尔勒西尔勒并不清楚自己在做什么？并不清楚自己在做什么？ 计算机导论计算机导论(2009)8.3.2 西尔勒中文小屋西尔勒中文小屋西尔勒的观点西尔勒的观点形式化的计算机仅有语法，没有语义，只是按规形式化的计算机仅有语法，没有语义，只是按规则办事，并不理解规则的含义及自己在做什么？则办事，并不理解规则的含义及自己在

16、做什么？机器永远也不可能代替人脑。机器永远也不可能代替人脑。图灵的观点图灵的观点不要求机器与人脑在内部构造上一样，只要与人不要求机器与人脑在内部构造上一样，只要与人脑有相同的功能就认为机器有思维。脑有相同的功能就认为机器有思维。 计算机导论计算机导论(2009)人工智能的含义人工智能的含义研究、开发用于模拟、延伸和扩展人的智能的理论、方研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。法、技术及应用系统的一门新的技术科学。人工智能研究的目标人工智能研究的目标使机器能够胜任一些通常需要人类智能才能完成的复杂使机器能够胜任一些通常需要人类智能才能完成的复杂工作。

17、工作。 8.3.2 西尔勒中文小屋西尔勒中文小屋 计算机导论计算机导论(2009)人工智能的不同观点人工智能的不同观点符号主义符号主义：认为人的认知基元是符号，认为人是一个物认为人的认知基元是符号，认为人是一个物理符号系统，计算机也是一个物理符号系统，因而能够理符号系统，计算机也是一个物理符号系统，因而能够用计算机来模拟人的智能行为。用计算机来模拟人的智能行为。连接主义连接主义：认为人的思维基元是神经元，而不是符号处认为人的思维基元是神经元，而不是符号处理过程。认为人脑不同于电脑，主张人工智能应着重于理过程。认为人脑不同于电脑，主张人工智能应着重于结构模拟。结构模拟。行为主义行为主义：认为智能

18、取决于感知和行动，提出智能行为认为智能取决于感知和行动，提出智能行为的的感知动作感知动作模式。模式。8.3.2 西尔勒中文小屋西尔勒中文小屋 计算机导论计算机导论(2009)人工智能的展望人工智能的展望目前人们对心理学和生物学的认识还很不成熟，对目前人们对心理学和生物学的认识还很不成熟，对人脑的结构还没有真正了解，无法建立起人脑思维人脑的结构还没有真正了解，无法建立起人脑思维完整的数学模型。完整的数学模型。让计算机具有和人脑完全一样的智能，不是短期内让计算机具有和人脑完全一样的智能，不是短期内能够实现的。能够实现的。在相当长的时间内，只能从不同的侧面、以不同的在相当长的时间内，只能从不同的侧面

19、、以不同的方式让计算机具有某些类似人的智能。方式让计算机具有某些类似人的智能。8.3.2 西尔勒中文小屋西尔勒中文小屋 计算机导论计算机导论(2009)8.3.3 博弈问题博弈问题博弈的含义博弈的含义狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质的游戏。具有输赢性质的游戏。广义上讲，博弈就是对策或斗智。广义上讲，博弈就是对策或斗智。 计算机导论计算机导论(2009)8.3.3 博弈问题博弈问题双人完备博弈双人完备博弈两位选手对垒，轮流走步，其中一方完全知道另两位选手对垒，轮流走步，其中一方完全知道另一方已经走过的棋步以及未来可能的棋步。一方已经

20、走过的棋步以及未来可能的棋步。对弈的结果要么是一方赢（另一方输），要么是对弈的结果要么是一方赢（另一方输），要么是和局。和局。对于任何一种双人完备博弈，都可以用一个博弈对于任何一种双人完备博弈，都可以用一个博弈树来描述，并通过博弈树搜索策略寻找最佳解。树来描述，并通过博弈树搜索策略寻找最佳解。 计算机导论计算机导论(2009)博弈树博弈树博弈树类似于状态图和问题求解搜索中使用的搜博弈树类似于状态图和问题求解搜索中使用的搜索树。索树。搜索树上的一个结点对应一个棋局，树的分支表搜索树上的一个结点对应一个棋局，树的分支表示棋的走步，根结点表示棋局的开始，叶结点表示棋的走步，根结点表示棋局的开始，叶结

21、点表示棋局的结束。示棋局的结束。博弈树是非常大的，国际象棋有博弈树是非常大的，国际象棋有10120个结点，中个结点，中国象棋来有国象棋来有10160个结点。个结点。8.3.3 博弈问题博弈问题 计算机导论计算机导论(2009)中国象棋博弈树中国象棋博弈树8.3.3 博弈问题博弈问题 计算机导论计算机导论(2009)8.4 并发控制问题并发控制问题 生产者生产者-消费者问题消费者问题哲学家共餐问题哲学家共餐问题 计算机导论计算机导论(2009)8.4.1 生产者生产者-消费者问题消费者问题问题描述问题描述有有n个生产者和个生产者和m个消费者，在生产者和消费者个消费者，在生产者和消费者之间设置了一

22、个能存放之间设置了一个能存放k个产品的货架。个产品的货架。只要货架未满，生产者只要货架未满，生产者pi生产的产品就可以放入生产的产品就可以放入货架，每次放入一个产品；货架，每次放入一个产品；只要货架非空，消费者只要货架非空，消费者cj就可以货架取走产品消就可以货架取走产品消费，每次取走一个。费，每次取走一个。所有生产者的产品生产和消费者的产品消费都可所有生产者的产品生产和消费者的产品消费都可以按自己的意愿进行，即相互之间是独立的。以按自己的意愿进行，即相互之间是独立的。 计算机导论计算机导论(2009)8.4.1 生产者生产者-消费者问题消费者问题约束条件约束条件不允许消费者从空货架取产品，现

23、实中也是取不不允许消费者从空货架取产品，现实中也是取不到的。到的。不允许生产者向一个已装满产品的货架中再放入不允许生产者向一个已装满产品的货架中再放入产品。产品。应用背景应用背景是对操作系统中并发进程同步的一种抽象描述，是对操作系统中并发进程同步的一种抽象描述，多个进程虽然看起来是按异步方式执行的，但相多个进程虽然看起来是按异步方式执行的，但相互有关的进程应有一种协调机制。互有关的进程应有一种协调机制。 计算机导论计算机导论(2009)8.4.2 哲学家共餐问题哲学家共餐问题问题描述问题描述哲学家的生活除了吃面条就是思考问题。哲学家的生活除了吃面条就是思考问题。吃面条的时候需要左、右手各拿起一

24、支筷子。吃面条的时候需要左、右手各拿起一支筷子。吃完后将筷子放回原处，继续思考问题。吃完后将筷子放回原处，继续思考问题。 计算机导论计算机导论(2009)8.4.2 哲学家共餐问题哲学家共餐问题一个哲学家的活动进程表示一个哲学家的活动进程表示思考问题。思考问题。饿了停止思考，左手拿一支筷子（拿不到就等）。饿了停止思考，左手拿一支筷子（拿不到就等）。右手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等） 。进餐。进餐。放右手筷子。放右手筷子。放左手筷子。放左手筷子。重新回到思考问题状态。重新回到思考问题状态。 计算机导论计算机导论(2009)8.4.2 哲学家共餐问题哲学家共餐问题可能出现的问题可能出现的问题当所有的哲学家都同时拿起左手筷子时，则所有的哲学当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，最终饿死。家都将无法进餐，最终饿死。将哲学家的活动进程修改一下，变为当右手的筷子拿不将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子。到