QuatumQuill

动态规划与超图二分

说明 exact subset dynamic programming、递归超图二分与 fixed-leaf-order interval dynamic programming 的状态空间和调用关系。

本页目录

结构化搜索方法的关系

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

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

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

bisect 递归划分张量超图；子问题不超过 cutoff 时，调用固定 PlannerObjective::FIXED 的 optimal_dp 构造局部收缩树。公开 per-call objective 不会传入这个 cutoff DP。
先合并节点并划分，再展开节点、调整两侧成员。图中以移动 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 接收一个包含全部输入张量编号的 leaf order。它只考虑这个顺序中的连续区间，并为每个区间选择最佳左右拆分；因此它可以改变二叉括号结构，但不会重新排列张量叶子。

固定 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 是构造叶序的启发式，不会把后续结果变成所有收缩树上的全局最优。

下载原始 Markdown 文档 ↓