基于压入与重标记可提前终止的最大流最小割求解算法

发布者：技术转移办公室发布时间：2021-10-15浏览次数：10

技术主题：后摩尔器件与集成系统

发明名称：基于压入与重标记可提前终止的最大流最小割求解算法

申请时间：2021-04-20

申请号：CN202110421777.5

摘要：本发明提供了一种基于压入与重标记可提前终止的最大流最小割求解算法，用于不需要确切最大流量的应用，其特征在于，由分离条件和稳定条件构成Push‑relabel算法的提前终止条件；在Push‑relabel算法进行过程中的任意时刻，若集合T中不存在源点s，s∈S，则满足分离条件；若集合T中不存在任何活跃节点则满足稳定条件；若分离条件及稳定条件都满足，则Push‑relabel算法终止。本发明提出了一种新颖的提前终止技术，可以大大消除冗余计算，并确保算法在所有情况下都能正确终止。实验结果表明，使用新的终止条件可以在测试数据中将计算量平均减少到原来的2％。