---
title: "贪心与随机贪心"
description: "从当前活张量对逐步构造完整路径，并说明 trial、seed、温度采样和线程之间的关系。"
eyebrow: "寻路算法"
---

## 贪心路径生成过程 {#greedy-loop}

ArcTN 的贪心内核维护活张量、腿的持有者和候选张量对。初始候选只包含至少共享一条腿的张量对；每次收缩后，只为新结果与仍和它共享腿的活张量加入候选。若网络含有互不连通的分量，最后再按张量大小从小到大完成外积合并。

```diagram
greedy-contraction
一次贪心收缩：A、B 沿 b 收缩为 AB，输出指标 a、e 不变。本例取 temperature=0；随机贪心可在候选窗口内按温度权重采样。
```

共享腿结构决定哪些活张量对进入候选集；局部代价用于给当前候选对排序或采样。基础局部代价是 `size(result) - costmod × (size(a) + size(b))`，随机贪心还会使用其他受支持的局部代价变体。各条完整 trial 完成后，再使用本次调用的 `PlannerObjective` 选择返回结果。

```diagram
greedy-candidate-scores
三个候选的局部得分。costmod=1 时，(0,1) 得分最低，因此在零温度下被选中。
```

Greedy 路径生成的核心循环；省略输入校验、错误处理和公开包装层

```rust
let n = net.n_tensors();
let mut st = GreedyState::new(net, costmod, cost_fn);
let mut path: SsaPath = Vec::with_capacity(n.saturating_sub(1));
while let Some((a, b)) = st.choose(temperature, nbranch, rng) {
    st.contract(a, b);
    path.push((a, b));
}

// Finish disconnected components with smallest-first outer products.
let mut rest: Vec<usize> = (0..st.node_legs.len()).filter(|&i| st.alive(i)).collect();
while rest.len() > 1 {
    rest.sort_by(|&x, &y| st.node_size[x].total_cmp(&st.node_size[y]));
    let (a, b) = (rest[0], rest[1]);
    let (a, b) = if a < b { (a, b) } else { (b, a) };
    let new_id = st.contract(a, b);
    path.push((a, b));
    rest.remove(0);
    rest.remove(0);
    rest.push(new_id);
}
```

> [!WARNING]
> **保证边界**
>
> `greedy` 是逐步局部选择，不保证得到局部最优或全局最优的完整收缩树。`random_greedy` 只保证返回显式 `ntrials` 条完整 trial 中、按同一 PlannerObjective 比较后最低的一条。

## greedy 与 random\_greedy {#greedy-vs-random}

| 入口 | 搜索工作 | 随机性 | 返回值 |
| --- | --- | --- | --- |
| greedy | 运行一次；costmod=1、temperature=0、nbranch=1 | 无 | 一条完整路径及其 PathStats |
| random\_greedy | 运行 ntrials 条完整 trial | 每条 trial 使用独立 ChaCha8 随机流 | 按完整路径目标选出的一条最佳路径 |

`random_greedy` 要求 `ntrials >= 1`。trial 0、1、2 分别使用 `costmod=1、4、8` 和零温度作为确定性起点；后续 trial 从各自随机流采样参数，并从堆顶的有限候选窗口进行温度加权采样。

> **两个不同的温度语境**
>
> random\_greedy 的温度控制的是一条贪心路径中每一步怎样从候选张量对采样。它不是收缩树模拟退火的温度，也不表示数值执行温度。

## Rust 入口 {#public-api}

确定性贪心与随机贪心

```rust
use arctn::{greedy, random_greedy};

let (baseline, baseline_stats) = greedy(&net)?;
let (sampled, sampled_stats) = random_greedy(&net, 64, 7)?;
```

```text
greedy(net: &TensorNetwork)
```

| 参数 | 类型 | 说明 |
| --- | --- | --- |
| net | &TensorNetwork | 待规划的张量网络；调用时检查网络是否合法。 |

**返回：** Result\<(SsaPath, PathStats), String\>

```text
random_greedy(net: &TensorNetwork, ntrials: usize, seed: u64)
```

| 参数 | 类型 | 说明 |
| --- | --- | --- |
| net | &TensorNetwork | 待规划的张量网络；调用时检查网络是否合法。 |
| ntrials | usize | 完整候选路径的数量，必须大于零。 |
| seed | u64 | 用于派生各 trial 随机流的种子。 |

**返回：** Result\<(SsaPath, PathStats), String\>

## trial 并行与顺序依赖 {#parallelism}

`random_greedy` 用 Rayon 并行不同 trial。第 i 条 trial 由 `seed + i` 派生随机流，因此线程调度不会改变一条 trial 使用的随机流。增加线程允许同一批 trial 并行执行，不会自动增加 `ntrials`；实际耗时还取决于任务规模、可用核心和调度开销。

- 可以并行：多条彼此独立的完整 trial。
- 必须顺序：一条 trial 内从第 1 步到第 n-1 步的候选选择。
- 固定工作量比较：固定网络、ntrials、seed、objective 和软件版本，再改变线程数。
- 带协作式时间条件的高层 Auto：完成的工作量还可能受运行时序影响，不能与固定 ntrials 混为同一实验。

> **API 层级**
>
> `greedy` 与 `random_greedy` 是独立的低层 API；Light 与 Heavy 的公开契约不包含其内部搜索组合、数量、参数或调度。