③ 如果没有一个地方是通奇数座桥的，则无论从哪里出发，
所要求的路线都能实现。
• 欧拉回路的判定规则为：
图中所有地方都通偶数座桥（图中所有节点的边均为偶
数）。根据判定规则可以得出，任一连通无向图存在欧拉回路 的充分必要条件是图的所有顶点均有偶数度 。 • 有向欧拉通路的判定规则： ① 图连通； ② 除两个节点外，其余节点的入度=出度；
将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子
上，即将整个塔迁移，同时定下3条规则：
①每次只能移动一个盘子； ②盘子只能在三根柱子上来回移动，不能放在别处； ③在移动过程中，三根柱子上的盘子必须始终保持大盘在
下，小盘在上。
据说当这64个盘子全部移到第三根柱子上后，世界末日就 要到了。 汉诺塔问题是一个典型的用递归方法来解决的问题。递归 是计算机学科中的一个重要概念，它是将一个较大的问题归约为
塔求解问题。再由 1 个盘子的汉诺塔的解求出 2 个盘子的汉诺塔
……直到解出64个盘子的汉诺塔问题。
从左到右的柱子依次为A，B，C。移动时首先把上面n-1个盘 子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所 有盘子移动到B上，由此可以得出移动n个盘子的次数H(n)表达式:
H(1) = 1
为已知数，如图7.6、7.7所示。从图中可以看到，可供选择的路
线共有6条，可以很快选出一条总距离最短的路线。
当城市数目为n时，那么组合路径数则为（n-1）！。很显然 ，当城市数目不多时要找到最短距离的路线并不难，但随着城 市数目的不断增大，组合路线数将呈阶乘级急剧增长，以至达 到无法计算的地步，这就是所谓的“组合爆炸问题”。假设现 在 城 市 的 数 目 增 为 20 个 ， 组 合 路 径 数 则 为 （ 20-1 ） ！ ≈ 1.216×1017 ，如此庞大的组合数目，若计算机以每秒检索
③ 1个节点的入度比出度大1，1个节点的入度比出度小1，或者
所有节点的入度=出度。 • 有向欧拉回路的判定规则： ① 图连通； ② 所有节点的入度=出度。
欧拉的论文为图论的形成奠定了基础。今天，图论已广泛 地应用于计算机科学、运筹学、信息论、控制论等科学之中，并 已成为我们对现实问题进行抽象的一个强有力的数学工具。随着 计算机科学的发展，图论在计算机科学中的作用越来越大，同时
欧拉不仅给出了哥尼斯堡七桥问题的证明，还将问题进行
了一般化处理，即对给定的任意一个河道图与任意多座桥，判
定可能不可能每座桥恰好走过一次，并用数学方法给出了3条判 定规则。 • 欧拉通路的判定规则： ① 如果通奇数座桥的地方不止两个，满足要求的路线是找不 到的； ② 如果只有两个地方通奇数座桥，可以从这两个地方之一出 发，找到所要求的路线；
城市且只能在每个城市逗留一次，最后回到原出发城市。问如何
事先确定好一条最短的路线，使其旅行的费用最少？
人们在考虑解决这个问题时，首先想到的最原始的一种方法
是：列出每一条可供选择的路线（即对给定的城市进行排列组合
），计算出每条路线的总里程，最后从中选出一条最短的路线。 假设现在给定4个城市分别为A、B、C和D，各城市之间的距离
面体投影到平面上，在图 7.3 中标出了一种走法，即从城市 1 出发
，经过2，3，…，20，最后回到1。
图7.3 周游世界示意图
“哈密尔顿回路问题”与“欧拉回路问题”看上去十分相 似，然而又是完全不同的两个问题。“哈密尔顿回路问题”是 访问每个结点一次，而“欧拉回路问题”是访问每条边一次。
对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图
于排序和查找，我们对比较次数计数。空间由实施该算法所需的
最大内存来衡量。 算法M的复杂性是一个函ƒ(n)，它对于输人数据的规模n给
出运行该算法所需时间与所需存储空间。执行一个算法所需存储
空间通常就是数据规模的倍数。因此，除非特殊情况，“复杂性 ”将指运行算法的时间。
对于时间复杂性函数ƒ(n)，它通常不仅与输入数据的规模有 关，还与特定的数据有关。例如，在一篇英文短文中查找第一次 出现的3个字母的单词W。那么，如果W为定冠词“the”，则W
网络爬虫
网络爬虫是一个自动提取网页的程序。整个互联网中所有网 页构成的图中每一个网页URL作为一个结点。网络爬虫涉及图
论中经典的搜索算法，网页链接构成了节点之间边，整个万维
网可以看作一个图是网络爬虫的理论基础。
• 广度优先搜索 广度优先搜索策略是指在网页获取过程中，在完成当前层次 的搜索抓取后，再进行下一层次的搜索抓取。目前，为覆盖尽
G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必 要条件。
中国油路问题 我国著名数学家管梅谷教授在1960年提出了一个有重要理论
意义和广泛应用背景的问题，被称为“中国邮路问题”。邮递
员要把信送往各地点，由于送信地点多、道路不好走、还要绕 过楼房，出发前需要设计一条送信路线，从邮局出发不但把信 送到每一个地点，而且路线不重复，最后回到邮局。这一问题 可以表示为图7.4，其中，“· ”代表送信地点，空白方格“□”
一个或多个子问题的求解方法，这些子问题比原问题简单，但在
性质上与原问题相同。
图7.5 汉诺塔问题示意图
按照这种思想要解决64个盘子的汉诺塔问题可以转化为63 个盘子的汉诺塔问题。依此类推，63个盘子的汉诺塔求解问题可 以转化为62个盘子的汉诺塔求解问题，62个盘子的汉诺塔求解问 题又可以转化为 61个盘子的汉诺塔求解问题直到 1个盘子的汉诺
C
A
B
D
图7.2 哥尼斯堡七桥问题示意图
为了解决哥尼斯堡七桥问题，欧拉用4个字母A、B、C、D
代表 4 个城区，并用 7 条线表示 7 座桥，如图 7.2 所示。图中，只 有4 个点和 7条线，这样做是基于该问题的本质考虑，抽象出问 题最本质的东西，忽视问题非本质的东西（如桥的长度等）， 从而将哥尼斯堡七桥问题抽象成为一个数学问题，即经过图中 每边一次且仅一次的回路问题。欧拉在论文中论证了这样的回 路是不存在的，后来，人们把有这样回路的图称为欧拉图，即 包含有经过所有边的简单生成回路的图称为欧拉图。
(n=1)
（7.1）
（7.2）
H(n) = 2*H(n-1)+1 (n>1)
那么就能得到H(n)的一般式（其中n为盘子数目）：
H(n) = 2n – 1
(n>0)
（7.3）
因此，要完成64个盘子的汉诺塔的搬迁，需要移动盘子的次 数为： 264-1 = 18446744073709551615 次。如果每次移动花费 一秒,这表明移完这些盘子需要 5845.54亿年以上，而地球存在至 今不过 45 亿年，太阳系的预期寿命据说是数百亿年。真的过了
，图论本身也得到了充分的发展。
首 页
7.2 计算机领域的典型问题
7.2.1 图论问题
哈密尔顿回路问题 在图论中除了欧拉回路以外，还有一个著名的“哈密尔顿回
路问题”。十九世纪爱尔兰数学家哈密尔顿(Hamilton)发明了一种
叫做周游世界的数学游戏。它的玩法是：给你一个正十二面体， 它有二十个顶点，把每个顶点看作一个城市，把正十二面体的三 十条棱看成连接这些城市的路。请你找一条从某城市出发，经过 每个城市恰好一次，并且最后回到出发点的路线。我们把正十二
─ 对于这一问题，可以采用以下几步来解决： ① 图论建模：由于街道是双向通行的，可以把它看成是赋权无 向连通图，将路口抽象为点，街道抽象为边，街道的长度就
是每条边的权值，问题转化为在图中求一条回路，使得回路
的总权值最小。最理想的情况：若图中有欧拉回路，即可通 过所有的边，因此任何一个欧拉回路即为此问题的解。
目 录
7.2.2 算法复杂性问题 7.2.2 算法复杂性问题
汉诺塔问题
传说在古代印度的贝拿勒斯神庙里安放了一块黄铜座，座上竖 有三根宝石柱子。在第一根宝石柱上，按照从小到大、自上而下 的顺序放有 64 个直径大小不一的金盘子，形成一座金塔，如图 7.5所示，即所谓的汉诺塔（又称梵天塔）。天神让庙里的僧侣们
要的促进作用。本章将从图论问题、算法复杂性问题、机器智能
问题、并发控制问题和分布式计算进行分析。
目录
7.1 问题求解的一般过程
7.2 计算机领域的典型问题
7.2.1 图论问题 7.2.2 算法复杂性问题 7.2.3 计算智能问题 7.2.4 并发控制问题
7.2.5 分布式计算问题
7.1 问题求解的一般过程
1000万条路线的速度计算，也需要花上386年的时间。
算法复杂性分析与难解性问题 算法分析是计算机科学的一项主要工作。为了进行算法比较 ，我们必须给出算法效率的某种衡量标准。假设M是一种算法， 并设n为输入数据的规模。实施 M 所占用的时间和空间是衡量该 算法效率的两个主要指标。时间由“操作”次数衡量。比如，对
定义：问题求解是一个发现问题、分析问题，最后导向问题 目标与结果的过程，一般包括提出问题、明确问题、提出假
设、检验假设四个基本步骤。欧拉回路问题就是一个典型的
问题求解过程。 哥尼斯堡七桥问题：18世纪中叶，当时东普鲁士有一座哥尼
斯堡（ Konigsberg ）城，城中有一条贯穿全市的普雷格尔（
完七桥，最后回到出发地点？即寻找走遍这7座桥，且只许走过 每座桥一次，最后又回到原出发点的路径。试验者都没有解决 这个难题。1736年，瑞士数学家列昂纳德· 欧拉（L.Euler）发表 图论的首篇论文，论证了该问题无解，即从一点出发不重复地 走遍七桥，最后又回到原来出发点是不可能的。他论证所用的 图为图 7.2 所示。后人为了纪念数学家欧拉，将这个难题称为 “哥尼斯堡七桥问题”。
表示两个送信地点之间必须经过的区域，行走时不能走对角。
该问题归结为图论问题就是：给定一个连通无向图（没有孤立 的点），每条边都有非负的确定长度，求该图的一条经过每条 边至少一次的最短回路。