[發明專利]基于壓入與重標記可提前終止的最大流最小割求解算法

在審

• 申請號: 202110421777.5
• 申請日: 2021-04-20
• 公開（公告）號: CN113139976A
• 公開（公告）日: 2021-07-20
• 發明（設計）人: 劉心哲;閆光耀;哈亞軍
• 申請（專利權）人: 上海科技大學
• 主分類號: G06T7/11
• 分類號: G06T7/11
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 徐俊;柏子雵

1.一種基于壓入與重標記可提前終止的最大流最小割求解算法，用于不需要確切最大流量的應用，其特征在于，由分離條件和穩定條件構成Push-relabel算法的提前終止條件，在殘差圖中，設可以達到匯點t的所有節點v構成集合T，其余節點構成集合S；在Push-relabel算法進行過程中的任意時刻，若集合T中不存在源點s，s∈S，則滿足分離條件；若集合T中不存在任何活躍節點則滿足穩定條件；若分離條件及穩定條件都滿足，則Push-relabel算法終止，其中：

將分離條件定義為：殘差圖中不存在從源點到匯點的增廣路徑；

將穩定條件定義為：殘差圖中不存在從任一活躍節點到匯點的增廣路徑。

2.一種如權利要求1所述的基于壓入與重標記可提前終止的最大流最小割求解算法的應用，其特征在于，用于僅需要最大流量值或最小割斷但不要求最大流量的應用。