第5章 网络战场：图与组合优化

第5章 · 网络战场：图与组合优化

本章要回答的三个问题：在由点与线构成的网络里，最短路径、最大流量怎么高效计算？为什么巡游类问题（TSP、车辆路径）会成为组合优化的试金石，启发式如何救场？选址与网络设计这类战略决策如何建模？本章把战场从"资源分配"切换到"网络结构"。

为什么会有这一章

物流、通信、电网、社交关系——世界的骨架是网络。网络上的决策问题有鲜明的两极：一端是多项式可解的优美算法，最短路径、最大流、最小生成树都有教科书级的经典解法，几十年来支撑着导航、调度与传输协议；另一端是 NP 难的深渊，旅行商问题稍加变化就是另一个世界，逼出了启发式、近似算法与局部搜索的整套兵法。本章沿这条光谱推进：先打可解的（建立算法直觉），再攻不可精确解的（建立工程直觉），最后落到选址这类战略模型。

读完能解决什么

• 手写 Dijkstra 与最大流算法，理解贪心正确性与增广路径的机理；
• 用近邻构造 + 2-opt 局部搜索搭建一个能打的 TSP 求解器；
• 建立 p-中值、覆盖模型的建模套路，理解"战略层选址、战术层路径"的分层决策观。

各节怎么分工

本章知识点清单

• 图的表示：邻接矩阵与邻接表的取舍；
• Dijkstra 的贪心不变量：已定节点的距离不再缩短；
• 负权边为何破坏 Dijkstra，何时用 Bellman-Ford；
• 增广路径与残量网络；最大流最小割定理的对偶含义；
• 组合爆炸的现场：TSP 的 (n−1)!/2 条路线；
• 近邻构造、2-opt、模拟退火的局部搜索谱系；
• p-中值与集合覆盖模型的典型约束结构。

网络战场的光谱

网络问题的难度不在图的大小，而在"顺序"二字：选路不涉及顺序，多项式可解；一旦要求访问顺序（巡游），组合爆炸立刻登场。

网络战场的两条军规

第一条军规：先问"要不要顺序"，再选算法。最短路、最大流不关心访问顺序，所以有多项式解法；一旦问题变成"每个点都要去一次"，顺序维度让组合数从多项式跳到阶乘级，精确算法与启发式的分界线就在这里。初学者常在这条线两侧用错兵器——拿分支定界硬啃几百点的路径问题，或拿启发式去解明明一次 Dijkstra 就能精确搞定的单源最短路。第二条军规：解的质量要有证书或度量。可解类问题的算法自带最优性保证；启发式的产出必须配上量化口径——比初始构造改进了多少、与下界（比如最小生成树或 1-树下界）还差几个百分点、随机种子换了几个解是否稳定。没有度量体系的启发式方案，在评审会上撑不过第一轮追问。这两条军规贯穿三节，请带着它们读。

另外提醒代码层面的一个安排：本章所有算法都手写而不依赖图计算库，目的是让每一步贪心选择、每一次增广、每一回换边都暴露在你眼前——库当然要在实战里用，但第一次遇到这些算法时亲手写一遍，对机理的理解深度完全不同。手写版本同时也是你未来做算法改造与调试的参照系：当库的输出可疑时，你拿得出一个可信的小规模对照实现。

先决条件

• 第 2 章的复杂性侦察（理解 NP 难的含义）；
• 基本的数据结构常识（列表、字典）；代码全部手写，不依赖图库。

往下走到哪

本章网络上的决策者是单一主体。下一章让多个决策者同时入场——博弈沙盘上，你的最优选择取决于别人的选择。