---
title: "子树重构"
description: "固定局部输入和输出，用动态规划重新组合一棵子树，只采用降低目标值的结果。"
eyebrow: "寻路算法"
---

## 重新组合局部输入 {#reconfiguration}

子树重构（subtree reconfiguration）从已有收缩树中选一处局部根，向下展开得到若干输入节点，再用[子集动态规划](/docs/structured-search#optimal-dp)重新组合它们。

每个局部输入可以是原始张量，也可以是一棵子树的收缩结果。输入各自的内部结构、局部输出 index 和外部连接保持不变；改变的只是这些输入之间的收缩顺序。

```diagram
subtree-reconfiguration
F₀…F₃ 是固定的局部输入。图中两棵树保留相同的输入和输出，只有候选的目标值足够低时才替换原树。
```

这里只用 index 和维度计算代价，**不执行数值收缩**。

## 搜索过程 {#search}

```pseudocode
tree = 初始收缩树
最多进行 max_sweeps 轮:
    遍历树中的局部根:
        inputs = 展开得到的至多 subtree_size 个局部输入
        candidate = 固定局部输出，用子集 DP 求解该小网络
        若目标改善超过数值容差，则将 candidate 接回 tree
    本轮没有改善时结束
return tree 对应的路径
```

局部更新采用与完整路径一致的[优化目标](/docs/path-metrics#definition)。只有改善超过数值容差才接受，因此与允许暂时接受较差状态的[模拟退火](/docs/tree-search#annealing)不同。

## 接口与停止条件 {#interfaces}

`reconfigure_path` 接收已有路径、局部大小 `subtree_size` 和遍历轮数上限 `max_sweeps`。`subtree_size=8` 表示至多八个局部输入；每个输入可以是原始张量，也可以代表一棵已有子树。完整签名见 [Rust API](/docs/rust-api#reconfigure-path)。

Light 和 Heavy 的最终子树重构还会按相对改善量提前停止：满足最少遍历轮数后，若改善连续低于阈值，就停止继续搜索。没有可接受改善时，也可以自然收敛。

动态规划只对固定输入、输出和允许拆分的局部问题求优，不保证整棵树达到全局最优。