收缩树局部搜索

从已有路径出发，用树旋转、局部 exact DP、模拟退火、treesa_path 或 parallel tempering 继续改进。

本页目录

从 SSA path 到收缩树

SSA path 适合保存和重放；局部搜索先把它转成二叉收缩树。一次树旋转把 ((A B) C) 改为 (A (B C))，或作反向变换。叶子张量和最终表达式不变，变化的是中间张量与括号结构。

旋转前

v=(a,b) · b=(c,d)

局部旋转promote_left· 只重算 b 与 v 的局部代价

旋转后

v=(c,b′) · b′=(a,d)

旋转保留 a、c、d 内部结构，改变它们的组合方式。退火与回火按 Metropolis 准则决定是否接受候选。

图中展示 `promote_left` 局部旋转。叶子与窗口外树不变，只有两个内部节点的组合关系和对应局部代价发生变化。

这些入口都需要一条已有的合法完整路径。它们是在该路径附近搜索，不是从空白网络直接生成第一条路径。

API 层级

树搜索方法是独立的低层 API；Light 与 Heavy 的内部算法、参数、数量和调度不属于这些入口的接口定义。

Subtree reconfiguration 与局部 exact DP

Subtree reconfiguration（子树重构）从树中选择内部节点，向下展开到至多 subtree_size 个 frontier nodes。reconfigure_path 把这些前沿节点当作一个小张量网络的输入，把当前局部根的腿固定为输出，再调用内部的 connected-subset DP 选择新的局部括号结构。候选在当前 objective 下严格改善时才接回原树。

现有树与固定局部窗口

窗口外结构不动；F₀…F₃ 是已收缩子树，不一定是原始张量。

局部边界定义的小网络

inputs: legs[F₀…F₃]
output: legs[v]

将 F₀…F₃ 视为输入张量，保留局部根 v 的输出指标，求解这个小网络的最优组合。

比较局部树

当前局部树J(current)

DP 候选J(candidate)

仅当 J(candidate) < J(current) 时替换；否则保留原树。窗口外的连接保持不变。

固定局部输入、局部输出腿和窗口外收缩树；内部先在连通子集状态中求解，若有断开的分量，再用精确 outer-product DP 合并各分量的根。

固定条件	局部 DP 可以改变的内容
局部窗口外的收缩树	不改变
frontier nodes 代表的已收缩子树	内部结构不展开、不改变
局部根对外保留的腿	固定为小网络 output
同一 per-call objective	在允许的局部二叉结构中选优

公开 API 示例

rust

use arctn::reconfigure_path;

let (improved, stats) = reconfigure_path(
    &net, &initial_path,
    8,   // at most eight frontier nodes
    10,  // at most ten whole-tree sweeps
)?;

局部网络构造与改善判断的伪代码；省略泛型和代价计算

rust

let mini = TensorNetwork {
    name: String::new(),
    inputs: frontier.iter().map(|&f| self.legs[f].clone()).collect(),
    output: self.legs[v].clone(),
    size_dict,
};
let Ok(candidate) = optimal_dp_reconfiguration_core(
    &mini, subtree_size.max(16), self.objective,
) else {
    return Ok(ReconfigureNodeOutcome::default());
};
// ... compare the candidate and incumbent with the same objective ...
if !improved {
    return Ok(ReconfigureNodeOutcome::default());
}

Warning

局部 exact 的适用范围

subtree_size=8 表示至多八个 frontier nodes，不是八个原始输入张量。一个 frontier node 可以代表已经收缩的多张量子树。精确保证只属于固定边界及实现允许路径类内的局部子问题；多轮重构后的整棵树没有全局最优保证。

anneal_path、anneal_paths 与 treesa_path

这些入口实现 simulated annealing（模拟退火）式的局部树搜索；treesa_path 实现 TreeSA-style annealing。不同入口的差别主要在独立链数量、温度日程与推进方式。

current objective

best-so-far

搜索轨迹示意

current可以暂时变差，以离开当前邻域。best-so-far只在严格改善时更新；最终返回历史最好完整路径，并保留输入路径作为回退。

模拟退火维护 current 状态和独立的 best-so-far 快照。current 可以因接受较差旋转而暂时上升；best-so-far 只在出现更低 objective 时更新。曲线是机制示意，不是实测轨迹。

入口	初始路径	内部轨迹	最终返回
anneal_path	一条	一条链；相对温度按几何日程从 t0_rel 向 t1_rel 变化	搜索过程中保留的最佳路径
anneal_paths	一条	chains 条独立退火链，由 Rayon 并行	所有链中最好的一条路径，不是 Vec<SsaPath>
treesa_path	一条	chains 条独立链；逆温度 beta 线性增加并按全树 sweep 推进	所有链中最好的一条路径

anneal_path 对更好的旋转直接接受，对更差的旋转按相对 objective 变化和当前温度计算 Metropolis 概率。treesa_path 使用 objective 的 base-2 logarithm 作为 energy，并按 exp(-beta × delta_E) 接受较差状态。两者都保存历史最好路径，不会把最后停留的热状态直接作为结果。

公开 API；温度、链数和迭代参数应由调用者按实验协议显式给出

rust

use arctn::{anneal_path, anneal_paths};
use arctn::tree::treesa_path;

let (one_chain, one_stats) = anneal_path(
    &net, &initial_path, niters, seed, t0_rel, t1_rel
)?;

let (multi_chain, multi_stats) = anneal_paths(
    &net, &initial_path, chains, niters, seed
);

let (treesa, treesa_stats) = treesa_path(
    &net, &initial_path, chains, beta0, beta1, beta_steps,
    sweeps_per_beta, reconf_interval, reconf_size, seed,
)?;

Metropolis 接受与 best-so-far 更新的伪代码；变量名已简化

rust

let relative_delta = (next - current) / current;
let accept = next <= current
    || rng.gen::<f64>()
        < (-relative_delta / t_rel.max(f64::MIN_POSITIVE)).exp();
if accept {
    tree.rotate_apply(node, promote_left, change);
    if next < best_total {
        best_total = next;
        best_path = tree.to_path();
    }
}

单复数语义

函数名的单复数描述 API 组织方式，不描述返回路径数量。anneal_paths 的复数表示多条独立链；它的输入仍是一条初始路径，输出仍是一条最佳路径。

Warning

返回保证

这些方法可以临时接受较差状态，但最终返回运行期间保存的 best-so-far，并保留输入路径作为回退。因此返回结果在同一 objective 下不会比输入更差；这不等于收敛到局部最优、全局最优或平衡分布。

temper_path 与 temper_paths

Parallel tempering（replica exchange）在固定的几何温度阶梯上维护多个 replicas。每轮先由各 replica 并行执行 moves_per_round 次局部移动，再同步并尝试交换相邻温度下的完整树状态。

P、Q、R、S 表示完整收缩树。交换被接受后，P 在 T₁ 下搜索，Q 在 T₀ 下搜索。

p_accept = min(1, exp((βᵢ − βⱼ)(Eᵢ − Eⱼ)))β=1/T，E=ln(objective)

图中 P、Q 接受交换，R、S 拒绝交换；各条横线对应的温度不变。

入口	初始候选	replica 初始化	停止参数
temper_path	一条路径	所有温度 replica 从同一条路径开始	不暴露 patience；运行给定 rounds
temper_paths	非空的多条路径	在通过验证且具有可旋转节点的初始路径中循环初始化；最冷槽使用第一条符合条件的路径	额外接受 patience；0 表示关闭

相邻状态的交换概率使用逆温度差和两个状态 objective 的自然对数。每个 replica 独立保存自己的历史最好完整路径；函数结束时再与最佳初始路径比较。temper_path 和 temper_paths 都只返回一条最佳路径及其 PathStats。

公开 API；初始路径必须是完整合法的 SSA paths

rust

use arctn::{temper_path, temper_paths};

let (from_one, stats_one) = temper_path(
    &net, &initial_path, n_replicas, rounds, moves_per_round,
    t_min, t_max, reconf_interval, reconf_size, seed,
)?;

let (from_many, stats_many) = temper_paths(
    &net, &initial_paths, n_replicas, rounds, moves_per_round,
    t_min, t_max, reconf_interval, reconf_size, seed, patience,
)?;

相邻 replica exchange 的伪代码；变量名已展开

rust

let mut i = round % 2;
while i + 1 < replicas.len() {
    let ei = replicas[i].energy_log2() * std::f64::consts::LN_2;
    let ej = replicas[i + 1].energy_log2() * std::f64::consts::LN_2;
    let (bi, bj) = (1.0 / temperatures[i], 1.0 / temperatures[i + 1]);
    let p = ((bi - bj) * (ei - ej)).exp();
    if p >= 1.0 || exchange_rng.gen::<f64>() < p {
        replicas.swap(i, i + 1);
    }
    i += 2;
}

n_replicas：replica 数量，每个 replica 对应一个温度。
rounds：局部推进与交换的同步轮数。
moves_per_round：每个 replica 每轮的局部更新步数；启用周期性子树重构时，在规定间隔处以重构替代一次旋转。
t_min / t_max：相对温度阶梯的两端。
reconf_interval / reconf_size：周期性局部子树重构；reconf_interval=0 表示关闭。

Warning

保证边界

各温度保持不变，交换的是完整 replica 状态；不同 replica 的局部更新可以并行，交换发生在轮间同步点。返回值会与最佳初始路径比较，但不保证在给定 rounds 内达到局部最优或全局最优。这里将副本交换用于启发式优化，不作平衡采样保证。

局部改进方法对比

需求	入口
只接受严格改善、希望结果单调不回退	reconfigure_path
一条链、较小的随机局部搜索	anneal_path
同一起点的多条独立退火链	anneal_paths
按逆温度 sweep 整棵树并可周期性重构	treesa_path
一条起点参与 replica exchange	temper_path
多条不同起点共同初始化 replica exchange	temper_paths

并行上限

链、replica 或候选路径之间可以并行；单条链内的旋转、一个 replica 内的 moves，以及 tempering 的轮间交换都有状态依赖。线程数高于可并行对象数时，不会自动产生更多独立搜索。

下载原始 Markdown 文档 ↓