---
title: "动态规划"
description: "子集动态规划搜索张量子集的组合；区间动态规划在固定叶序下选择括号结构。"
eyebrow: "寻路算法"
---

## 两种动态规划 {#state-spaces}

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

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

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

## 子集动态规划 {#optimal-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)$ 按本次[优化目标](/docs/path-metrics#definition)计算，不是贪心的局部得分。

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

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

## 固定叶序的区间动态规划 {#order-dp}

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

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

对区间 $[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 集合处理的开销。

## 接口与用途 {#interfaces}

`optimal_dp` 用于小网络；`order_dp` 用于调整已有叶序的括号结构，叶序可由 `leaf_order_of_path` 从完整路径提取。函数签名和目标参数见 [Rust API](/docs/rust-api#path-search)。

### 与超图二分的关系 {#bisect}

[超图二分](/docs/bisection#bisect)递归划分网络，在足够小的子问题上调用子集 DP。