跳跃正交表

动态更新更快

一种新的数据结构，用于在权重或位置变化时高效更新最优运输方案，避免了从头重新计算的高昂成本。

Xiaoyang, Xu · 丁虎

2024

参数信息

枢轴查找时间

O(1)

技术优势

枢轴查找 O(1)

利用 2D Skip Orthogonal List 和动态树技术，即使基于单纯形法，也能在期望 O(1) 时间内找到要枢轴的变量。

每次枢轴 O(|V|)

完成每次枢轴操作仅需期望 O(|V|) 时间，其中 V 是所有供需节点的集合。

动态场景更优

实验证明该算法在动态场景下显著优于现有算法。

应用场景

• 机器学习中的最优运输：无需在数据变化后重新训练模型，可即时更新最优传输方案。
• 动态优化：在目标函数或约束动态变化时快速调整解，避免从头求解。
• 数据流处理：以增量方式维护最优传输计划，适合连续流入的数据点更新。