QuatumQuill

贪心与随机贪心

从当前活张量对逐步构造完整路径，并说明 trial、seed、温度采样和线程之间的关系。

本页目录

贪心路径生成过程

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

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

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

三个候选的局部得分。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 运行一次；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 入口

确定性贪心与随机贪心

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 并行与顺序依赖

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

API 层级

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

下载原始 Markdown 文档 ↓