动态规划

子集动态规划搜索张量子集的组合；区间动态规划在固定叶序下选择括号结构。

本页目录

两种动态规划

动态规划（dynamic programming，DP）先求小问题，再用小问题的结果求大问题。ArcTN 有两种状态划分方式：

方法	一个状态代表什么	搜索范围
`optimal_dp`	一个连通张量子集	该子集允许的二叉拆分
`order_dp`	给定叶序中的一个连续区间	保持叶序不变的二叉括号结构

两者使用不同的状态：optimal_dp 是子集动态规划，order_dp 是区间动态规划。

设 $C(S)$ 是收缩张量集合 $S$ 的最小代价。用 $\mathcal P(S)$ 表示当前搜索范围内允许的拆分： $A$ 、 $B$ 是非空的合法子问题，满足 $A\cup B=S$ 和 $A\cap B=\varnothing$ 。总成本是两侧各自的收缩成本，加上最后合并两侧的成本：

C(S)=\min_{(A,B)\in\mathcal P(S)} \bigl[C(A)+C(B)+c(A,B)\bigr].

$c(A,B)$ 按本次优化目标计算，不是贪心的局部得分。

pseudocode

为单个张量初始化表项
按张量数递增处理连通子集 S:
    枚举 S 的合法左右拆分 (A, B)
    C[S] = C[A] + C[B] + c(A, B) 的最小值
    保存达到该值的拆分
按最佳拆分回溯各连通分量的收缩树
用外积动态规划合并分量根
return 完整路径

optimal_dp 的精确性限于上述搜索范围：先收缩连通子集，再合并互不连通的分量，不枚举任意中间步骤都允许外积的所有树。状态数随网络规模迅速增长，适合小网络；max_n 是整个输入网络的张量数上限。

给定叶序 [A, B, C, D]，可以比较 ((AB)C)D、(AB)(CD) 等括号结构，但不能把叶序改成 [A, C, B, D]。

每次只把连续区间分成左右两段。图中列出整个四张量区间的三个拆分点；每一段再使用已经求出的最佳结果。

对区间 $[i,j]$ ，枚举拆分点 $k$ ：

C(i,j)=\min_{i\le k<j} \left[C(i,k)+C(k+1,j)+c([i,k],[k+1,j])\right].

pseudocode

为每个单张量区间初始化表项
按区间长度递增处理 [i, j]:
    枚举拆分点 k = i, ..., j-1
    C[i,j] = 左段代价 + 右段代价 + 合并代价 的最小值
    保存最佳拆分点
return 从完整区间回溯得到的路径

order_dp 在给定叶序下选择最优括号结构，不保证在所有叶序中最优。它有 $O(n^2)$ 个区间、 $O(n^3)$ 次候选拆分，实际还包括 index 集合处理的开销。

optimal_dp 用于小网络；order_dp 用于调整已有叶序的括号结构，叶序可由 leaf_order_of_path 从完整路径提取。函数签名和目标参数见 Rust API。

超图二分递归划分网络，在足够小的子问题上调用子集 DP。