电子学报 ›› 2019, Vol. 47 ›› Issue (11): 2386-2391.DOI: 10.3969/j.issn.0372-2112.2019.11.021

• 学术论文 • 上一篇    下一篇

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

王辛1,2, 王晓峰1, 李卫民2   

  1. 1. 北方民族大学计算机科学与工程学院, 宁夏银川 750021;
    2. 上海大学计算机工程与科学学院, 上海 200444
  • 收稿日期:2018-11-26 修回日期:2019-03-20 出版日期:2019-11-25 发布日期:2019-11-25
  • 通讯作者: 李卫民
  • 作者简介:王辛 男,1995年生于宁夏吴忠.现为北方民族大学计算机科学与工程学院硕士研究生.主要研究方向为算法设计与分析.E-mail:wx_nun@163.com;王晓峰 男,1980年生于甘肃会宁.现为北方民族大学副教授、硕士生导师.主要研究方向人工智能.E-mail:wxf_gzu@163.com
  • 基金资助:
    国家重点研发计划(No.2017YFE0117500);国家自然科学基金(No.61462001,No.61762019,No.61762002,No.61862051);北方民族大学重点科研项目(No.2017KJ24,No.2017KJ25);2018宁夏回族自治区重点研发计划项目(No.2018BEE0309);宁夏高等学校一流学科建设(电子科学与技术学科)资助项目(No.NXYLXK2017A07);宁夏自然科学基金(No.2019AAC03120)

A Warning Propagation Algorithm for Solving Minimum Cut

WANG Xin1,2, WANG Xiao-feng1, LI Wei-min2   

  1. 1. College of Computer Science and Engineering, North Minzu University, Yinchuan, Ningxia 750021, China;
    2. College of Computer Engineering and Science, Shanghai University, Shanghai 200444, China
  • Received:2018-11-26 Revised:2019-03-20 Online:2019-11-25 Published:2019-11-25

摘要: 最小割问题(minimum cut problem)是NP(Non-deterministic Polynomial)难问题,警示传播算法(warning propagation)是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法.

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

Abstract: 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.

Key words: combinatorial optimization, minimum cut, warning propagation(WP), hidden Markov model(HMM), probability algorithm, Markov off

中图分类号: