一种求解最小割的警示传播算法  

A Warning Propagation Algorithm for Solving Minimum Cut

作　　者：王辛 王晓峰[1] 李卫民[2] WANG Xin;WANG Xiao-feng;LI Wei-min(College of Computer Science and Engineering,North Minzu University,Yinchuan,Ningxia 750021,China;College of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]上海大学计算机工程与科学学院,上海200444

出　　处：《电子学报》2019年第11期2386-2391,共6页Acta Electronica Sinica

基　　金：国家重点研发计划(No.2017YFE0117500);国家自然科学基金(No.61462001,No.61762019,No.61762002,No.61862051);北方民族大学重点科研项目(No.2017KJ24,No.2017KJ25);2018宁夏回族自治区重点研发计划项目(No.2018BEE0309);宁夏高等学校一流学科建设(电子科学与技术学科)资助项目(No.NXYLXK2017A07);宁夏自然科学基金(No.2019AAC03120)

摘　　要：最小割问题(minimum cut problem)是NP(Non-deterministic Polynomial)难问题,警示传播算法(warning propagation)是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法.The minimum cut problem(MCP) is an NP(Non-deterministic Polynomial)-hard problem,warning propagation(WP) is a kind of message passing algorithm based on factor graph,it solve the combinatorial optimization problem.First,HMM(Hidden Markov Model) converted undirected graph to factor graph.Then,we designed a kind of warning propagation algorithm to solving the minimum cut.Finally,we selected skit randomly undirected graphs numerical experiments.The experimental show that the algorithm precedes similar algorithms in speed.

关 键 词：组合优化 最小割 警示传播算法 隐马尔可夫模型 概率算法 马尔科夫化 

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