---
title: "贪心与随机贪心"
description: "贪心逐步选择张量对；随机贪心生成多条路径，再比较完整路径的目标值。"
eyebrow: "寻路算法"
---

## 贪心：逐步选择张量对 {#greedy-loop}

贪心搜索每次选择一对张量，记录收缩步骤，并用它们的收缩结果替换这两个张量。这里更新的是 index 结构，不执行数组计算。

局部得分的基础形式为：

$$
c(A,B)=|C|-\alpha\bigl(|A|+|B|\bigr).
$$

$C$ 是收缩结果，$|\cdot|$ 是元素数，$\alpha$ 对应 `costmod`。得分越低，候选越优先。这个得分用来选择下一步，不是[完整路径的优化目标](/docs/path-metrics#definition)。

下面的伪代码省略候选集合的维护细节：

```pseudocode
path = []
while 存在共享 index 的候选张量对:
    (A, B) = 局部得分最低的候选
    C = 计算收缩结果的 index 结构
    将 (A, B) 追加到 path
    用 C 替换 A、B，并更新候选
按张量大小从小到大，用外积合并剩余分量
return path
```

共享 index 只有在不属于输出、且不再被其他张量使用时，才会在该步消去。

## 随机贪心：比较多次搜索 {#greedy-vs-random}

`random_greedy` 反复生成完整路径。不同尝试使用不同参数；温度为正时，还会在得分靠前的候选窗口内加权采样，而不总是选择第一名。

```pseudocode
并行执行 ntrials 次尝试:
    parameters = 本次尝试的参数
    path = 按 parameters 生成一条贪心路径
    score = 完整路径的目标值 J(path)
return score 最低的路径
```

前三次尝试（若存在）使用 `costmod=1、4、8` 的零温度起点；后续尝试随机采样参数。不同尝试可以并行，但一条路径内的收缩选择仍逐步进行。

这里的温度控制张量对的选择，与[模拟退火](/docs/tree-search#annealing)中接受树结构变化的温度不同。

## 接口 {#public-api}

| 入口 | 作用 |
| --- | --- |
| `greedy` | 生成一条确定性贪心路径 |
| `random_greedy` | 运行指定次数的尝试，返回目标值最低的路径 |

随机贪心按本次调用的优化目标选择候选路径。在自动调度的 [Light 和 Heavy](/docs/auto-light-heavy) 中，优化目标由顶层接口统一指定；独立调用时，未指定目标则使用库的[默认权重](/docs/path-metrics#definition)。调用方式见 [Rust API](/docs/rust-api#random-greedy)。`ntrials` 至少为 1。贪心与随机贪心都不保证全局最优。

### 并行 {#parallelism}

线程数决定同时运行多少次尝试，不会自动增加 `ntrials`。完整参数与返回类型见 [Rust API](/docs/rust-api#greedy)。