计算机应用研究2021，Vol.38Issue(7) ：1998-2002,2024.DOI:10.19734/j.issn.1001-3695.2020.10.0357

求解最小费用最大流问题的信念传播算法

Belief propagation algorithm for solving minimum cost maximum flow problem

左逢源 王晓峰 牛进 梁晨
计算机应用研究2021，Vol.38Issue(7) ：1998-2002,2024.DOI:10.19734/j.issn.1001-3695.2020.10.0357
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 维普
  • 万方数据

求解最小费用最大流问题的信念传播算法

Belief propagation algorithm for solving minimum cost maximum flow problem

左逢源 1王晓峰 2牛进 1梁晨1
扫码查看

作者信息

  • 1. 北方民族大学 计算机科学与工程学院,银川750021
  • 2. 北方民族大学 计算机科学与工程学院,银川750021;北方民族大学 宁夏智能信息与大数据处理重点实验室,银川750021
  • 折叠

摘要

最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值.针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法.利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解.最后选取若干带权有向图模型进行数值实验,验证了算法的可行性及有效性,且算法在求解效率上优于部分算法.

关键词

最小费用最大流/线性规划/信念传播算法/因子图

引用本文复制引用

基金项目

国家自然科学基金(62062001)

国家自然科学基金(61762019)

国家自然科学基金(61862051)

国家自然科学基金(61962002)

北方民族大学重大专项项目(ZDZX201901)

宁夏自然科学基金(2020AAC03214)

宁夏自然科学基金(2020AAC03219)

宁夏自然科学基金(2019AAC03120)

宁夏自然科学基金(2019AAC03119)

北方民族大学校级科研一般项目(2019XYZJK05)

出版年

2021
计算机应用研究
四川省电子计算机应用研究中心

计算机应用研究

CSTPCDCSCD北大核心
影响因子：0.93
ISSN：1001-3695
被引量1
参考文献量11
段落导航相关论文