相关算法

在本节中，我们简要描述与本章相关的三个问题——最短路径问题、中国邮递员问题和旅行商问题。

• 最短路径问题可以通过一种高效算法来解决，即通过一个有限的、逐步执行的程序能快速得出解决方案。
• 邮递员问题只考虑一种特殊情况。
• 旅行商问题，目前还没有已知的高效算法；因此必须在执行时间长的算法和启发式算法之间做出选择，启发式算法虽然应用起来很快，但只能给出近似解。

最短路径问题

注意，通过选取从 $A$ 到 $L$ 的任意一条路径并计算其长度，就可以很容易地得到答案的一个上界。例如，路径 $A\to B\to D\to G\to J\to L$ 的总长度为 18，所以最短路径的长度不会超过 18。

加权图

在最短路径问题中，图/连通图中的每条边都被赋予了一个非负数字，这样的图被称为加权图（weighted graph），赋予每条边 $e$ 的数字就是 $e$ 的权重（weight），用 $w(e)$ 表示。

• 最短路径问题就在于找到从 $A$ 到 $L$ 总权重最小的一条路径。
• 如果一个加权图中每条边的权重都为 1，那么该问题就简化为找出从 $A$ 到 $L$ 的最短路径中的边数问题。

解决思路

本质是动态规划思想，从起点到当前节点的最短距离一定来源于上一个具有最短距离的邻接节点。

• 动态规划数组 $l(V)$ 表示从起点 $A$ 到当前顶点 $V$ 的最短距离。同时再用一个数组标记当前顶点 $V$​ 是否已经找到了最短距离，称为永久标记。
• 递推方程
  • 用节点 $V^{{}^{\prime }}$ 表示当前节点 $V$ 的邻接节点
  • $l(V^{'})=min(l(V{‘}), l(V)+w(e_{VV^{’}})) $
• 初始化：起点最短距离标记为 $l(A)=0$，并永久标记。
• 遍历顺序：从起点开始遍历邻接节点，之后每次都从已经确定最短距离的顶点开始遍历，直到遍历完整个图。

中国邮递员问题

问题定义

在中国数学家管梅谷所探讨的这个问题中，一名邮递员希望投递信件，要覆盖尽可能短的总路程并返回其起点。显然，他必须至少遍历其路线中的每条道路一次，且应避免过多道路被重复经过。

解决思路

• 图表示
  • 用加权图的形式表述问题，该图对应道路网络，每条边的权重就是相应道路的长度。
  • 问题要求是找到一条总权重最小的闭迹，且每条边至少要经过一次。
• 思路
  • 如果该图是欧拉图，那么任何一条欧拉迹都是问题的解，欧拉迹可以通过弗勒里算法找到。
  • 如果该图不是欧拉图，但有可能是半欧拉图
    • 回顾推论：一个连通图是半欧拉图当且仅当它恰有两个度数为奇数的顶点。
    • 该图中恰好有两个顶点的度数为奇数，说明该图是一个半欧拉图。
    • 在一个半欧拉图中，任何半欧拉迹都必须以一个度数为奇数的顶点作为起始顶点，以另一个度数为奇数的顶点作为终点。
    • 找到一条半欧拉迹，该半欧拉迹会经过每条边，但是我们还需要从终点返回到起点。
    • 根据最短路径算法找到一条从终点返回起点的最短路径加入半欧拉迹即可。

旅行商问题

问题定义

在这个问题中，一名旅行推销员希望走访若干给定的城市并返回其起点，且要覆盖尽可能短的总路程。

走访给定城市可以视为走访图中尽可能多的顶点，即找哈密顿圈。

解决思路

• 图表示
  • 用加权图的形式表述问题，该图对应道路网络，每条边的权重就是相应道路的长度，也可以指代城市之间的通行时间，或者其他成本。
  • 问题要求是在一个加权完全图中找到总权重尽可能小的哈密顿圈。
• 思路
  • 一种可能的算法是计算所有可能的哈密顿回路的距离再选择距离最小的，但对于超过约五座城市的情况，该方法过于复杂。
    • 如果有20座城市，可能的回路数量是 $(19!)/2$，大约为 $6\times 10^{16}$。也有其他算法被提出，但应用起来耗时太长。
  • 另一方面，有几种启发式算法能快速大致告诉我们最短距离是多少，其中一种启发式方法将在后续中介绍。