欢迎来到图论算法 II！
在之前的学习中，你已经学会了如何找出两点之间的最短路径（Dijkstra 算法）。但如果你是一位邮差，需要走遍街区内的每一条街道呢？或者是一位外送员，需要走遍每一个住户并回到起点呢？
在本章中，我们将探讨决策数学（Decision Mathematics）中最著名的两个问题：路线检查问题（Route Inspection Problem）和旅行推销员问题（Travelling Salesman Problem）。这些算法每年能为企业节省数以百万计的燃料与时间成本！
1. 路线检查问题
这个问题又称为中国邮差问题（Chinese Postman Problem），其目标是找出最短的路线，使该路线能走遍网络中的每一条边（edge）至少一次，并回到起始顶点。
背后的逻辑
想象一个图，其中每个顶点的度数（degree）皆为偶数（即连接到该点的边数为偶数）。这被称为欧拉图（Eulerian graph）。在这些图中，你可以走遍每一条边刚好一次，最后回到起点。这样一切都很简单！
然而，大多数真实世界的地图都包含奇点（odd nodes）（即连接边数为奇数的顶点）。为了完成路线，你必须重复走过某些边。
逐步算法（适用于最多 4 个奇点的情况）
- 找出奇点：检查每一个顶点，计算有多少条边与其相连。列出所有计数为奇数的顶点。
- 识别配对方式：如果你有两个奇点（A 和 B），只有一种配对方式：AB。如果你有四个奇点（A、B、C、D），则有三种可能的配对方式：
- AB 和 CD
- AC 和 BD
- AD 和 BC
- 寻找最短路径：计算每一对配对中两点之间的最短距离。
- 选择最小值：选择总权重最低的配对方案。
- 计算最终路线：总长度 = (网络中所有边的总和) + (最短配对方案的权重)。
小贴士：如果一开始觉得很棘手，别担心！只要记住：问题出在奇点。我们通过重复走过它们之间的最短路径，直到它们在效果上变成偶数，就能“修复”这些奇点。
常见错误：忘记将重复路径的权重加回到图中所有边的总和中。务必再次检查你的加法计算！
重点总结：路线检查问题的核心是走遍每一条边。为了将距离最小化，我们重复计算奇点对之间的最短路径。
2. 旅行推销员问题 (TSP)
与想要走遍每条街道的邮差不同，旅行推销员只在乎走遍每一个顶点（城市/住户）并回到起点，且路径总长度最短。
传统 TSP 与 实用 TSP
- 传统 TSP：每个顶点都直接与其他所有顶点相连（称为完全图, complete graph），且距离满足三角不等式（直接路径永远是最短的）。
- 实用 TSP：并非所有节点都直接相连。为了解决这个问题，我们会先通过找出每对节点间的最短“距离”路径，将其转换为完全图。
你知道吗？TSP 在计算机科学中是一个“困难”问题。随着城市数量增加，可能的路径数量会以惊人的速度增长，即便世界上最强大的计算机也难以快速找出完美答案！
3. 寻找上下界
由于找出 TSP 的精确最短路径非常困难，我们转而寻找答案所在的“范围”。这个范围由下界（Lower Bound）和上界（Upper Bound）定义。
上界（“够好”的路线）
上界是一个我们确定可以达到的距离。它可能不是最好的，但它是一条可行的路线。我们通常使用最近邻点算法（Nearest Neighbour Algorithm）：
- 选择一个起始顶点。
- 前往距离最近且尚未造访过的顶点。
- 重复上述步骤，直到所有顶点都已造访。
- 回到起点。
注意：你也可以通过在加倍的最小生成树（Minimum Spanning Tree）上使用“捷径”来改善上界。
下界（“最理想”的情境）
下界是一个最佳路线不可能比其更短的值。我们使用MST 方法（最小生成树法）：
- 删除一个节点：选择一个顶点（例如顶点 A），暂时删除它以及所有与其相连的边。
- 找出 MST：为剩余的节点找出最小生成树（使用 Prim's 或 Kruskal's 算法）。
- 重新连接：加入连接到已删除顶点 A 的两条最短边的权重。
- 总计：下界 = (MST 的权重) + (连接到顶点 A 的两条最短边)。
类比：把下界想象成房间的地板，上界想象成天花板。实际的最佳路线就在两者之间！
复习小窗口：
- 最近邻点算法得出上界。
- 删除节点 + MST + 两条最短边得出下界。
4. 转换为完全网络
有时，题目给出的网络不是“完全”的（某些城市之间没有直接连接）。要应用 TSP 算法，你必须先建立一个最短距离表。
这意味着如果你想从 A 到 C，但没有直接的边，你可能会发现从 A → B → C 是最短路径。接着，你就将 A 到 C 的距离视为这两个步骤的总和。
重点总结：对于 TSP，我们寻找的是哈密顿回路（Hamiltonian Cycle，走遍每个顶点一次并回到起点）。我们使用界限来缩小可能的最小距离范围。
检查清单
✓ 路线检查：我是否找出了所有奇点以及最便宜的配对方式？
✓ 最近邻点法：我是否总是选择最近且未造访过的节点？
✓ 下界：我是否记得将两条最短边加回到 MST 中？
✓ 准确性：我是否正确读取了表格/矩阵？（这是失分最常见的原因！）
你一定没问题的！决策数学的关键在于细心地遵循步骤。持续练习配对和 MST 方法，很快你就会成为这方面的高手！