如何寻找可降低动态规划内存开销的最优/约束拓扑排序

对应专业术语 #

你描述的这类最优拓扑排序的标准学术术语为 DAG最小活跃集拓扑排序（Minimum Active Set Topological Sort），也有部分研究将其归类为带拓扑约束的最小割线性排列问题子类。如果你要检索内存优化场景的相关资料，也可以直接搜「DAG峰值内存最小化拓扑排序」作为关键词。

最优排序的实现方案 #

你提出的最小化打开节点数量的问题，已经被证明属于NP难问题，通用DAG没有多项式时间的精确最优解，但工业场景下有成熟的近似方案可以拿到接近最优的效果：

• 你已经在用的Kahn算法框架可以直接调整优先级规则：每次从入度为0的候选节点中，优先选择「处理该节点后新增的打开节点数最少」的节点。具体计算逻辑是统计每个候选节点的后继里还未被标记为打开的数量，选数值最小的优先处理，这个规则可以避免一次性激活大量新节点，有效压低打开节点的峰值。
• 另一个经大量验证有效的启发式是迟调度规则：每次优先选择「从该节点到DAG出口的最长路径最短」的入度为0节点，这种逻辑可以让刚打开的节点尽可能快地被处理关闭，避免长期处于打开状态占用内存。
• 如果你的DAG规模不大（节点数低于1万），也可以用分支定界法求解精确最优解，常规硬件下的计算效率完全够用。

现有测试结果的补充说明 #

你当前测试的几类启发式没有明显优劣，大概率是因为测试用的DAG连通度较高、边数分布相对均匀，这类场景下单纯按总边数排序的规则粒度太粗，拉不开效果差距，换成上面提到的「新增打开节点数最小」规则后，通常能拿到30%以上的优化效果。

内容的提问来源于stack exchange，提问作者Luxii