---
title: "候选树与选择"
description: "说明候选收缩树、完整路径目标函数与最终选择之间的关系。"
eyebrow: "Auto 寻路"
---

## 探索多棵完整收缩树 {#candidate-set}

同一个张量网络通常存在大量可能的二叉收缩树。穷举全部树会很快变得不可行，因此 Auto 采用启发式搜索，在可用资源内尝试构造多棵完整候选树，而不是声称遍历整个搜索空间。

```diagram
auto-candidate-selection
图中候选数量和树形只用于解释未切片路径的有限候选选择，不对应 Light 或 Heavy 的内部配额。
```

> **运行成本**
>
> 启发式搜索只访问有限候选，不会穷举全部收缩树。规划耗时取决于网络、可用资源和搜索配置，因此没有固定的运行时间保证。

> **切片不在本图范围内**
>
> 本图描述未提供 `target_size` 时的普通路径选择。提供 `target_size` 后还会执行切片；`dynamic` 模式允许局部调整路径，因此最终切片结果不再对应原始候选集合上的同一个 `arg min`。

## 统一评分并选择已观察到的最佳候选 {#selection}

候选选择的概念模型

```text
C_done = {本次调用中已经完成并通过验证的完整路径}
P* = arg min J(P)
          P in C_done

J(P) = w_F * F(P) + w_R * R(P)
```

| 符号 | 含义 |
| --- | --- |
| C\_done | 本次调用实际完成并通过验证的完整路径集合；每条路径对应一棵二叉收缩树 |
| J(P) | 调用开始时固定的 PlannerObjective |
| F(P) / R(P) | 完整路径的 FLOPs 与 total read/write complexity |
| P\* | C\_done 中目标值最低的候选；目标值并列时返回其中一条，tie-break 未指定 |

这个有限集合上的 `arg min` 可以严格成立，但它不等价于整个收缩树空间的局部最小值或全局最小值。内部搜索即使进行了局部改进，也不能仅凭返回一棵树就证明严格局部最优。

## 通过公共接口比较多次独立运行 {#public-comparison-code}

多次独立 Auto 调用

```python
from arctn import arctn_schedule

reports = [
    arctn_schedule(
        inputs, output, size_dict,
        preset="light", seed=seed, use_ssa=True,
    )
    for seed in (0, 1, 2, 3)
]
best_observed = min(
    reports,
    key=lambda report: report["planner_objective_score_log2"],
)
print(best_observed["path"])
```

> **多次调用的预算**
>
> 循环中的每个 `seed` 都触发一次独立 Auto 调用；选择 `best_observed` 使用的是四次调用的总搜索预算，不是一次调用内部的四个 trial。