---
title: "动态规划与超图二分"
description: "说明 exact subset dynamic programming、递归超图二分与 fixed-leaf-order interval dynamic programming 的状态空间和调用关系。"
eyebrow: "寻路算法"
---

## 结构化搜索方法的关系 {#state-spaces}

`optimal_dp`、`bisect` 与 `order_dp` 是三个独立入口，状态空间和输入条件不同。前两者从网络构造路径；`order_dp` 接收一份包含全部输入张量的 leaf order。

| 入口 | 首先决定什么 | 路径怎样产生 | 复用关系 |
| --- | --- | --- | --- |
| optimal\_dp | connected tensor subset 的拆分 | 从 DP 表回溯完整 SSA path | 被 bisect 的小块求解复用 |
| bisect | 张量超图的递归二分 | 直接把递归分区树接成收缩树，小块交给 exact DP | cutoff 小块调用 optimal\_dp |
| order\_dp | 给定叶序中的连续区间 | 保持叶序不变，只选择二叉括号结构 | 可从已有路径提取 leaf order 后单独调用 |

> **API 层级**
>
> 这些低层算法是独立 API；Light 与 Heavy 的内部组成不属于这些入口的接口定义。

## optimal\_dp：位掩码表示的精确子集动态规划 {#optimal-dp}

`optimal_dp` 用一个 `u64` bit 表示一个输入张量。它先把共享腿连通分量分别求解：对每个连通子集保存当前 objective 下的最佳代价、自由腿和最佳左右拆分；随后再用 exact outer-product DP 合并各分量根。

两种 DP 都优化二叉收缩结构，但状态空间不同：optimal\_dp 使用 connected tensor subsets；order\_dp 只使用给定叶序中的连续区间。

```diagram
subset-dp-transition
一个 connected-subset 表项的更新：对同一 S 枚举合法左右拆分，比较子问题代价与当前收缩步代价之和，并保存用于回溯的最佳拆分。
```

| 限制 | 含义 |
| --- | --- |
| u64 表示 | 最多表示 64 个输入张量 |
| max\_n | 调用者显式传入的指数工作量保护；超过时返回 Err |
| DEFAULT\_MAX\_N=26 | 库中提供的默认常量；不表示 optimal\_dp 会忽略调用者传入的 max\_n |
| deadline 变体 | 部分 DP 表不能构成完整路径，超时返回 Err 而不是半条路径 |

公开 API 示例

```rust
use arctn::optimal_dp;

let (path, stats) = optimal_dp(&net, 24)?;
```

Connected-subset DP 的填表伪代码；省略 deadline、数值分支和 Rust 借用细节

```rust
// Fill the table in increasing subset size.
for s in 2..=k {
    for i in 1..=s / 2 {
        let j = s - i;
        for &m1 in &by_size[i] {
            let e1_adj = table[&m1].adj;
            for &m2 in &by_size[j] {
                if m1 & m2 != 0 { continue; }
                if i == j && m1 >= m2 { continue; }
                if e1_adj & m2 == 0 { continue; }

                let m = m1 | m2;
                // ... compute total cost and retained result legs ...
                if table.get(&m).is_some_and(|prev| prev.cost <= cost) {
                    continue;
                }
                table.insert(m, Entry {
                    cost, legs: result_legs, adj, left: m1, read_log2,
                });
                // A newly created mask is also recorded in by_size[s].
            }
        }
    }
}
```

> [!WARNING]
> **精确性的边界**
>
> 这里的 exact 只针对实现声明的 connected-subset／outer-product 状态空间和同一 planning objective。它不等于对所有允许任意中途外积的二叉树作无条件全局枚举。

## bisect：递归超图二分 {#bisect}

`bisect` 把张量看作节点，把至少连接两个当前成员的腿看作超边，超边权重使用 `log2(dimension)`。实现经过多层 coarsening、初始划分和 Fiduccia–Mattheyses refinement，再递归处理两侧。

```diagram
tensor-partition-routes
bisect 递归划分张量超图；子问题不超过 cutoff 时，调用固定 PlannerObjective::FIXED 的 optimal_dp 构造局部收缩树。公开 per-call objective 不会传入这个 cutoff DP。
```

```diagram
bisect-refinement
先合并节点并划分，再展开节点、调整两侧成员。图中以移动 C 为例。
```

公开 API；ntrials、cutoff 与 objective 应由调用者按实验协议显式给出

```rust
use arctn::paths::bisect::bisect_with_objective;

let (path, stats) = bisect_with_objective(
    &net,
    ntrials,
    seed,
    cutoff,
    objective,
)?;
```

递归二分与父 SSA 步骤的伪代码；省略局部网络构造

```rust
let hg = build_hg_with(members, &ctx.input_legs, &|leg| {
    ctx.net.log2_dim(leg)
});
let side = multilevel_bipartition(hg, ctx.eps, rng);
let mut a = Vec::new();
let mut b = Vec::new();
for (local, &global) in members.iter().enumerate() {
    if side[local] { b.push(global); } else { a.push(global); }
}
if a.is_empty() || b.is_empty() {
    let half = members.len() / 2;
    a = members[..half].to_vec();
    b = members[half..].to_vec();
}
let (ia, _) = solve(ctx, &a, path, rng)?;
let (ib, _) = solve(ctx, &b, path, rng)?;
path.push((ia.min(ib), ia.max(ib)));
```

公开 `cutoff` 会被限制在 2 到 20 之间。不同 bisection trial 采样不同 imbalance 与 seed，可由 Rayon 并行；一次递归划分内部仍有父子依赖。`bisect_with_objective` 的 per-call objective 只用于在完成的 trials 之间选优，cutoff 内部的 `optimal_dp` 使用固定规划目标。整体 `bisect` 是启发式搜索，cut-net objective 也不等于最终完整路径 objective。断开分量由 smallest-first outer products 合并，而不是复用 `optimal_dp` 的 exact component-root DP。

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

`order_dp` 接收一个包含全部输入张量编号的 leaf order。它只考虑这个顺序中的连续区间，并为每个区间选择最佳左右拆分；因此它可以改变二叉括号结构，但不会重新排列张量叶子。

```diagram
order-dp-transition
固定 leaf order 的上三角 DP 表。每个 C[i,j] 枚举区间内的 split point；图中只用符号说明一次转移，不固定某个网络的实际代价值。
```

| 性质 | 含义 |
| --- | --- |
| 状态 | 给定 leaf order 中的连续区间 \[i,j\] |
| 转移 | 枚举区间内的二叉拆分点，按同一个 PlannerObjective 选优 |
| 复杂度 | O(n³) 时间、O(n²) 内存；公开入口限制 n ≤ 5000 |
| 典型输入 | 由任意合法完整路径提取的 leaf order |

公开 API 示例

```rust
use arctn::paths::ordertree::{leaf_order_of_path, order_dp};

let order = leaf_order_of_path(&net, &existing_path)?;
let (candidate, stats) = order_dp(&net, &order)?;
```

用 reverse Cuthill–McKee 启发式构造 leaf order，再在该固定顺序内求最优括号结构

```rust
use arctn::paths::ordertree::{order_dp_with_objective, rcm_order};

let order = rcm_order(&net);
let (path, stats) = order_dp_with_objective(
    &net, &order, objective
)?;
```

Fixed-leaf-order interval DP 的区间递推伪代码；省略 objective 分支、并行层和 deadline

```rust
for len in 2..=n {
    for i in 0..=(n - len) {
        let j = i + len - 1;
        let (mut best, mut best_k) = (f64::INFINITY, i);
        for k in i..j {
            // ... combine [i,k], [k+1,j], and this step ...
            if total < best {
                best = total;
                best_k = k;
            }
        }
        cost[i * n + j] = best;
        split[i * n + j] = best_k as u32;
    }
}
```

> **两种 DP**
>
> fixed-leaf-order interval DP 与 optimal\_dp 的 connected-subset DP 不是同一种动态规划。前者固定叶序并只考虑连续区间；后者以连通张量子集的 bitmask 为状态。

> [!WARNING]
> **精确性的边界**
>
> `order_dp` 只在给定 leaf order 的二叉括号结构内是 exact。`rcm_order` 是构造叶序的启发式，不会把后续结果变成所有收缩树上的全局最优。