欢迎来到图论算法 II！
在之前的学习中，你已经学过如何找出两点之间的最短路径，或是如何以最少的线缆连接所有点。在这个章节，我们要进一步探讨更复杂的应用——规划现实生活中的最佳路径，例如邮差如何将信件送到街上的每一户人家，或是推销员如何走访多个城市。
这些算法是现代物流业的基石，像 Amazon 和 FedEx 这样的公司每天都在使用。如果刚开始觉得这些概念有点抽象，不用担心！我们会透过简单的类比，一步步为你拆解！
1. 路线检查算法 (Route Inspection Algorithm)
这个算法又称为中国邮差问题 (Chinese Postman Problem)，其核心在于找出最短的路线，使该路线能够走遍每一条边 (edge) 至少一次，并回到起点。
核心概念：偶点与奇点
在开始之前，请记得一个节点的度数 (degree) 或称价数 (valency)，是指与该节点相连的边的数量。
- 偶点 (Even Node)：相连的边数为偶数 (2, 4, 6...)。
- 奇点 (Odd Node)：相连的边数为奇数 (1, 3, 5...)。
黄金法则：如果网络中的所有节点皆为偶点，你便可以走遍每一条边恰好一次，并回到起点。这称为欧拉回路 (Eulerian circuit)。此时的总距离即为网络中所有权重之和。
如果出现奇点怎么办？
如果有奇点存在，你必须重复经过某些边。因为我们追求“最短”路线，所以我们希望重复经过的边其总权重越小越好。在考试中，你通常会处理含有两个或四个奇点的网络。
步骤拆解：检查过程
- 找出所有度数为奇数的节点。
- 列出这些奇点所有可能的配对方式。
- 计算每一组配对中，节点之间的最短路径。
- 选择总权重最小的那一组配对。
- 将这个最小权重加入网络中所有边的总权重。这就是你的最终答案！
4 个奇点 (A, B, C, D) 的范例：
配对方式只有三种：
1. (AB 和 CD)
2. (AC 和 BD)
3. (AD 和 BC)
小撇步：只需固定一个点（例如 A），将它与其他所有点配对，剩下的两个点会自动形成第二个配对！
重点复习：
- 欧拉图 (Eulerian)：所有节点皆为偶点。
- 半欧拉图 (Semi-Eulerian)：有两个奇点（你将从其中一个起点开始，并在另一个终点结束）。
- 路线检查：重复经过奇点之间的边，使路线“有效”变为偶点图。
2. 旅行推销员问题 (Travelling Salesman Problem, TSP)
邮差问题是要走遍每一条边，而旅行推销员则是要走遍每一个顶点 (vertex) 恰好一次并回到起点。这个问题比前者困难得多！
TSP 的两种分类
- 经典 TSP：必须走访每个顶点且不可重复。这通常适用于完全图 (complete graphs)。
- 实用 TSP：如果重复经过某些顶点能让总行程更短，则允许重复。我们会透过最短距离表 (table of least distances) 将“实用”问题转化为“经典”问题来处理。
三角不等式 (Triangle Inequality)
这是一个说明“直线距离最短”的华丽说法。正式定义为：
\( \text{Length } AB \leq \text{Length } AC + \text{Length } CB \)
如果网络中所有节点皆符合此条件，两点之间的最短路径永远是连接它们的那条边。
3. 寻找上限 (Upper Bound)
由于 TSP 非常困难，我们通常会寻找一个上限 (Upper Bound)——也就是我们确定可以达成的“足够好”的路线。主要有两种方法。
方法 A：最近邻居算法 (Nearest Neighbour Algorithm)
这是一个“贪婪”算法，就像一个懒惰的购物者，总是只去最近的下一家店。
- 选择一个起点。
- 前往距离最近且尚未造访的节点。
- 重复此动作直到造访所有顶点。
- 关键步骤：最后必须回到起点！
常见错误：学生常忘记最后一步——加上从最后一个节点回到起点的距离。
方法 B：最小生成树 (MST) x 2
1. 找出整个网络的 MST（使用 Prim’s 或 Kruskal’s 算法）。
2. 将 MST 的权重加倍。这是初始的上限。
3. 寻找捷径（利用最短距离表）来减少权重，以找到更好的上限。
小知识：“上限”是我们愿意支付行程的最大值。我们一直在寻找降低这个数值的方法！
4. 寻找下限 (Lower Bound)
下限 (Lower Bound) 是一个值，代表我们能找到的最优路径不可能短于这个值。它告诉我们：“这趟旅程的时间/距离绝对不可能少于这个数字。”
删除顶点法 (Deleted Vertex Method)
- 删除一个顶点以及所有与其相连的边。
- 找出剩余节点的最小生成树 (MST)。
- 找出原先与被删除顶点相连的两条最短边。
- 下限 = (MST 的权重) + (两条最短边之和)。
如果觉得复杂也不用担心！只要记住：下限不一定必须是一条可行的完整路线（它看起来常像“Y”字型，而非封闭的圆圈）。它的功用只是为我们的预期提供一个最低底线。
总结摘要：
- 上限：一条我们“做得到”的路线（通常由最近邻居法得出）。
- 下限：一条我们“无法超越”的数值（由删除顶点法得出）。
- 最佳解就在两者之间！
5. 最终总结与常见陷阱
关键术语复习：
- 路径 (Walk)：边的序列。
- 巡回 (Tour)：走访每一个顶点并回到起点的路线。
- 捷径 (Shortcuts)：在 TSP 中用来跳过已造访的顶点，以改善上限。
常见错误：
- 路线检查：忘记将“额外”重复的边加回图的原始总权重中。
- 最近邻居法：忘记加上最后回到起点的那条边。
- 下限计算：从整个图中选择两条最短边，而不是选择与被删除的顶点相连的两条最短边。
继续练习这些步骤吧！决策数学的核心就是完美地遵循“食谱”（算法）。你一定做得到的！