欢迎来到图论算法 II！
在先前的学习中，你已经学会了如何找出两个特定点之间的最短路径（Dijkstra 算法），以及如何用最少的“电缆”连接所有点（Prim 算法和 Kruskal 算法）。现在，我们将进一步探讨如何有效率地处理整个网络的导航问题。
无论是邮差要将邮件送到每一条街道的每一户人家，还是送货司机需要在一天内走访多个不同的城市，这些算法都能帮助我们找到最省时、最省钱的路线。如果一开始觉得步骤很多，别担心——一旦你看出了当中的规律，这就像是一个逻辑分明的“解谜游戏”！
1. 路线检查算法（中国邮差问题）
这里的目标很简单：沿着网络中的每一条边至少走过一次，并回到起点，同时尽可能保持总距离最短。
理解节点度数 (Node Degrees)
在开始之前，请记住“握手定理”的规则：若一个节点连接了奇数条边，它就是奇点 (odd node)；若连接了偶数条边，它就是偶点 (even node)。要实现走遍每一条边且不重复走过任何边（即一个欧拉回路 Eulerian circuit），所有的节点都必须是偶点。
运作过程
如果网络中存在奇点，我们就必须重复走过某些边。该算法旨在找出需要重复哪些边，以增加最小的额外距离。
- 识别网络中的所有奇点。
- 列出这些奇点所有可能的配对方式 (pairings)。
- 针对每一种配对，找出节点之间的最短路径。
- 选择总距离最小的配对方案。
- 将这个最小距离加到原网络所有边的总和上。
快速复习：配对规则
在 D1 中，你将处理最多包含四个奇点的网络。如果你有四个奇点（假设为 A、B、C 和 D），它们恰好有三种配对方式：
1. (AB) 和 (CD)
2. (AC) 和 (BD)
3. (AD) 和 (BC)
常见错误：学生经常忘记检查节点间的“最短路径”。有时从 A 到 B 的最短距离并非直接连线，而是需要经过另一个节点！
重点总结：路线检查总长度 = (所有边的总和) + (配对带来的最小额外距离)。
2. 旅行推销员问题 (TSP)
如果说路线检查问题关注的是边，那么 TSP 关注的就是顶点。其目标是访问每一个顶点恰好一次，并回到起点。
实际问题 vs. 经典 TSP
经典 TSP：你需要访问每个顶点恰好一次。这通常发生在一个“完全图”中，即每个节点都直接连接到其他所有节点。
实际 TSP：你必须访问每个顶点，但如果重复经过某个顶点能让旅程更短，是被允许的。在这种情况下，我们通常会先将网络转换为一个最短距离的完全网络。
三角不等式 (Triangle Inequality)
听起来很深奥，但道理很简单！它指出两点之间的直接路径，绝对不会比经过第三点的路径长。
形式上：\( d(A, C) \le d(A, B) + d(B, C) \)。
如果一个网络满足此条件，使用“捷径”总能节省距离。
你知道吗？ TSP 被称为“NP-hard”问题。用计算机科学的术语来说，这意味着对于大规模网络，电脑要找到绝对完美的答案是非常困难的。这就是为什么我们需要使用界限 (Bounds)。
3. 寻找上限 (Upper Bound)
上限 (Upper Bound) 是一个“保证可行”的距离。我们知道最佳路线的长度最多就是这个距离。
方法 A：最近邻居算法 (Nearest Neighbour Algorithm)
这是一种“贪婪”算法——你总是选择距离当前点最近且尚未访问过的城市。
- 从指定的顶点出发。
- 前往最近且未访问过的顶点。
- 重复上述步骤，直到访问完所有顶点。
- 回到起始顶点。
注意：上限的结果可能会因起始顶点的不同而改变。通常考试会指定你从哪里开始！
方法 B：最小生成树加倍法 (Doubling the MST)
- 使用 Prim 或 Kruskal 算法找出最小生成树 (MST)。
- 将 MST 的权重加倍（这相当于将树中的每条路径走两遍以回到起点）。
- 利用捷径来避免重复访问节点，并选择最短的可用路径以缩短总距离。
快速复习盒
上限检查清单：
- 我是否访问了每一个节点？
- 我是否回到了起点？
- 我的计算正确吗？（一定要检查加法！）
4. 寻找下限 (Lower Bound)
下限 (Lower Bound) 是一个保证最佳路线长度至少要达到的数值。实际答案必定大于或等于此距离。
删除顶点法 (Deleted Vertex Method)
- 删除其中一个顶点及其所有相连的边。
- 找出剩余顶点的最小生成树 (MST)。
- 找出原先与被删除顶点相连的两条最短边。
- 下限 = (MST 的权重) + (那两条最短边的和)。
鼓励一下：如果你通过删除不同的顶点计算出不同的下限，数值最高的那一个就是“最好”的下限，因为它对最佳解的限制最准确。
重点总结：我们将这些界限结合起来，为最佳解建立一个区间：
下限 \(\le\) 最佳解 \(\le\) 上限
章节总结与小撇步
- 路线检查 (Route Inspection)：想着边。重点在于配对所有的奇点。
- TSP：想着顶点。重点在于上限和下限。
- 记忆小帮手：“最近邻居 (Nearest Neighbour)”是一个想吃最近零食的贪婪朋友（上限）。“删除顶点 (Deleted Vertex)”是一个需要地基（MST）和两根支柱（两条最短边）的建筑师（下限）。
- 考场攻略：对于路线检查，务必清晰地展示你的配对过程。对于 TSP，如果题目给你一个表格，确保你寻找的是那些尚未被“划掉”的数值中最小的数字。
你一定做得到的！只要多练习判断题目是在问路线检查（走遍所有路）还是 TSP（走遍所有镇），剩下的就只是按部就班地执行算法而已！