企业官网建设流程全解析

大家好，我是熊猫钓鱼！欢迎大家和我一起探讨技术。希望您能点赞关注，谢谢！

「图论全景实测」系列第三篇。前两篇在证明算法「对」——一篇横评全家族（《一座 676 路口的城市，跑遍图论全家族》），一篇讲建模视角（《同一份外卖数据，我建了四种图》）。这篇反过来：证明模型在什么时候「错」。

教科书把图定义成G = (V, E, w)，干净利落。但这个定义里藏着四个几乎从不说出口的假设：静态（w 不随时间变）、全知（规划时知道全局）、单目标（只要一个 w 最小）、确定（w 是定值不是分布）。我用前两篇的城市与订单数据，把四条假设逐个实测证伪，每条配一个修正工具——也如实记录修正工具自己的账单。

全文 13 张图均为实验结果图，随机种子固定，可复现。

摘要

• 失效 1（静态假设）：50 组跨城 OD，静态规划误差负值 0 个——它不是"有误差"，而是单边低估：永远不会让你提前到，只会让你迟到。FIFO 性质实测被打破：某条路边晚 0.4 分钟出发反而早 12.63 分钟到达，此时"最早到达"的计算前提直接崩塌；
• 失效 2（全知假设）：在线派单竞争比在随机图上是 0.845（典型），但在 KVV 阶梯紧例上单调收敛到 0.6327，理论地板 1−1/e = 0.6321——同一套贪心，两种命运，取决于图的稀疏结构；
• 失效 3（单目标假设）：一条 OD 上实测4 条互不支配的路——走近路要多花 11.3% 时间，走快路要多绕 9.5% 距离，"最优"是偏好不是事实；
• 失效 4（确定假设）：均值最优路 vs 风险最优路，准点率 87.9% → 88.6%（+0.7pp）、CVaR90 改善 0.09 分钟——增益真实但微弱；教科书推荐的 w+λσ 确定性等价实测非单调（λ=3 反而比 λ=0 差）；
• 彩蛋（平局假设）：等权网格的"平局海洋"里，tie-breaking 让同一条 44 跳最优路的扩展量差11.8 倍（45 vs 529 个节点）。

关键词：时变最短路；FIFO；时间扩展图；在线算法竞争比；Hopcroft-Karp；Pareto 多目标；风险敏感路径；tie-breaking；实验证伪

目录

• 0. 第三篇的任务：从「算得对」到「模型错」
• 1. 实验底座：时变城市
• 2. 失效 1：静态假设——出发时的「快照」不是路上的真相
  • 2.1 误差的单边性：负值 0 个
  • 2.2 FIFO 违反：晚出发反而早到
  • 2.3 修正工具的账单：时间扩展图
  • 2.4 误差窗口：峰值不在拥堵时，在「爆发前夜」
• 3. 失效 2：全知假设——不知道未来就被理论卡脖子
  • 3.1 竞争比：典型图的 0.85 与最坏图的 0.632
  • 3.2 真实批次的反转：全知不值钱
• 4. 失效 3：单目标假设——「最优」是一条前沿
• 5. 失效 4：确定性假设——平均最快 ≠ 大概率准时
• 6. 彩蛋：平局假设——tie-breaking 决定白扫多少地
• 7. 修正工具箱与检查清单
• 8. 诚实的边界
• 9. 复现指南
• 10. 写在最后：三部曲的闭环

0. 第三篇的任务：从「算得对」到「模型错」

图 1：本篇任务地图。教科书图定义的四个隐含假设，每个配一节证伪实验和一个修正工具。

这个系列写到第三篇，我想把刀口对准一件比"算法写错"更隐蔽的事：算法完全正确，模型假设全是错的。

Dijkstra 没有 bug，但当边权随时间变化时，它给出的"最短"在物理世界里不成立；Hopcroft-Karp 没有 bug，但当订单一个一个到来时，它的"最大匹配"算的是一个不存在的问题。这类错误的可怕之处在于：不崩溃、不报错、日志全绿——只有拿现实数据重放，才会看到路径悄悄变长、准时率悄悄下滑。

1. 实验底座：时变城市

先给第一位主角：把第一篇的 676 路口城市升级成时变路网w(e, t)：

图 2：三条代表路段的通行时间曲线。中心快速路（红）午高峰涨到 9 倍；外围支路（绿）几乎不变；跨河桥（橙）堵起来最狠——10 分钟内从"全城最快"变成"全城最慢"。

模型本身很简单：w(e, t) = w0(e) × (1 + k_e × bell(t))，bell 是以正午 12:00 为峰值的钟形；k 按限速等级分化（中心 8.0、外围 2.0、小巷 0.5、桥 10）。这是一个温和、连续、满足 FIFO的拥堵模型——记住这个前提，第 2.2 节我们要亲手打破它。

后文还会复用第二篇的配送数据（163 单/30 商家/12 骑手）来做在线竞争比实验，以及第一篇的坐标工具来画图。三部曲的数据在这里合流。

2. 失效 1：静态假设——出发时的「快照」不是路上的真相

场景：你开车前用导航规划路线，导航用的是"当前时刻"的路况快照；但你开过去要 10 分钟，10 分钟后的路况不是快照。导航不知道未来——没有人知道，但算法可以知道"路况会变"这件事。

我把两种规划器放在同一条赛道上：

• 静态快照：用出发时刻 t 的边权当常数，跑标准 Dijkstra（=今天的导航的做法）；
• 时变最优：Dijkstra 的松弛规则改为"到达 u 的时刻决定走 (u,v) 的代价"，即arrive(v) = arrive(u) + w(u, v, arrive(u))。

同一批 50 组跨城 OD，出发时刻随机撒在"爆发前夜"窗口，然后把静态规划的路径按真实时变路况重放（这是关键——静态规划本身不知道它会变慢）：

图 3：最坏案例。左：静态规划选了穿中心快速路的直线（因为出发时它最快），重放真实路况要 42.1 分钟；中：时变最优知道中心即将爆发，改走外围支路，快 0.5 分钟（+1%）。

2.1 误差的单边性：负值 0 个

50 组 OD 的误差统计里，我想让你先看这一行：

neg_count: 0 ← 静态规划比时变最优「快」的案例数 min_extra: 0.0 ← 最小误差 mean_extra: 0.12 ← 平均多花（分钟） worst_extra: 0.53 ← 最坏多花 pct_worse: 40% ← 有可感知延迟的 OD 占比

误差负值是 0 个。这不是实验运气，是数学必然：静态规划的路径是时变问题的一个可行解，时变最优是全体可行解的下界——所以静态规划的误差恒为非负。

这条性质比误差的量级重要得多。它的工程含义是：静态假设的代价不是"有误差"，而是"误差从不站在你这边"。用快照规划，你不可能意外提前到达，只可能默默迟到；订单系统里这意味着 ETA 系统性偏乐观、承诺时限系统性违约——而所有监控面板都是绿的，因为算法没有出错。

至于量级（本模型下平均 +0.12 分钟、最坏 +0.53 分钟），如实说：它取决于拥堵对比度与路网几何的匹配度，我调参过程中见过更大也见过更小的值。方向性是结论，量级是场景的函数。

2.2 FIFO 违反：晚出发反而早到

上面所有讨论都建立在一条没被点破的公理上——FIFO 性质（First-In-First-Out）：早出发，到达时间不会更晚。用公式说，arrival(t) = t + w(t)必须单调不减。几乎所有"时变最短路"课程都把它当背景跳过，因为"现实路网天然满足"。

真的吗？我在这座城里制造了一场事故：某座桥的通勤时间在事故期间涨 12 倍，t=48 分钟时清除：

图 4：事故桥的 arrival(t) 曲线。t=48 之前的车被事故拖住（arrival 一路爬升到 61.86）；事故清除瞬间函数垂直下跳——t=47.6 出发的车 61.86 到，t=48.0 出发的车 49.23 到：晚 0.4 分钟出发，早 12.63 分钟到达。

FIFO 被打破了。后果是什么？所有依赖"arrival 单调"的算法性质开始漏水：

• Dijkstra 的"最早到达标号"不再可信——先处理 late 标号可能得到更早的到达；
• 静态规划的"最优路径"甚至不再是简单的次优，而是在物理上不可能复现的路径；
• 反过来，一个反直觉的正确答案出现了："原地等一等"可能胜过任何一条路。

实测这个 OD：绕行 vs 等待，到达时刻 49.27 vs 49.27——打平。结论要诚实：在有多条绕行选择的路网里，"等待"未必优于绕行（本例打平，事故代价 1.22 分钟）。但"晚出发早到"本身推翻的是一条公理级别的假设——工业界真正需要的不是"等待策略"，而是能检测 FIFO 违反并切换到时间扩展模型的重规划器（自动驾驶路径规划里这是一等公民：D* Lite、Anytime Repairing A* 都在处理这类动态性）。

2.3 修正工具的账单：时间扩展图

教科书对时变最短路的"正确答案"很明确：时间扩展图（time-expanded graph）——把 (路口, 时刻) 拍平成节点，等待是零成本边、行驶是真实成本边，然后在扩展图上跑普通 Dijkstra。理论上它可以处理 FIFO 违反（等待边让"等一等"变成显式选择）。

我把它实现出来跟时变 Dijkstra 对拍，同时记下它的账单：

图 5：时间扩展图的精度-规模权衡。时间片从 2 分钟细化到 0.25 分钟：到达时刻误差从 65.9 分钟降到 4.1 分钟（×16 改善），但状态数从 2.9 万涨到 31 万（×11）——精度每一档，内存和跑时都在后面跪着。

（误差的绝对量级看着吓人，因为粗时间片下每条边至少消耗一整个 step：39 条边的路径在 step=2 时误差就有 60+ 分钟。这不是 bug，是"离散化近似"的本质——扩展图的正确性有明确的价格标签。）

还有一个更微妙的账单：FIFO 违反时，扩展图能通过等待边找到"等一等"的解；但时变 Dijkstra 不能——它的松弛只考虑"立即走"。这就是 2.2 节里那条 0.4 分钟的缝隙：连续时间的实时算法和离散时间的扩展图，处理的是两个不同的数学对象。

2.4 误差窗口：峰值不在拥堵时，在「爆发前夜」

最后给静态误差画一张"天气预报"——沿时间轴逐时刻扫描：

图 6：误差随出发时刻的变化。峰值出现在 t≈33 和 t≈48（“爆发前夜”：出发时路况尚好，路上撞进爬坡段），而拥堵峰值 t=60 出发时误差归零——因为快照已经把拥堵算进去了，规划自然绕开。

这张非单调曲线是给导航产品经理的：最坑人的不是最堵的时段，而是"快照看起来还行、路上急转直下"的时段。要抓住的正是这个窗口。

3. 失效 2：全知假设——不知道未来就被理论卡脖子

第二篇的派单实验里，MCMF 靠"知道全天订单"多抢回 13 单。但现实中订单是一个一个来的，调度器必须立即决策、不可反悔。学术上这叫在线二分匹配，它的理论骨架极其漂亮：

• 随机到达顺序 + 贪心分配，竞争比期望 ≥1 − 1/e ≈ 0.632（Karp–Vazirani–Vazirani 1990）；
• 任何确定性在线算法，对抗顺序下竞争比 ≤1/2。

我要做的第一件事，是把这条 1990 年的定理在真实规模上跑出来。

3.1 竞争比：典型图的 0.85 与最坏图的 0.632

实验设计：n 个订单、n 个骑手、随机二分图（平均度 3），离线最优用第二篇的 Hopcroft-Karp 求，在线用同一套贪心、只变到达顺序：

图 7：两种图族上的竞争比。蓝线（随机二分图，典型情况）：0.845–0.864，远高于理论地板；红线（KVV 阶梯紧例，最坏情况）：0.6463 → 0.6327，随 n 增大单调收敛到理论线 0.6321。

这张图回答了一个很多人对竞争比的误解：

1−1/e 不是"在线算法通常能拿到的比例"，而是"最坏情况下保证拿到的下限"。典型随机图上是 0.85，而专门构造的阶梯紧例把你精确地压到 0.6321 的地板上——上界和下落都算得清清楚楚，这才是竞争比该有的读法。

3.2 真实批次的反转：全知不值钱

那真实配送数据属于哪一边？

图 8：左：真实午高峰批次（20 单 × 12 骑手）——在线贪心、随机序、对抗序全部拿到 12 单 = 离线最优；右：阶梯紧例的地板。

真实批次上竞争比 =1.0：可行边够稠密时，无论订单以什么顺序到达、无论贪心怎么贪，12 个骑手总能被填满。"全知"在这张图上不值一分钱。

把两张图放在一起，全知假设的失效边界就清晰了：

全知的价值 = f(图的稀疏结构) 稠密图（可行边富余）→ 在线 = 离线，全知免费 稀缺图（可行边嵌套）→ 在线被压到 0.632，全知昂贵

这解释了为什么外卖平台在午高峰之外的时段对"预测未来订单"投入有限，而在极端峰值时段预测系统就成了核心资产——同样的算法，不同的图，价值天差地别。

4. 失效 3：单目标假设——「最优」是一条前沿

导航里"最优"到底是什么意思？最快？最短？还是最便宜？教科书只给你一个 w，现实给你一串。

我把边权拆成两个目标：通行时间（分钟）和行驶距离（km），在一条跨城 OD 上跑双目标 label-setting（每个路口保留非支配标签集，被支配的路径直接淘汰）：

图 9：Pareto 前沿与两条端点路径。4 条互不支配的路——最快路线 2.54 分钟 / 1.81 km；最短路线 2.82 分钟 / 1.65 km。想走近路，多花 11.3% 时间；想走快路，多绕 9.5% 距离。

"最优路径"这四个字的真面目在这里：它不是一条路，是一条权衡曲线；你平时导航拿到的"最优"，只是这条曲线上按某个隐含偏好切出来的一点。偏好一变（今天赶时间 / 明天油价贵 / 后天要平稳），最优点整段平移。

单目标假设崩塌的工程含义：API 里应该返回前沿（或至少支持偏好参数），而不是假模假式地宣布唯一最优。主流导航已经开始这么做了（"时间优先/距离优先/少收费"三档选择），而教科书 Dijkstra 只给你其中的一档。

5. 失效 4：确定性假设——平均最快 ≠ 大概率准时

前面所有实验都默认w是一个确定的数。现实里它是分布：同一条路今天 20 分钟、明天事故 45 分钟；桥的方差尤其离谱。

给每条边配一个对数正态波动（快速路 σ=0.55、小巷 σ=0.22、桥 σ=0.8），然后问一个承诺时限场景：哪条路"大概率准时"？

图 10：均值最优 vs 风险最优。左：到达时间分布——两条路均值几乎相同，但右尾厚度不同；右：两条路的实际分歧。

实测数字（5000 次蒙特卡洛）：准点率87.9% → 88.6%（+0.7pp），CVaR90（最坏 10% 的平均到达时间）4.93 → 4.84 分钟。增益真实但微弱——这个 OD 上两条路的方差不悬殊，如实呈现。

更硬的锚在"修正工具"的体检上。教科书给的标准工具是确定性等价：把每条边的成本设为w + λσ（λ 是风险厌恶系数），然后照常跑 Dijkstra。我扫描 λ 做了完整的权衡曲线：

图 11：λ 旋钮拧出的准点率-期望时间曲线。注意它不是单调的：λ=0.4 时准点率最高（88.8%），λ=3 反而掉回 85.6%——比不做风险控制还差。

原因值得单独说：w + λσ的推导假设方差可加（路径方差 = 边方差之和），但真实路径的到达时间是边随机变量之和的分布，其方差不是边方差的和，更不是对数正态。边级启发式的"确定性等价"，在路径级是对分布的粗暴近似（学术上这正是"风险敏感搜索"要精确处理多项式分布的原因）。

诚实结论：风险敏感路径规划里，w + λσ 可以当粗筛，但当不了裁判。裁判要的是对候选路径直接做蒙特卡洛或分布卷积——工程上更贵，但不会开出 λ=3 比 λ=0 更差的笑话。

6. 彩蛋：平局假设——tie-breaking 决定白扫多少地

这一节是上文实验时被我撞见的"编外发现"，送给大家。

A* 的正确性和效率依赖堆里 f 值的严格排序。但在等权图上（所有边权相等——网格地图、BFS 类问题里极其常见），一大片节点的 f 值完全相等：从 (0,0) 到 (22,22) 的矩形区域里，所有单调路径上的节点 f 恒等于 44。这时"取 f 最小的"退化成"取堆内顺序"，tie-breaking 规则接管了搜索的形态：

图 12：同一个问题、同一条最优路径（44 跳）、三种 tie 规则。左：平局交给节点索引序——扩展529个节点（几乎扫完整片矩形）；中：平局偏向"走得更深"（堆键 (f, −g)）——沿一条链直插目标，只扩展45个节点；右：平局偏向"更浅"——BFS 式铺开，又是 529。

11.8 倍扩展差距，路径一模一样。tie-breaking 不改变答案，只决定你为这个答案扫多少地、烧多少电。

两个工程推论：其一，图数据库和路由引擎里"堆键的第三元组"是性能调优的公开秘密（Dijkstra 论文里从没提过它）；其二，平局还影响等代价路径的选择——同一 f 值下的不同路径，tie 规则一换就可能换路，这在实时重规划里表现为"导航路径莫名抖动"的经典 bug。

7. 修正工具箱与检查清单

四条假设的证伪-修正路线图：

图 13：失效 → 工具 → 证据。

把整篇的检查清单提取出来，下次动手建图之前过一遍：

拿到一个问题，先问四个问题： 1. w 会随时间变吗？ → 会：时变 Dijkstra（FIFO 满足）/ 时间扩展图（FIFO 可能被打破） → 务必检查 arrival(t) 单调性——事故、限行、场站开关都会打破它 2. 规划时知道全局吗？ → 不知道：算清楚你的图的稀疏结构。稠密图在线贪心 ≈ 离线最优； 稀缺图先算竞争比下界（1−1/e），再决定要不要押注预测系统 3. 真的只有一个目标吗？ → 不止一个：Pareto label-setting 返回前沿，偏好交给用户/下游 4. w 是确定的吗？ → 不确定：候选路径直接做蒙特卡洛评估；确定性等价 w+λσ 只配当粗筛 彩蛋：等权图上给堆键加一个 tie-breaker（如 −g），白捡一个数量级的扩展量

8. 诚实的边界

老规矩，交代实验的适用边界，防止结论被过度外推：

1. 时变模型是合成的：钟形拥堵 + 阶跃事故，覆盖了"渐变"与"突变"两类现实模式，但不是任何一座真实城市的实测流量数据。误差的单边性（2.1）与FIFO 违反的机制（2.2）是模型无关的数学结论；误差量级是场景的函数，别引用具体数字；
2. 竞争比实验的粒度：静态二分图在线匹配（一次性决策、不可撤销、无重匹配），是真实派单的骨架不是全貌（无转单、无并单、无预承诺）。1−1/e 的收敛是教科书结果的复现，价值在"把理论跑给你看"；
3. 风险模型的独立性假设：蒙特卡洛里各边独立——真实的拥堵是相关的（一场雨全局变慢），相关场景下尾部会更厚，风险敏感的收益通常更大（方向对，量级存疑）；
4. 城市尺度：676 路口、分钟级行程。百万节点级图上，时变/扩展图的规模账单会放大几个数量级，工业方案是收缩层次 + 动态重优化，本篇的所有算法是它们的内核。

9. 复现指南

graph-blog3/ ├── timevar.py # 失效 1：时变路网 + FIFO 违反 + 时间扩展图（~300 行） ├── online.py # 失效 2：在线竞争比 + KVV 阶梯紧例（~200 行） ├── multiobj.py # 失效 3/4/5：Pareto + 风险 + tie-breaking（~320 行） ├── figs3_a.py # 图 1-7（元图/时变/FIFO/扩展图/竞争比） ├── figs3_b.py # 图 8-13（Pareto/风险/权衡/平局/工具箱） └── figure/ # 13 张实验图；results/ 下为全部实验数据 JSON

python timevar.py# → results/timevar.jsonpython online.py# → results/online.json（含 KVV 紧例收敛）python multiobj.py# → results/multiobj.json（含 260 组 OD 扫描）python figs3_a.py&&python figs3_b.py

正确性验证：时变 Dijkstra 与时间扩展图对拍（量化误差曲线自证）；在线贪心与离线 HK 对拍（真值来自第二篇已验证的实现）；Pareto 前沿做非支配二次过滤；给定种子后所有确定性结果逐字节一致（计时数据毫秒级抖动正常）。

随机种子：路网沿用第一篇 seed=42；OD 扫描 seed=77；蒙特卡洛 seed=5/11；竞争比实验每规模 60–300 次重复。

10. 写在最后：三部曲的闭环

三篇写下来，主题其实是一条收敛的线：

• 第一篇（算法横评）：同一张图，算法决定你走得多快——16 张图验证了"选对算法"的价值；
• 第二篇（建模视角）：同一份数据，建模决定你答对问题——四张图证明"建对模型"比"算得快"更上位；
• 第三篇（失效现场）：同一个模型，假设决定你对到哪去——算法对、建模对，假设错了，结果照样是错的，而且错得静悄悄。

图论工具箱里没有"放之四海"的算法，只有"假设成立范围内"的正确。写出算法前，先写出假设；验证结论前，先验证假设——这是三篇实验合起来想说的一句话。

三部曲完结。全系列代码、数据、图表均可复现：第一篇graph-blog/、第二篇graph-blog2/、本篇graph-blog3/。欢迎带着反例来对线——尤其是想推翻 2.1 节"误差单边性"的，先想想你的模型里 w 是不是真的只跟时间有关。

系列第一篇：《一座 676 路口的城市，跑遍图论全家族：15 张实验图，从 BFS 讲到最大流》
系列第二篇：《同一份外卖数据，我建了四种图：拓扑排序、着色、匹配、状态搜索全实测》