子树重构
固定局部输入和输出,用动态规划重新组合一棵子树,只采用降低目标值的结果。
本页目录
重新组合局部输入
子树重构(subtree reconfiguration)从已有收缩树中选一处局部根,向下展开得到若干输入节点,再用子集动态规划重新组合它们。
每个局部输入可以是原始张量,也可以是一棵子树的收缩结果。输入各自的内部结构、局部输出 index 和外部连接保持不变;改变的只是这些输入之间的收缩顺序。
当前局部树
DP 候选树
这里只用 index 和维度计算代价,不执行数值收缩。
搜索过程
tree = 初始收缩树
最多进行 max_sweeps 轮:
遍历树中的局部根:
inputs = 展开得到的至多 subtree_size 个局部输入
candidate = 固定局部输出,用子集 DP 求解该小网络
若目标改善超过数值容差,则将 candidate 接回 tree
本轮没有改善时结束
return tree 对应的路径
局部更新采用与完整路径一致的优化目标。只有改善超过数值容差才接受,因此与允许暂时接受较差状态的模拟退火不同。
接口与停止条件
reconfigure_path 接收已有路径、局部大小 subtree_size 和遍历轮数上限 max_sweeps。subtree_size=8 表示至多八个局部输入;每个输入可以是原始张量,也可以代表一棵已有子树。完整签名见 Rust API。
Light 和 Heavy 的最终子树重构还会按相对改善量提前停止:满足最少遍历轮数后,若改善连续低于阈值,就停止继续搜索。没有可接受改善时,也可以自然收敛。
动态规划只对固定输入、输出和允许拆分的局部问题求优,不保证整棵树达到全局最优。