所有实验均为确定性随机种子(20261121ULL)或步骤计数,与时钟无关。
myers_knuth_test.cpp:- Myers \(O(ND)\)
编辑脚本重建 vs Wagner-Fischer \(O(NM)\) 编辑距离对拍(300
组随机串 +
"ABCABBA" -> "CBABAC"逐层V[k]追踪),并统计 \(N=2000\)、不同编辑距离 \(D\) 下的状态访问量; - Knuth-Plass 最优断行 DP vs \(2^{n-1}\) 暴力枚举对拍(150
组随机词宽段落),并对比 Greedy First-Fit 与 Knuth-Plass 的
demerits。
- Myers \(O(ND)\)
编辑脚本重建 vs Wagner-Fischer \(O(NM)\) 编辑距离对拍(300
组随机串 +
map_match_pacing.py:- Newson–Krumm (2009) HMM + Viterbi 地图匹配在道路分叉/天桥噪音序列上的验证,以及与 \(3^5\) 暴力路径枚举的对拍;
- 24 小时波动流量(含突发峰与高价值夜间流量)下,离线 0-1 背包上界、固定 \(\lambda\) 与 PID 预算 pacing 的对比模拟。
plot_industry.py:汇总生成../industry-dp-plots.svg。- 运行方式:
bash run.sh源码下载
本文相关源码已整理,共 4 个文件。