---
title: "超图二分"
description: "通过递归划分张量超图构建收缩树，小规模子问题使用动态规划。"
eyebrow: "寻路算法"
---

## 用划分构建收缩树 {#bisect}

超图二分（hypergraph bisection）把张量作为节点，把共享 index 作为连接相关节点的超边。算法将节点分成两组，递归处理各组，再合并两侧的结果。

普通图的一条边连接两个节点；超图的一条超边可以连接多个节点。例如，同一个 index 同时出现在三个张量中，就用一条超边连接这三个张量。划分决定先在各组内部收缩，再收缩两组的结果。

```diagram
tensor-partition-routes
虚线是一次划分的分界。橙色超边同时连接两侧节点；每条跨侧超边只计一次，不按端点数重复计数。
```

划分时，在两侧规模约束下尽量减少跨侧超边的加权总和：

$$
\operatorname{cut}(L,R)=
\sum_{\substack{e\cap L\ne\varnothing\\e\cap R\ne\varnothing}}
\log_2 d_e.
$$

$d_e$ 是对应 index 的维度。这个划分代价不等于完整路径的 FLOPs 或读写量。划分只用于确定收缩树，**不会删除 index，也不是切片**。

## 递归过程 {#recursion}

先在合并节点后的较小超图上求划分，再逐层展开并调整划分。对每一侧重复这个过程；节点数不超过 `cutoff` 时，改用[子集动态规划](/docs/structured-search#optimal-dp)。

```pseudocode
构建子树(S):
    if S 只有一个张量:
        return 该张量
    if S 的张量数 <= cutoff:
        return 用子集 DP 求得的局部树
    (L, R) = 对 S 做超图二分
    left = 构建子树(L)
    right = 构建子树(R)
    return 合并 left 和 right 得到的树
```

不同随机种子和不平衡参数产生不同候选；多次尝试后，按完整路径的目标值选优。互不连通的分量分别处理，最后按大小进行外积合并。

## 接口 {#interfaces}

`bisect` 使用默认目标；`bisect_with_objective` 可指定比较完整候选的目标。小问题中的 `optimal_dp` 仍使用默认目标 $F+64R$，不是调用者传入的权重。`cutoff` 的范围为 2–20；函数签名见 [Rust API](/docs/rust-api#bisect)。

二分是启发式方法，不保证全局最优。Light 使用二分候选，Heavy 不使用，见 [Light / Heavy 接口](/docs/auto-light-heavy)。