网络算法简介
欢迎来到网络算法的世界！本章属于你离散数学课程的一部分。试想像你正尝试使用 Google Maps 找出前往学校的最快路线，或者身为工程师，正试图以最少的物料将多个城镇连接起来。这些都是现实生活中典型的“网络”问题。
在本章中，我们将学习如何使用特定的分步规则——即算法 (algorithms)——来有效地解决这些问题。刚开始看到步骤很多别担心；只要掌握当中的模式，这其实就像跟着食谱做菜一样简单！
1. 最短路径：Dijkstra 算法
这里的目标很简单：找出网络中两点（顶点）之间权重最小的路径（通常指最短距离或最低成本）。
Dijkstra 算法运作原理
你可以把它想像成一次“受控的爆炸”。我们从起点开始，慢慢地为附近的点标记上它们距离起点的长度，直到抵达目的地为止。
分步流程：
- 为起始顶点加上一个永久标记 (permanent label)，数值为 0。
- 从你刚刚设定为永久标记的顶点开始，观察所有与之相邻 (adjacent)（相连）且尚未拥有永久标记的顶点。
- 计算这些邻点工作值 (working values)（暂时距离）：\( \text{新数值} = \text{当前永久标记顶点的数值} + \text{边的权重} \)。
- 如果计算出的新数值比之前的工作值小，则更新它。
- 在整个网络中，找出具有最小工作值的顶点，并将其设为新的永久标记。
- 重复此过程，直到目的地顶点获得永久标记为止。
快速回顾： 标记通常包含三个部分：顶点名称、变为永久标记的顺序，以及最终距离。
效率（阶数）： Dijkstra 算法具有平方阶 (quadratic order)，表示为 \( O(V^2) \)，其中 \( V \) 是顶点的数量。这意味着如果城镇数量增加一倍，电脑计算所需的时间可能会增加四倍！
常见错误提醒： 下一次设定永久标记时，务必从整个网络中挑选最小的工作值，而不仅仅是与当前点直接相连的那些点！
重点总结
Dijkstra 算法是处理加权网络中寻找两点之间绝对最短路径的首选工具。
2. 最小生成树 (Minimum Spanning Trees, MST)
有时候，我们的目标不仅是从 A 到 B，而是要将网络中的每一个点连接起来，并确保总边权重最小。这被称为最小连接器 (Minimum Connector) 或最小生成树 (Minimum Spanning Tree)。
Prim 算法
Prim 算法是“基于顶点”的。你从一个点出发，像植物生长一样扩展你的树，过程中总是添加连接到新点且最便宜的分支。
- 图形法： 选择一个起始顶点。添加连接到它的最短边。现在，观察所有从已拥有的顶点连接到尚未拥有的顶点的边，选出最短的一条。重复此步骤！
- 列表/矩阵法： 如果题目给出距离表，你可以删除已选行的数值，并在“已连接”顶点的列中寻找最小值。
Kruskal 算法
Kruskal 算法是“基于边”的。它甚至更简单，但需要小心避免出现“回路 (cycles)”（封闭路径）。
- 将网络中所有的边按长度由短到长排序。
- 挑选最短的边。
- 挑选下一条最短的边。如果它会形成回路（形成闭环），则放弃并跳至下一条。
- 重复此过程，直到所有顶点都被连接起来。
记忆小撇步： Prim 从一个点 (Point) 开始。Kruskal 从一个边的目录 (Katalog/List) 开始。
效率： Prim 和 Kruskal 算法都具有立方阶 (cubic order)，即 \( O(V^3) \)。对于电脑而言，它们比 Dijkstra 算法稍微“沉重”一点。
重点总结
使用 Prim 或 Kruskal 算法来以最小总权重连接所有节点。Prim 从一点向外生长；Kruskal 从列表中挑选最优边。
3. 旅行推销员问题 (Travelling Salesperson Problem, TSP)
在这个问题中，推销员必须访问每一个顶点并回到起点，同时最小化总距离。这比 MST 要困难得多，因为我们必须遵循特定的“回路 (cycle)”。
由于对于大型网络来说，“完美”答案非常难以寻找，我们通常会找出答案所在的范围（界限）。
上限：最近邻居法 (Nearest Neighbour Method)
这是一种“贪婪”的方法。从某个顶点开始，总是前往尚未访问过的最近顶点。当所有点都访问完后，直接回到起点。
小知识： 如果网络不是“完全图”（即并非每个城镇都有直接通往其他城镇的路），这种方法可能会“卡住”。你可能需要走更远的路才能到达遥远的城镇或回到家。
下限：MST 方法
要找到下限（我们知道真实答案必然大于或等于的值）：
- “删除”一个顶点及其所有相连的边。
- 找出剩余顶点的最小生成树 (MST)。
- 加上被删除顶点原先连接的两条最短边的权重。
- 结果即为一个下限。针对不同的删除顶点重复此步骤会得到不同的界限；其中最高的数值即为最有用的“最佳”下限。
重点总结
最近邻居法给出一个上限（一个“足够好”的路线）。删除顶点 + MST 方法给出一个下限（数学上的成本“地板”）。
4. 路线检查：中国邮差问题 (Route Inspection: The Chinese Postman Problem)
想像一位邮差需要走遍社区内的每一条街道（边）至少一次，并回到邮局。为了高效，他希望将必须重复行走的距离最小化。
度数规则 (Rule of Degrees)
如果网络中每个顶点的度数都是偶数（汇集在该点的边的数量为偶数），邮差可以将每一条边恰好走一遍。这是一个欧拉 (Eulerian) 回路。
如果有奇数点（度数为奇数的顶点），邮差就必须重复走某些边。
解决奇数点问题
我们必须将奇数点配对，并找出它们之间的最短路径来进行“重复行走”。
- 2 个奇数点： 找出它们之间的最短路径（如有需要可使用 Dijkstra），并将该权重加到所有边的总和中。
- 4 个奇数点： 有 3 种配对方式。例如，若点为 A、B、C、D，你可以配成 (AB, CD)、(AC, BD) 或 (AD, BC)。计算每种配对的“额外”权重总和，并选择最小的那一组。
- 6 个奇数点： 这会变得更复杂！共有 15 种可能的配对。
重要公式： 对于 \( 2n \) 个奇数点，配对数量为： \( 1 \times 3 \times 5 \times ... \times (2n - 1) \)。
例子： 对于 4 个奇数点 (\( n=2 \))，公式为 \( 1 \times 3 = 3 \) 种配对。对于 6 个奇数点 (\( n=3 \))，则为 \( 1 \times 3 \times 5 = 15 \) 种配对。
重点总结
路线检查问题的关键在于透过重复奇数点对之间的最短路径，使所有节点都变成“偶数点”。
最终快速回顾箱
Dijkstra： 两点间的最短路径。\( O(V^2) \)。
Prim/Kruskal： 连接所有点的最短方式。\( O(V^3) \)。
最近邻居法： 寻找巡回 (TSP) 的上限。
缩减网络上的 MST： 寻找巡回 (TSP) 的下限。
路线检查： 遍历每一条边；将奇数点两两配对。
如果刚开始觉得有点难，别担心！ 学习这些算法最好的方法就是拿张纸，画一个小网络，亲自按照算法步骤动手画一遍。你一定可以做到的！