RuView 实时 RF 感知中的次线性最小割算法：从 Stoer-Wagner 到动态维护、流式处理与 Rust 落地

RuView 实时 RF 感知中的次线性最小割算法：从 Stoer-Wagner 到动态维护、流式处理与 Rust 落地

【免费下载链接】RuViewπ RuView turns commodity WiFi signals into real-time spatial intelligence, vital sign monitoring, and presence detection — all without a single pixel of video.项目地址: https://gitcode.com/GitHub_Trending/wi/RuView

本篇技术指南以 05-sublinear-mincut-algorithms.md 为核心骨架，系统梳理 RuView 在 RuvSense 多站感知网格（16 个 ESP32 节点、120 条链路边、20 Hz 更新率）上维护动态 RF 链路图全局最小割的算法选型、原理推导与工程实现。读者读完后将掌握：为什么在 V=16 的小规模图上经典精确算法反而是最优解、惰性重算混合策略如何把平均每帧开销压到 O(E) 量级、以及ruvector-mincut风格的无堆分配 Rust 实现如何在 ESP32-S3 上把单帧延迟控制在微秒级。

1. 问题定义：RF 感知为什么需要最小割

一个 16 节点的 ESP32 多站网格会生成一个 C(16,2)=120 条边的完全加权图，每条边的权重编码两个节点之间的信道状态信息（CSI）衰减或相干度。人体、移动物体与环境变化会持续扰动这些权重。该图的最小割把感知场划分成 RF 耦合最弱的两个区域——这正好对应物理遮挡（人体、墙体、大型物体）对 RF 场的衰减位置，因而直接服务于人体分割、占用计数与异常检测。

给定无向加权图 G=(V,E,w)，w:E→R⁺，全局最小割是把 V 划分成两个非空集合 (S, V\S) 并最小化跨越割的边权总和的划分：

mincut(G) = min_{S⊆V, S≠∅, S≠V} Σ_{(u,v)∈E, u∈S, v∈V\S} w(u,v)

在 20 Hz 更新率下，每帧最小割计算的墙钟预算为50 ms。虽然 V=16、E=120 在通用图算法标准下是小规模，但真正的约束不是问题规模，而是更新频率与平台限制——目标是目标硬件上每帧延迟低于2 ms，而非渐进复杂度上的优越性。该方向在仓库中已有明确落地脉络：ADR-075-mincut-person-separation.md 记录了把固定阈值人数计数器替换为基于子载波时域相关图的谱最小割算法的决策，其动机正是 ESP32 固件多目标计数恒报n_persons=4的缺陷（Issue #348）。

2. 经典最小割复杂度：为什么 V=16 时经典算法反而够用

2.1 Stoer-Wagner 算法（1997）

Stoer-Wagner 通过 V-1 次最大邻接序（Maximum Adjacency Ordering）的 s-t 最小割计算，以 O(VE + V²logV) 时间精确求解全局最小割：

1. 任选起始顶点；
2. 贪心地不断把与当前集合连接最紧的顶点加入，构建最大邻接序；
3. 序中最后两个顶点 (s,t) 定义一条割，记录其权重；
4. 合并 s 与 t，使 |V| 减 1；
5. 重复 V-1 次，返回记录的最小割。

在本图的复杂度核算：V=16、E=120 时 O(VE+V²logV)=O(16×120+256×4)=O(2944)；每轮迭代用优先队列实现为 O(E+VlogV)。Stoer-Wagner 执行 15 个阶段，每阶段最多扫描 120 条边，总工作量约 1800 次边扫描加优先队列操作。在现代硬件上微秒级完成，ESP32 240 MHz 上估算墙钟 50–200 μs，远在预算内。

2.2 Karger 随机收缩算法（1993）

Karger 算法反复随机收缩边并合并端点，直到只剩两个顶点，幸存边即构成一条割；重复 O(V²logV) 次即可高概率得到最小割。单轮收缩用并查集 O(E) 完成，高概率成功的总开销为 O(V²ElogV)，改进实现为 O(V²log³V)。

本图核算：单轮收缩 O(120) 微不足道；1/V 失败概率所需重复次数约 O(256×4)≈1024 次，总操作约 120,000 次边操作。结论：Karger 虽优雅，但重复试验带来的常数因子使它在小 V 时慢于 Stoer-Wagner；其价值要到 V>1000 才显现（随机化可规避确定性最坏情形）。

2.3 Karger-Stein 递归收缩（1996）

Karger-Stein 只收缩到 V/√2 个顶点，然后对两个独立副本递归，把重复次数从 O(V²) 降到 O(V²/2^depth)，总时间 O(V²logV)。本图规模下：总工作量 O(1024)，递归深度 O(logV)=4 层，约 16 个规模为 4 的叶子子问题。在该规模下比 Stoer-Wagner 增加了实现复杂度却没有实际收益。

2.4 经典算法为何充分、又为何不充分

对静态 16 节点图，所有经典算法都在微秒级完成。真正的挑战在于：

1. 更新频率：20 Hz 下每帧 120 条边都变化，需要增量更新而非全量重算；
2. 批处理叠加：若最小割是更大流水线（信号处理、姿态估计）的一环，微秒级开销也会在每帧多次图操作中累积；
3. 规模扩展：未来可能部署 32/64/128 节点。128 节点时 E=8128，Stoer-Wagner 每帧需 O(128×8128+16384×7)≈O(1.15M) 次操作；
4. 多割需求：实际往往需要不止全局最小割，还有多重最小割、Gomory-Hu 树或 k-way 划分。

后续章节正是围绕动态、流式与近似场景展开。

3. 次线性近似：少于 120 次边读取

次线性时间算法运行时间为 o(m)（m=|E|）。m=120 时"次线性"意味着少于 120 次边读取，这在边权重计算昂贵（每条边都要 CSI 处理）、需在完整 CSI 帧处理前快速给出近似答案、或图规模更大（未来部署）时有用。

3.1 随机边采样割估计

最简单的次线性方案：均匀随机采样 k 条边，计算总权重，估计最小割值。依据Karger 采样定理（1994）：若每条边以概率 p=O(logV/(ε²·λ))（λ 为最小割值）独立采样，则高概率下采样图中的每条割经 1/p 缩放后都在原图值的 (1±ε) 范围内。

本场景核算：ε=0.1、V=16 时 p≈O(log16/(0.01·λ))；若 λ≈10（归一化单位），p≈O(40)，即采样 120 条中的约 40 条，仅读取 1/3 边即可得到 (1±0.1) 近似。

1. 以概率 p 采样每条边 2. 在采样图上运行精确最小割（Stoer-Wagner） 3. 结果按 1/p 缩放

关键洞察：Stoer-Wagner 在约 40 条边、16 顶点的稀疏样本上运行 O(16×40)=O(640) 次操作，比全图更快且带可证明的近似保证。

3.2 割稀疏化（Cut Sparsifiers）

Benczur-Karger（1996）证明 O(VlogV/ε²) 条边足以在 (1±ε) 内保持所有割值。V=16、ε=0.1 时需 O(6400) 条边，超过实际 120 条边，该规模下稀疏化无收益；但扩展到 V=64（E=2016，需约 2560 边，边际节省）、V=128（E=8128，需约 5120 边，节省 37%）、V=256（E=32640，需约 10240 边，节省 69%）时变得关键。

3.3 谱稀疏化（Spectral Sparsification）

Spielman-Srivastava（2011）通过保有效电阻的谱稀疏化保持所有割值：先计算所有边有效电阻 R_e，按 w_e·R_e 成比例采样，再重加权保持期望割值。O(VlogV/ε²) 条边即可，且比组合稀疏化更强——它保持拉普拉斯算子的整个谱而非仅割值。

对 RF 感知的意义：RF 场图拉普拉斯特征向量对应 RF 场的空间模态，谱稀疏化保持这些模态，不仅服务最小割，还服务于断层成像与场建模（见 ruvsense/field_model.rs）。

3.4 查询式次线性算法

Rubinstein-Schramm-Weinberg（2018）提出 O(VpolylogV) 时间的算法，通过查询邻接/权重预言机而非读取全部边。V=16 时约 O(256) 次查询，相对读全 120 边仅 2 倍缩减（此规模无用），但 V=256 时从 32640 降到约 4000 次查询。

4. 动态最小割：面对每帧 120 条边同时变化

RF 感知中每帧 CSI 更新使全部 120 条边权重同时变化，这是批量动态场景：120 个更新一起到达，然后查询最小割。

4.1 Thorup 动态连通性（2000）

Thorup 证明边连通性（无权最小割）可在每条边更新 O(logV·(loglogV)²) 摊还时间内维护，加权图扩展为每更新 O(polylogV)。本场景：每帧 120 次更新 ×O(120·~16)=O(1920) 摊还工作量，对比 Stoer-Wagner 全量重算 O(2944)。V=16 时节省有限，但摊还意味着有些帧近乎免费（最小割未变时），有些帧代价更高。

4.2 全动态 (1+ε) 近似最小割

Goranci-Henzinger-Thorup（2018）在边插入删除下以 O(polylog(V)/ε²) 摊还更新时间维护 (1+ε) 近似最小割。核心思想：维护不同粒度层级上的割稀疏化层次结构，边权重变化时只更新受影响的稀疏化层，最小割值从最粗层读取。

本场景核算：ε=0.1 时每次边更新 O(log³(16)/0.01)≈O(6400)，120 次批量更新即 O(768,000)——比全量重算还差！这揭示了一个重要实践结论：动态算法渐进性优异但常数因子巨大，在小 V 时主导开销。对 V=16，Stoer-Wagner 全量重算快于任何已知动态算法。

4.3 动态算法何时胜出

当 V>1000 且 E>100,000（摊还 polylog 更新胜过 O(VE)）、稀疏更新（每帧仅少数边变化而非全部 120）、或增量权重变化（小增量便于增量稀疏化更新）时，动态算法才占优。RF 网格的实用中间地带是阈值过滤更新：只重新处理权重相对上一帧变化超过 δ 的边。若 RF 场相对稳定（相对 20 Hz 人移动缓慢），多数边变化极小；每帧仅 10–20 条边超阈值时，局部 Stoer-Wagner 重启或局部修复很有吸引力。

4.4 混合方案：惰性重算

算法：Lazy-Mincut-Update 输入：上一帧最小割 (S*, V\S*)、新边权 w' 输出：更新后的最小割 1. 计算 δ = 跨越 (S*, V\S*) 的边 |w'(e)-w(e)| 之和 2. 若 δ < ε·mincut_value： 原样返回 (S*, V\S*) // 割值变化可忽略 3. 计算 crossing_weight = 跨越 (S*, V\S*) 的边 w'(e) 之和 4. 若 crossing_weight == mincut_value ± ε： 更新 mincut_value = crossing_weight // 同一割，调整数值 返回 (S*, V\S*) 5. 否则： 在 G'=(V,E,w') 上运行完整 Stoer-Wagner // 全量重算 返回新最小割

实践中步骤 1–4 覆盖 >90% 的帧（最小割划分在空间上稳定——人不会瞬移），仅当有人穿越割边界时才触发全量重算。平均每帧开销降为 O(E)=O(120) 的穿越边权重评估加偶发 O(VE) 重算。该惰性失效思想正是文档第 8 节 Rust 实现中update_frame批量更新的工程原型。

5. 流式算法：CSI 异步到达时的有限内存估计

流式模型中边逐个到达（或来自多个 ESP32 节点的流），需用 O(VpolylogV) 而非 O(V²) 的工作内存估计最小割。相关场景：16 节点通过 TDM（时分复用）异步到达 CSI 数据；协调器无法先缓冲全部 120 条边权重；ESP32-S3 仅有 512 KB SRAM。

5.1 单遍流式

Ahn-Guha-McGregor（2012）证明单遍流式算法可维护图的线性草图（linear sketch），用 O(VpolylogV/ε²) 空间计算 (1+ε) 近似最小割：

1. 每个顶点 v 维护其关联边权重的稀疏随机线性组合；
2. 草图规模每顶点 O(log²V/ε²)；
3. 由草图近似任意划分的割值。

本场景核算：每顶点空间 O(16/0.01)=O(1600) 个数≈6.4 KB，总空间 O(16×6400)=O(102,400) 个数≈400 KB——能放进 ESP32-S3 SRAM，但留给其他状态的空间所剩无几。

5.2 多遍流式

k 遍扫描可提升精度：O(logV) 遍足以用 O(VpolylogV) 空间精确计算最小割。实用两遍算法：

第 1 遍：按估计有效电阻成比例采样边，构建割稀疏化器 第 2 遍：基于第一遍估计做重要性采样精化稀疏化器 结果：从精化稀疏化器得到 (1+ε) 近似最小割

对 TDM 协议，16 节点完整 CSI 扫描即"一遍"。两遍方案需两个连续 TDM 周期（20 Hz 下共 100 ms）构建并精化稀疏化器——若能容忍初始估计 100 ms 延迟则可接受。

5.3 旋转门流式（Turnstile）

旋转门模型中边权可增可减，正好匹配 CSI 相干度波动的 RF 感知。Ahn-Guha-McGregor（2013）扩展草图方法至此模型：L0 采样草图允许从草图差分恢复边，支持动态割估计，空间复杂度 O(V·polylog(V)/ε²)。对 RF 感知，这意味着可以维护一个运行中的草图，边权重更新随各节点到达即时处理，无需存储全图，天然容纳 RF 场的连续权重波动。

5.4 ESP32 网格的草图架构

ESP32 节点 i： - 计算到所有其他节点的链路 CSI - 构建入射边的局部草图 S_i - 传输 S_i 给协调器（紧凑：约 400 字节） 协调器： - 接收 S_1, ..., S_16 - 合并草图：S = merge(S_1, ..., S_16) - 从 S 提取近似最小割 - 延迟由网络往返主导，而非计算

该架构把草图计算分布到各节点，降低协调器负载，且即使部分节点上报延迟或缺失也能做近似最小割估计。

6. 图稀疏化：当作噪声滤波器使用

6.1 Benczur-Karger 割稀疏化（1996）

定理：任意无向加权图 G（V 个顶点）存在一个 O(VlogV/ε²) 条边的子图 H，使每个割 (S,V\S) 满足 (1-ε)·w_G(S,V\S) ≤ w_H(S,V\S) ≤ (1+ε)·w_G(S,V\S)。

构造算法：

1. 每条边 e 计算其强连通度 c_e（使用权重 ≥ w_e 的边时两端点间边不相交路径的最大数）；
2. 以概率 p_e=min(1, C·logV/(ε²·c_e))（C 为适当常数）采样每条边；
3. 重加权采样边：w_H(e)=w_G(e)/p_e。

强连通度的计算需 O(VE) 时间的最大流——与直接解最小割同价；但可用稀疏化自身（自举）在 O(Elog³V) 内计算近似强连通度。

6.2 应用到 RF 图

16 节点 RF 图上静态稀疏化无必要（E=120 已很小），但稀疏化可作为噪声滤波器：

1. 强连通度高的边（通过多条独立高权路径连接的节点）结构上重要；
2. 强连通度低的边可能代表噪声或不稳定 RF 链路；
3. 按强连通度采样自然弱化不可靠链路。

RF 实用算法：

1. 用 2-3 轮随机生成树采样计算每条边的近似连通度 2. 连通度低于阈值的边标记为"不可靠" 3. 在可靠边子图上运行最小割 4. 若最小割用到不可靠边，在全图上重算

通常把有效边数从 120 降到 60–80，Stoer-Wagner 提速 1.5–2 倍。

6.3 更新下的稀疏化维护

增量更新（Abraham-Durfee 等，2016）：增量维护强连通度估计；边权重变化超过 (1+ε) 因子时更新其采样概率并重新决定是否保留，摊还成本每边更新 O(polylogV)。

RF 批量更新策略：

每帧： 1. 从 CSI 处理接收新边权 w' 2. 稀疏化器中的每条边 e： a. 若 |w'(e)-w(e)|/w(e) > ε：标记重新评估 3. 重新评估标记边（更新采样决策） 4. 在更新后的稀疏化器上运行最小割

预计每帧重新评估 10–30 条边；约 70 边、16 顶点的稀疏化器最小割为 O(16×70)=O(1120) 次操作。

6.4 谱稀疏化与拉普拉斯算子

RF 网格的图拉普拉斯 L_G 编码完整空间耦合结构，其特征值与割值直接相关：λ₂（代数连通度）是归一化最小割的下界；Fiedler 向量（λ₂ 的特征向量）近似最小割划分。谱稀疏化保持所有特征值：

(1-ε)·L_G ≤ L_H ≤ (1+ε)·L_G （Loewner 序）

这严格强于割稀疏化，保持：割值（用于最小割）、有效电阻（用于 field_model.rs 断层成像）、随机游走分布（用于 pose_tracker.rs 跟踪）、热核（用于 gesture.rs 手势识别）。对 RuvSense 流水线，谱稀疏化器一石二鸟：最小割计算与空间场建模。

7. 局部划分：从种子顶点做局部探索

经典最小割算法是全局的——检查整张图。局部划分算法只探索图的一小片区域，运行时间正比于割较小一侧的规模而非全图。RF 感知中，想检测局部遮挡（站在某区域的人）时无需扫描整个 120 边图。

7.1 Spielman-Teng 局部划分（2004）

通过截断随机游走实现局部图划分：

1. 从种子顶点 v 启动随机游走；
2. 每步计算游走分布向量 p；
3. 沿 p(u)/degree(u) 排序的顶点做"扫描割"，找到电导（conductance）最优的割；
4. 游走扩散覆盖 O(|S|) 个顶点（|S| 为目标较小侧）时终止。

复杂度：O(|S|·polylogV/φ)，φ 为目标电导，算法从不检查远离种子的顶点。RF 场景：若已知（或怀疑）某人在节点 {3,7,8} 附近，从这些节点播种游走；完全图上游走会遍历邻居，但权重使其集中在受影响最强的区域；期望工作量 O(4·polylog(16)/φ)≈O(64/φ)，φ=0.3 时约 200 次操作。

7.2 个性化 PageRank 局部割

Andersen-Chung-Lang（2006）用个性化 PageRank（PPR）精化局部划分：

ApproximatePPR(seed, alpha, epsilon): p = 零向量 // PPR 估计 r = indicator(seed) // 残差 只要存在 r(v)/degree(v) > epsilon 的 v: Push(v): p(v) += alpha * r(v) 对 v 的每个邻居 u: r(u) += (1-alpha) * r(v) / (2 * degree(v)) r(v) = (1-alpha) * r(v) / 2 返回 p

性质：运行时间 O(1/(alpha·epsilon))，与图规模无关；p 向量经扫描割后产生种子附近的低电导割；alpha 控制局部性——alpha 越大越局部、越小越全局。RF 场景：alpha=0.15（标准 PageRank 阻尼）产生适合人体分割的半全局割；alpha=0.5 产生高度局部割，适合检测哪些具体链路被衰减；epsilon=0.01 时约 O(1/(0.15×0.01))=O(667) 次 push 操作。

7.3 与 RuvSense 姿态跟踪器集成

pose_tracker.rs 维护卡尔曼滤波的人体位置估计（17 关键点、6 维状态、常速度模型）。当跟踪器预测某人靠近某些节点时，局部划分可快速确认或精化检测：

1. 跟踪器预测某人在节点 {5, 9, 12} 附近 2. 从每个预测节点以 alpha=0.3 运行 PPR 3. 对 PPR 向量做扫描割寻找局部割 4. 若局部割电导 < 阈值： 在预测位置确认有人 5. 把割边界反馈给跟踪器作为量测更新

这形成反馈回路：跟踪器引导图算法、图算法精化跟踪器——运行时间 O(1/alpha/epsilon) 而非全最小割的 O(VE)。

7.4 多种子局部划分

多人场景下从多个种子同时运行局部划分。k 个人、V=16 时，每人的局部划分探索约 4–6 个节点，总工作量约 O(k×6×degree)=O(k×90)。k=3 时约 O(270)，不足全量 Stoer-Wagner 的一半。重叠划分的处理有两种方案：

1. 顺序剥离：找最强局部割，移除这些节点，重复；O(k) 轮且每轮更便宜；
2. 多商品流松弛：用局部 PPR 向量作近似流求解多商品流 LP 松弛；更贵但正确处理重叠。

8. 随机化方法：Monte Carlo 与 Las Vegas 的正确取舍

Monte Carlo 算法：返回答案以概率 ≥1-δ 正确，运行时间固定、精度概率化。Las Vegas 算法：始终返回正确答案，运行时间概率化（期望多项式）、正确性有保证。

对安全关键的 RF 感知（经wifi-densepose-mat的群体伤亡评估，参见 ADR-001-wifi-mat-disaster-detection.md），优先 Las Vegas：最小割答案永远正确，即使偶尔慢。

8.1 Karger Monte Carlo 最小割

Karger 收缩算法是 Monte Carlo：单次试验以 ≥2/V²=2/256≈0.78% 概率找到最小割。运行 O(V²logV) 次试验把成功概率提升到 1-1/V。可靠性放大：δ=10⁻⁶ 失败概率需 V²·ln(1/δ)/2=256×14/2=1792 次试验；每次 O(V) 次收缩=O(16) 次操作；总计 O(28,672) 次操作≈现代硬件 0.1 ms。

8.2 Karger-Stein 早期终止

Karger-Stein 递归收缩可加早期终止启发式：

Karger-Stein-ET(G, best_known_cut): 若 |V(G)| <= 6: 暴力法返回精确最小割 把 G 收缩为 |V'| = |V|/√2 + 1 的 G' 若 crossing_edges(G') > best_known_cut * (1 + epsilon): 剪枝此分支 // 不可能优于已知最优 对 G' 的两个独立副本递归 返回递归结果的较小者

剪枝提前剔除分支、降低期望工作量。V=16 时极少起作用，但 V>100 时可把常数因子降低 2–5 倍。

8.3 Las Vegas 化与验证代价

把 Karger 转成 Las Vegas：运行 Karger 直到找到一条割，然后用最大流验证（割两端各取一顶点算最大流）；若最大流等于割值，由最大流最小割定理该割即最小割，否则继续。验证代价：单次最大流 O(VE)=O(1920)，成功前期望验证次数 O(V²/2)=O(128)——代价高昂，不建议实时使用。更佳方案：用 Stoer-Wagner（确定性、永远正确），随机化方法留给近似或多割计算。

8.4 安全关键系统的可靠性分析

对 MAT（群体伤亡评估工具），最小割错误可能意味着漏掉幸存者。可靠性需求分级：

建议：所有安全关键应用用确定性 Stoer-Wagner；Monte Carlo 近似仅用于手势识别或活动分类等非关键任务（漏一帧可接受）。

8.5 多路割的随机取整

k-way 划分（分离 k 个人）可用随机化 LP 取整：解 k-way 割问题的 LP 松弛，把分数分配随机取整为整数（每个顶点归入 k 组之一），期望近似比 2-2/k。k=3 时近似比 4/3≈1.33，k=5 时 8/5=1.6。这对已知人数下的实时人体分割很实用。

9. Rust 实现：为 RuVector 基础设施打造的ruvector-mincut

9.1 设计原则

实现面向ruvector-mincutcrate——该 crate 已在metrics.rs提供DynamicPersonMatcher（ADR-075 记载其已集成进训练流水线wifi-densepose-train/src/metrics.rs），最小割算法需与既有基础设施干净集成。关键约束：内循环无堆分配（ESP32 兼容）；支持no_std加可选alloc面向嵌入式；用 Rust 类型系统做编译期图规模校验；用 SIMD（std::simd或packed_simd2）批量边权更新。

9.2 数据结构：固定尺寸邻接矩阵

/// 编译期定规模的完全图邻接矩阵。 /// V = 16 节点，存为上三角（120 项）。 pub struct RfGraph<const V: usize> { /// 按上三角顺序存储的边权。 /// 边 (i, j) 且 i < j 的下标：i * (2*V - i - 1) / 2 + (j - i - 1) weights: [f32; V * (V - 1) / 2], /// 缓存的最小割值（权重更新时失效）。 cached_mincut: Option<f32>, /// 缓存的最小割划分（位向量：第 i 位为 1 表示节点 i 在集合 S 中）。 cached_partition: Option<u32>, }

V=16 时权重占 120×4=480 字节，加 8 字节缓存值，共 488 字节——可装进一对缓存行。

/// Stoer-Wagner 可复用状态。预分配以避免每次调用分配。 struct StoerWagnerState<const V: usize> { /// 已合并顶点集（并查集）。 parent: [u16; V], /// 最大邻接序的 key 值。 key: [f32; V], /// 顶点是否在当前工作集中。 active: [bool; V], /// 迄今找到的最优割。 best_cut: f32, /// 迄今找到的最优划分。 best_partition: u32, }

9.3 Stoer-Wagner 实现

impl<const V: usize> RfGraph<V> { /// 用 Stoer-Wagner 计算精确全局最小割。 /// 稠密图时间 O(V^3)（V^2 阶段，每阶段 V 工作量）。 /// V=16 时约 4000 次操作，估算 10-50 us。 pub fn minimum_cut(&mut self) -> (f32, u32) { if let Some(val) = self.cached_mincut { return (val, self.cached_partition.unwrap()); } let mut state = StoerWagnerState::new(); let mut merged: [[f32; V]; V] = self.build_adjacency_matrix(); let mut best_cut = f32::MAX; let mut best_partition: u32 = 0; for phase in 0..(V - 1) { let (s, t, cut_weight) = self.maximum_adjacency_phase( &mut merged, &mut state, V - phase ); if cut_weight < best_cut { best_cut = cut_weight; best_partition = state.current_partition(t); } // 合并 s 和 t self.merge_vertices(&mut merged, s, t); } self.cached_mincut = Some(best_cut); self.cached_partition = Some(best_partition); (best_cut, best_partition) } }

9.4 增量更新路径：惰性失效

impl<const V: usize> RfGraph<V> { /// 更新边权并判断最小割是否需要重算。 /// 返回 true 表示缓存最小割仍然有效。 pub fn update_edge(&mut self, i: usize, j: usize, new_weight: f32) -> bool { let idx = self.edge_index(i, j); let old_weight = self.weights[idx]; self.weights[idx] = new_weight; // 检查这条边是否跨越缓存的划分 if let Some(partition) = self.cached_partition { let i_side = (partition >> i) & 1; let j_side = (partition >> j) & 1; if i_side != j_side { // 边跨越割——必须更新割值 if let Some(ref mut cut_val) = self.cached_mincut { *cut_val += new_weight - old_weight; // 割值变了但划分可能仍最优 // 保守起见：若变化超过 ε * cut_val 则失效 if (new_weight - old_weight).abs() > 0.1 * *cut_val { self.cached_mincut = None; self.cached_partition = None; return false; } return true; } } // 边不跨越割——划分仍有效， // 但割值可能不再是全局最小 // 启发式：权重显著下降则失效 if new_weight < old_weight * 0.8 { self.cached_mincut = None; self.cached_partition = None; return false; } return true; } false } /// 从新 CSI 帧批量更新所有边。 /// 惰性重算：仅当缓存割被失效时才重算。 pub fn update_frame(&mut self, new_weights: &[f32; V * (V - 1) / 2]) { let mut needs_recompute = false; for idx in 0..new_weights.len() { let old = self.weights[idx]; let new_w = new_weights[idx]; self.weights[idx] = new_w; if !needs_recompute { if let Some(partition) = self.cached_partition { let (i, j) = self.edge_vertices(idx); let crosses = ((partition >> i) ^ (partition >> j)) & 1 == 1; if crosses && (new_w - old).abs() > 0.05 * self.cached_mincut.unwrap_or(1.0) { needs_recompute = true; } if !crosses && new_w < old * 0.7 { needs_recompute = true; } } else { needs_recompute = true; } } } if needs_recompute { self.cached_mincut = None; self.cached_partition = None; } } }

这正是第 4.4 节惰性重算混合方案的类型化落地：跨越割的边权重小变化（阈值 0.05×cut_val）只更新缓存割值，不触发全量重算；非跨越边大幅下降（<0.7×old）或跨割边大幅变化才失效缓存。

9.5 SIMD 加速权重更新

#[cfg(target_arch = "x86_64")] use std::arch::x86_64::*; impl<const V: usize> RfGraph<V> { /// 用 SSE 一次更新 4 条边权。 /// 120 条边在 30 次 SIMD 迭代中处理完。 #[cfg(target_arch = "x86_64")] pub unsafe fn update_weights_simd( &mut self, new_weights: &[f32; V * (V - 1) / 2] ) { let n = V * (V - 1) / 2; let mut i = 0; while i + 4 <= n { let old = _mm_loadu_ps(self.weights.as_ptr().add(i)); let new_v = _mm_loadu_ps(new_weights.as_ptr().add(i)); _mm_storeu_ps(self.weights.as_mut_ptr().add(i), new_v); // 为缓存失效检查计算绝对差 let diff = _mm_sub_ps(new_v, old); let abs_diff = _mm_andnot_ps(_mm_set1_ps(-0.0), diff); let threshold = _mm_set1_ps(0.05); let exceeds = _mm_cmpgt_ps(abs_diff, threshold); if _mm_movemask_ps(exceeds) != 0 { self.cached_mincut = None; self.cached_partition = None; } i += 4; } // 处理剩余边 while i < n { self.weights[i] = new_weights[i]; i += 1; } } }

9.6 Rayon 并行：面向更大部署

V>32 时 Stoer-Wagner 的最大邻接序可并行化：并行 key 更新（各线程写不同 key[v]，用 unsafe 注明安全性），顺序找最大 key（V 小故保持顺序）。

#[cfg(feature = "parallel")] use rayon::prelude::*; impl<const V: usize> RfGraph<V> where [(); V * (V - 1) / 2]:, { /// 并行最大邻接序阶段。跨线程拆分 key 值计算。 #[cfg(feature = "parallel")] fn parallel_max_adjacency_phase( &self, merged: &[[f32; V]; V], active: &[bool; V], n_active: usize, ) -> (usize, usize, f32) { let mut in_set = [false; V]; let mut key = [0.0f32; V]; let mut order = Vec::with_capacity(n_active); // 从第一个活动顶点开始 let start = active.iter().position(|&a| a).unwrap(); in_set[start] = true; order.push(start); // 并行更新 key for _ in 1..n_active { let last_added = *order.last().unwrap(); (0..V) .into_par_iter() .filter(|&v| active[v] && !in_set[v]) .for_each(|v| { // 安全性：每个线程写入不同的 key[v] unsafe { let key_ptr = &key[v] as *const f32 as *mut f32; *key_ptr += merged[v][last_added]; } }); // 找最大 key（顺序——V 很小） let next = (0..V) .filter(|&v| active[v] && !in_set[v]) .max_by(|&a, &b| key[a].partial_cmp(&key[b]).unwrap()) .unwrap(); in_set[next] = true; order.push(next); } let t = order[n_active - 1]; let s = order[n_active - 2]; let cut_weight = key[t]; (s, t, cut_weight) } }

9.7 与 DynamicPersonMatcher 集成

ruvector-mincut的DynamicPersonMatcher（src/metrics.rs）用最小割做人体分割。pose_tracker.rs 的头注释确认了检测-跟踪关联正是经由ruvector-mincut::DynamicPersonMatcher实现。集成调用链如下：

use wifi_densepose_signal::rf_graph::RfGraph; impl DynamicPersonMatcher { /// 用新 CSI 数据更新 RF 图并检测人体边界。 pub fn update_with_csi_frame( &mut self, csi_weights: &[f32; 120], // 16 节点完全图 ) -> Vec<PersonSegment> { // 更新图权重（惰性失效） self.rf_graph.update_frame(csi_weights); // 取当前最小割 let (cut_value, partition) = self.rf_graph.minimum_cut(); // 把划分位掩码转为人段 let segments = self.partition_to_segments(partition, cut_value); // 把人段喂给卡尔曼跟踪器 for segment in &segments { self.pose_tracker.update_measurement(segment); } segments } /// 多人分层多割。 /// 递归二分图直到所有段内部连通性超过阈值。 pub fn hierarchical_cut( &mut self, max_people: usize, ) -> Vec<PersonSegment> { let mut segments = vec![Segment::all(16)]; let mut result = Vec::new(); while let Some(segment) = segments.pop() { if segment.size() <= 2 || result.len() >= max_people { result.push(segment); continue; } // 为该段构建子图 let subgraph = self.rf_graph.subgraph(&segment.nodes); let (cut_value, partition) = subgraph.minimum_cut(); // 归一化割阈值：cut_value / min(|S|, |V\S|) let smaller_side = partition.count_ones().min( (segment.size() as u32 - partition.count_ones()) ); let normalized_cut = cut_value / smaller_side as f32; if normalized_cut > self.connectivity_threshold { // 段内部连接良好——一个人或空房间 result.push(segment); } else { // 拆成两个子段继续 let (left, right) = segment.split(partition); segments.push(left); segments.push(right); } } result } }

9.8 性能基准目标

20 Hz 预算：每帧 50 ms。V=16 时所有操作都从容落在预算内；V=128 时全量分层多割逼近预算，此时应启用前文的流式/近似方法。

9.9 测试策略

#[cfg(test)] mod tests { use super::*; /// 在已知最小割的图上验证 Stoer-Wagner。 #[test] fn test_stoer_wagner_known_graph() { let mut graph = RfGraph::<8>::from_edges(&[ (0, 1, 2.0), (0, 4, 3.0), (1, 2, 3.0), (1, 4, 2.0), (1, 5, 2.0), (2, 3, 4.0), (2, 6, 2.0), (3, 6, 2.0), (3, 7, 2.0), (4, 5, 3.0), (5, 6, 1.0), (6, 7, 3.0), ]); let (cut_val, _) = graph.minimum_cut(); assert!((cut_val - 4.0).abs() < 1e-6); } /// 验证惰性更新正确性：跨割边权重大幅变化 /// 时缓存失效触发重算。 #[test] fn test_lazy_update_invalidation() { /* ... */ } /// 验证 SIMD 与标量路径产生相同结果。 #[test] fn test_simd_scalar_equivalence() { /* ... */ } /// 基准：20 Hz 下 10,000 帧随机权重扰动。 /// 验证 V=16 时平均每帧时间 < 100 us。 #[test] fn bench_20hz_sustained() { /* ... */ } /// 性质测试：最小割值 <= 最小顶点加权度。 #[test] fn prop_mincut_bounded_by_min_degree() { /* ... */ } }

测试覆盖四类：已知图正确性、惰性失效语义、SIMD/标量等价性、以及 20 Hz 持续运行下的性能预算与性质不变式（最小割值不超过最小顶点加权度，这是图论中可直接验证的上下界关系）。

10. 总结与推荐架构

10.1 算法选择矩阵

10.2 RuVector 推荐架构

主路径（V ≤ 32）：

1. 接收 CSI 帧；
2. SIMD 批量更新边权；
3. 惰性检查：缓存划分仍有效则直接返回缓存结果；
4. 失效则运行 Stoer-Wagner（精确、确定、够快）；
5. 缓存结果供下一帧。

次路径（V > 32 或需多割）：

1. 用跟踪器预测播种的 PPR 局部划分；
2. 局部割低电导则返回局部结果；
3. 否则回退全量 Stoer-Wagner。

安全关键路径（MAT/生命体征）：

1. 始终用 Stoer-Wagner（确定、精确）；
2. 用第二次 Karger 试验交叉验证（独立验证）；
3. 结果不一致时取较小割值（保守）。

10.3 未来工作

1. 分布式最小割：每个 ESP32 节点计算其局部视图草图，协调器合并草图得到近似全局最小割——降低协调器瓶颈并支持优雅降级；
2. GPU 加速最小割：云托管部署中把多帧批进 GPU 内核，跨时间窗并行 Stoer-Wagner；
3. 学习增强算法：训练小神经网络从 CSI 特征预测最小割划分，以精确 Stoer-Wagner 为真值；网络 O(1) 预测、Stoer-Wagner 周期性验证；
4. 超图最小割：把多体 RF 交互（三个及以上节点同时受影响）建模为超边，超图最小割捕获高阶空间结构。

11. 参考资料

1. Stoer, M. and Wagner, F. "A Simple Min-Cut Algorithm." JACM 44(4), 1997.
2. Karger, D. "Global Min-Cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm." SODA, 1993.
3. Karger, D. and Stein, C. "A New Approach to the Minimum Cut Problem." JACM 43(4), 1996.
4. Benczur, A. and Karger, D. "Approximating s-t Minimum Cuts in O(n²) Time." STOC, 1996.
5. Spielman, D. and Teng, S. "Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems." STOC, 2004.
6. Spielman, D. and Srivastava, N. "Graph Sparsification by Effective Resistances." STOC, 2008 / SICOMP, 2011.
7. Andersen, R., Chung, F., and Lang, K. "Local Graph Partitioning using PageRank Vectors." FOCS, 2006.
8. Ahn, K.J., Guha, S., and McGregor, A. "Analyzing Graph Structure via Linear Measurements." SODA, 2012.
9. Ahn, K.J., Guha, S., and McGregor, A. "Graph Sketches: Sparsification, Spanners, and Subgraphs." PODS, 2012.
10. Thorup, M. "Near-Optimal Fully-Dynamic Graph Connectivity." STOC, 2000.
11. Goranci, G., Henzinger, M., and Thorup, M. "Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time." TALG, 2018.
12. Rubinstein, A., Schramm, T., and Weinberg, S.M. "Computing Exact Minimum Cuts Without Knowing the Graph." ITCS, 2018.
13. Abraham, I., Durfee, D., et al. "Using Petal-Decompositions to Build a Low Stretch Spanning Tree." STOC, 2016.
14. Nanongkai, D. and Saranurak, T. "Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time." FOCS, 2017.

【免费下载链接】RuViewπ RuView turns commodity WiFi signals into real-time spatial intelligence, vital sign monitoring, and presence detection — all without a single pixel of video.项目地址: https://gitcode.com/GitHub_Trending/wi/RuView