计算机应用研究

作者：左逢源,王晓峰,牛进,梁晨,

单位：北方民族大学a.计算机科学与工程学院;b.宁夏智能信息与大数据处理重点实验室,银川750021；

关键词：最小费用最大流,线性规划,信念传播算法,因子图,

基金：国家自然科学基金资助项目(62062001,61762019,61862051,61962002)；北方民族大学重大专项资助项目(ZDZX201901)；宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)；北方民族大学校级科研一般项目(2019XYZJK05)；；

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

来源：2021年第7期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2021年第7期