求解网络最大流问题的信念传播算法  

Belief algorithm propagation for network maximum flow problem

作　　者：左逢源 王晓峰[1,2] 任雪娇 张丹丹 ZUO Feng-yuan;WANG Xiao-feng;REN Xue-jiao;ZHANG Dan-dan(College of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Intelligent Information and Big Data Processing of Ningxia Province,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学宁夏智能信息与大数据处理重点实验室,宁夏银川750021

出　　处：《计算机工程与设计》2021年第5期1346-1352,共7页Computer Engineering and Design

基　　金：国家自然科学基金项目(61462001、61762019、61862051、61962002);北方民族大学重点科研基金项目(2017KJ24、2017KJ25);北方民族大学重大专项基金项目(ZDZX201901);北方民族大学校级科研一般基金项目(2019XYZJK05);宁夏回族自治区重点研发计划基金项目(2018BEE03019);宁夏自然科学基金项目(NZ17111、2019AAC03120、2019AAC03119)。

摘　　要：为解决目前网络最大流问题求解效率低、数据溢出等问题,设计求解网络最大流问题的信念传播算法。根据网络最大流问题的特性,使最大流问题的线性规划方程与信念传播算法传递方程结合,得到描述函数,将带权随机有向图映射为对应的因子图模型;在此模型基础上,利用信念传播算法的信息迭代方程进行特征值收敛计算,提高寻优效率。选取若干随机有向图进行数值实验,实验结果表明,该算法在寻优速度上优于同类算法,验证了其可行性及有效性。To solve the problems of current network maximum flow problem such as low efficiency and data overflow,a belief propagation algorithm for network maximum flow problem was designed.According to the characteristics of the network maximum flow problem,the linear programming equation of the maximum flow problem was combined with the belief propagation algorithm transfer equation to obtain the description function,and the weighted random directed graph was mapped to the corresponding factor graph model.Based on this model,the information iterative equation of belief propagation algorithm was used to calculate the eigenvalue convergence,thereby improving the efficiency of optimization.Several random directed graphs were selected for numerical experiments.The results show that the proposed algorithm is superior to similar algorithms in optimization speed,which verifies its feasibility and effectiveness.

关 键 词：网络最大流 线性规划 信念传播算法 因子图 描述函数 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]