大家好我是熊猫钓鱼欢迎大家和我一起探讨技术。希望您能点赞关注谢谢「图论全景实测」系列第三篇。前两篇在证明算法「对」——一篇横评全家族《一座 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-KarpPareto 多目标风险敏感路径tie-breaking实验证伪目录0. 第三篇的任务从「算得对」到「模型错」1. 实验底座时变城市2. 失效 1静态假设——出发时的「快照」不是路上的真相2.1 误差的单边性负值 0 个2.2 FIFO 违反晚出发反而早到2.3 修正工具的账单时间扩展图2.4 误差窗口峰值不在拥堵时在「爆发前夜」3. 失效 2全知假设——不知道未来就被理论卡脖子3.1 竞争比典型图的 0.85 与最坏图的 0.6323.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 倍t48 分钟时清除图 4事故桥的 arrival(t) 曲线。t48 之前的车被事故拖住arrival 一路爬升到 61.86事故清除瞬间函数垂直下跳——t47.6 出发的车 61.86 到t48.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——精度每一档内存和跑时都在后面跪着。误差的绝对量级看着吓人因为粗时间片下每条边至少消耗一整个 step39 条边的路径在 step2 时误差就有 60 分钟。这不是 bug是离散化近似的本质——扩展图的正确性有明确的价格标签。还有一个更微妙的账单FIFO 违反时扩展图能通过等待边找到等一等的解但时变 Dijkstra 不能——它的松弛只考虑立即走。这就是 2.2 节里那条 0.4 分钟的缝隙连续时间的实时算法和离散时间的扩展图处理的是两个不同的数学对象。2.4 误差窗口峰值不在拥堵时在「爆发前夜」最后给静态误差画一张天气预报——沿时间轴逐时刻扫描图 6误差随出发时刻的变化。峰值出现在 t≈33 和 t≈48“爆发前夜”出发时路况尚好路上撞进爬坡段而拥堵峰值 t60 出发时误差归零——因为快照已经把拥堵算进去了规划自然绕开。这张非单调曲线是给导航产品经理的最坑人的不是最堵的时段而是快照看起来还行、路上急转直下的时段。要抓住的正是这个窗口。3. 失效 2全知假设——不知道未来就被理论卡脖子第二篇的派单实验里MCMF 靠知道全天订单多抢回 13 单。但现实中订单是一个一个来的调度器必须立即决策、不可反悔。学术上这叫在线二分匹配它的理论骨架极其漂亮随机到达顺序 贪心分配竞争比期望 ≥1 − 1/e ≈ 0.632Karp–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每个路口保留非支配标签集被支配的路径直接淘汰图 9Pareto 前沿与两条端点路径。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.7ppCVaR90最坏 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 会随时间变吗 → 会时变 DijkstraFIFO 满足/ 时间扩展图FIFO 可能被打破 → 务必检查 arrival(t) 单调性——事故、限行、场站开关都会打破它 2. 规划时知道全局吗 → 不知道算清楚你的图的稀疏结构。稠密图在线贪心 ≈ 离线最优 稀缺图先算竞争比下界1−1/e再决定要不要押注预测系统 3. 真的只有一个目标吗 → 不止一个Pareto label-setting 返回前沿偏好交给用户/下游 4. w 是确定的吗 → 不确定候选路径直接做蒙特卡洛评估确定性等价 wλσ 只配当粗筛 彩蛋等权图上给堆键加一个 tie-breaker如 −g白捡一个数量级的扩展量8. 诚实的边界老规矩交代实验的适用边界防止结论被过度外推时变模型是合成的钟形拥堵 阶跃事故覆盖了渐变与突变两类现实模式但不是任何一座真实城市的实测流量数据。误差的单边性2.1与FIFO 违反的机制2.2是模型无关的数学结论误差量级是场景的函数别引用具体数字竞争比实验的粒度静态二分图在线匹配一次性决策、不可撤销、无重匹配是真实派单的骨架不是全貌无转单、无并单、无预承诺。1−1/e 的收敛是教科书结果的复现价值在把理论跑给你看风险模型的独立性假设蒙特卡洛里各边独立——真实的拥堵是相关的一场雨全局变慢相关场景下尾部会更厚风险敏感的收益通常更大方向对量级存疑城市尺度676 路口、分钟级行程。百万节点级图上时变/扩展图的规模账单会放大几个数量级工业方案是收缩层次 动态重优化本篇的所有算法是它们的内核。9. 复现指南graph-blog3/ ├── timevar.py # 失效 1时变路网 FIFO 违反 时间扩展图~300 行 ├── online.py # 失效 2在线竞争比 KVV 阶梯紧例~200 行 ├── multiobj.py # 失效 3/4/5Pareto 风险 tie-breaking~320 行 ├── figs3_a.py # 图 1-7元图/时变/FIFO/扩展图/竞争比 ├── figs3_b.py # 图 8-13Pareto/风险/权衡/平局/工具箱 └── figure/ # 13 张实验图results/ 下为全部实验数据 JSONpython timevar.py# → results/timevar.jsonpython online.py# → results/online.json含 KVV 紧例收敛python multiobj.py# → results/multiobj.json含 260 组 OD 扫描python figs3_a.pypython figs3_b.py正确性验证时变 Dijkstra 与时间扩展图对拍量化误差曲线自证在线贪心与离线 HK 对拍真值来自第二篇已验证的实现Pareto 前沿做非支配二次过滤给定种子后所有确定性结果逐字节一致计时数据毫秒级抖动正常。随机种子路网沿用第一篇 seed42OD 扫描 seed77蒙特卡洛 seed5/11竞争比实验每规模 60–300 次重复。10. 写在最后三部曲的闭环三篇写下来主题其实是一条收敛的线第一篇算法横评同一张图算法决定你走得多快——16 张图验证了选对算法的价值第二篇建模视角同一份数据建模决定你答对问题——四张图证明建对模型比算得快更上位第三篇失效现场同一个模型假设决定你对到哪去——算法对、建模对假设错了结果照样是错的而且错得静悄悄。图论工具箱里没有放之四海的算法只有假设成立范围内的正确。写出算法前先写出假设验证结论前先验证假设——这是三篇实验合起来想说的一句话。三部曲完结。全系列代码、数据、图表均可复现第一篇graph-blog/、第二篇graph-blog2/、本篇graph-blog3/。欢迎带着反例来对线——尤其是想推翻 2.1 节误差单边性的先想想你的模型里 w 是不是真的只跟时间有关。系列第一篇《一座 676 路口的城市跑遍图论全家族15 张实验图从 BFS 讲到最大流》系列第二篇《同一份外卖数据我建了四种图拓扑排序、着色、匹配、状态搜索全实测》