---
title: "收缩树局部搜索"
description: "从已有路径出发，用树旋转、局部 exact DP、模拟退火、treesa_path 或 parallel tempering 继续改进。"
eyebrow: "寻路算法"
---

## 从 SSA path 到收缩树 {#tree-neighborhood}

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

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

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

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

## Subtree reconfiguration 与局部 exact DP {#reconfiguration}

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

```diagram
subtree-reconfiguration
固定局部输入、局部输出腿和窗口外收缩树；内部先在连通子集状态中求解，若有断开的分量，再用精确 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 {#annealing}

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

```diagram
annealing-trajectory
模拟退火维护 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 {#tempering}

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

```diagram
parallel-tempering
图中 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 内达到局部最优或全局最优。这里将副本交换用于启发式优化，不作平衡采样保证。

## 局部改进方法对比 {#selection}

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

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