| 求解最小费用最大流问题的信念传播算法 |
| |
| 引用本文： | 左逢源,王晓峰,牛进,梁晨,张丹丹.求解最小费用最大流问题的信念传播算法[J].计算机应用研究,2021,38(7):1998-2002,2024. |
| |
| 作者姓名： | 左逢源 王晓峰 牛进 梁晨 张丹丹 |
| |
| 作者单位： | 北方民族大学 计算机科学与工程学院,银川750021;北方民族大学 计算机科学与工程学院,银川750021;北方民族大学 宁夏智能信息与大数据处理重点实验室,银川750021 |
| |
| 基金项目： | 国家自然科学基金资助项目(62062001,61762019,61862051,61962002);北方民族大学重大专项资助项目(ZDZX201901);宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119);北方民族大学校级科研一般项目(2019XYZJK05) |
| |
| 摘 要： | 最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值.针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法.利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解.最后选取若干带权有向图模型进行数值实验,验证了算法的可行性及有效性,且算法在求解效率上优于部分算法.
|
| 关 键 词： | 最小费用最大流 线性规划 信念传播算法 因子图 |
| 收稿时间： | 2020/10/12 0:00:00 |
| 修稿时间： | 2021/6/17 0:00:00 |
Belief propagation algorithm for solving minimum cost maximum flow problem |
| |
| Zuo Fengyuan,Wang Xiaofeng,Niu Jin,Liang Chen.Belief propagation algorithm for solving minimum cost maximum flow problem[J].Application Research of Computers,2021,38(7):1998-2002,2024. |
| |
| Authors: | Zuo Fengyuan Wang Xiaofeng Niu Jin Liang Chen |
| |
| Affiliation: | North Minzu University,,,, |
| |
| Abstract: | |
| |
| Keywords: | minimum cost maximum flow(MCMF) linear programming belief propagation algorithm factor graph |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
|
