提出通用方法，用极低空间实现宽有界动态规划的最优路径回溯。
Universal Hirschberg for Width Bounded Dynamic Programs
- 通过压缩时间递归树，将回溯空间降至$O(ω\log T)$
- 在序列比对、一维递推等任务中达到近最优空间复杂度
- 适合处理大规模动态规划问题的研究者与算法工程师
Hirschberg 算法（1975）通过网格动态规划的递归中点分割，将最长公共子序列的空间复杂度从 $O(N^2)$ 降低到 $O(N)$。本文证明该思想可推广至一类具有局部依赖关系的动态规划（DP DAG），其拓扑序上的前沿宽度为 $ω$，且入度有界。在标准离线随机访问模型下，假设最大型半环并有确定性平局打破机制，任意此类动态规划可在空间 $O(ω\log T + (\log T)^{O(1)})$ 单元内实现确定性回溯，其中 $T$ 为状态数。新框架以正向重计算替代反向传递，并构建高度压缩的递归树，使每条最优路径必经过小规模“中间前沿”。该方法在非对称和带状序列比对、一维递推及路径宽有界的图上动态规划中均取得近似最优回溯空间。我们还证明在前向单遍模型中 $Ω(ω)$ 空间（比特）不可避免，并讨论流式场景下的 $\sqrt{T}$ 类障碍，表明空间高效回溯是宽有界动态规划图的结构性特征，而非仅限于网格算法。
原文摘要 · Abstract (English)
Hirschberg's algorithm (1975) reduces the space complexity for the longest common subsequence problem from $O(N^2)$ to $O(N)$ via recursive midpoint bisection on a grid dynamic program (DP). We show that the underlying idea generalizes to a broad class of dynamic programs with local dependencies on directed acyclic graphs (DP DAGs). Modeling a DP as deterministic time evolution over a topologically ordered DAG with frontier width $ω$ and bounded in-degree, and assuming a max-type semiring with deterministic tie breaking, we prove that in a standard offline random-access model any such DP admits deterministic traceback in space $O(ω\log T + (\log T)^{O(1)})$ cells over a fixed finite alphabet, where $T$ is the number of states. Our construction replaces backward dynamic programs by forward-only recomputation and organizes the time order into a height-compressed recursion tree whose nodes expose small "middle frontiers'' across which every optimal path must pass. The framework yields near-optimal traceback bounds for asymmetric and banded sequence alignment, one-dimensional recurrences, and dynamic-programming formulations on graphs of bounded pathwidth. We also show that an $Ω(ω)$ space term (in bits) is unavoidable in forward single-pass models and discuss conjectured $\sqrt{T}$-type barriers in streaming settings, supporting the view that space-efficient traceback is a structural property of width-bounded DP DAGs rather than a peculiarity of grid-based algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。