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

doi:10.3969/j.issn.0372-2112.2019.11.021

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

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

王辛^1,2, 王晓峰¹, 李卫民²

1. 北方民族大学计算机科学与工程学院, 宁夏银川 750021;
2. 上海大学计算机工程与科学学院, 上海 200444

收稿日期:2018-11-26 修回日期:2019-03-20 出版日期: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 Xin^1,2, WANG Xiao-feng¹, LI Wei-min²

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
- Supported by:
- National Key Research and Development Program of China (No.2017YFE0117500); National Natural Science Foundation of China (No.61462001, No.61762019, No.61762002, No.61862051); Key Research Program of North Minzu University (No.2017KJ24, No.2017KJ25); 2018 Key Research and Development Project of Ningxia Hui Autonomous Region (No.2018BEE0309); Supported by First-Class Discipline Construction Program of Colleges and Universities in Ningxia Hui Autonomous Region ( Electronics Science and Technology) (No.NXYLXK2017A07); Natural Science Foundation of Ningxia Hui Autonomous Region (No.2019AAC03120)

摘要/Abstract

摘要： 最小割问题（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

中图分类号:

TP301

王辛, 王晓峰, 李卫民. 一种求解最小割的警示传播算法[J]. 电子学报, 2019, 47(11): 2386-2391.

WANG Xin, WANG Xiao-feng, LI Wei-min . A Warning Propagation Algorithm for Solving Minimum Cut[J]. Acta Electronica Sinica, 2019, 47(11): 2386-2391.

参考文献

[1] HIROSHI,ISHIKAWA.Global optimization using the DIRECT algorithm in Matlab[J].Matlab Advanced Modeling Optimization,1999,1(2):1-8.
[2] GRIFFING A R,LYNCH B R,STONE E A.Structural properties of the minimum cut of partially-supplied graphs[J].Discrete Applied Mathematics,2014,177(4):152-157.
[3] DAVID R,KARGER,CLIFFORD S.A new approach to the minimum cut problem[J].Journal of the ACM,1996,43(4):601-640.
[4] BHUSHAN G.Sajith.I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs[J].Theoretical Computer Science,2014,43(5):13-15.
[5] EDNAA,HOSHINO.The minimum cut cover problem[J].Electronic Notes in Discrete Mathematics,2011,37(9):255-260.
[6] CONNELLY B,FANG-LUE Z.A survey of the state of the art in patch-based synthesis[J].Computational Visual Media,2017,3(1):3-20.
[7] ORHAN D,VAHID K A,ALI F.A distributed evolutionary algorithm for detecting minimum vertex cuts for wireless ad hoc and sensor networks[J].Journal of Network and Computer Applications,2019,41(1):23-28.
[8] DUAN Q,JINHUI X.On the connectivity preserving minimum cut problem[J].Journal of Computer and System Sciences,2014,80(4):837-848.
[9] MARTIN D,ALAN F,MICHAEL M.A probabilistic analysis of randomly generated binary constraint satisfy-action[J].Theory Computer Science,2003,290(3):1815-1828.
[10] CREIGNOU N,EAUDE H.The SAT-UNSAT transition for random constraint satisfaction problems[J].Discrete Mat-hematics,2009,309(8):2085-2099.
[11] MARTIN OC,MONASSON R,ZECCHINA R.Statistical mechanics methods and phase transitions in optimization[J].Theory Computer Science,2001,265(12):3-67.
[12] 王晓峰,许道云.警示传播算法收敛的充分条件[J].软件学报,2016,27(12):3003-3013. Wang Xiao-feng,Xu Dao-yun.Sufficient conditions convergence of warning propagation algorithm[J].Journal of Software,2016,27(12):3003-3013.(in Chinese)
[13] XU K,Li W.The SAT phase transition[J].Science in China,1999,42(5):494-501.
[14] SHEN Y J.On the phase transitions of random k-constraint satisfaction problems[J].Artificial Intelligence,2011,17-5(3-4):914-927.
[15] ACHLIOPTAS D,NARO A,Peres Y.Rigorous location of phase transitions in hard optimization problems[J].Nature,2005,435(7043):759-764.
[16] MERTENS S,MEZARD M,ZECCHINA R.Threshold values of random k-SAT from the cavity method[J].Random Structure Algorithms,2006,28(3):340-373.
[17] MEZARD M,PARISI G.The cavity method at zero temperature[J].Journal of Statistical Physics,2003,111(1-2):1-34.
[18] MEZARD M,ZECCHINA R.Random k-satisfiability problem from an analytic solution to an efficient algorithm[J].Physical Review,2002,66(5):056-126.
[19] MANEVA E,MOSSEL E,WAINWRIGHT M.A new look at survey propagation and its generalizations[J].Journal of the ACM,2007,54(4):1089-1098.
[20] BRAUNSTEIN A,MEZARD M,MEZARD R.Survey propagation:an algorithm for satisfiability[J].Random Structures and Algorithms,2005,27(2):201-226.
[21] BRAUNSTEIN A,ZECCHINA R.Survey and belief propagation on random k-SAT[J].Lecture Notes in Computer Science,2004,2919(1):519-528.
[22] YEDIDIA JS,FREEMAN WT,WEISS Y.Understanding belief propagation and its generalizations[J].Artificial Intelligence,2003,8(1):239-269.
[23] MEZARD M,PARISI G,ZECCHINA R.Analytic and algorithmic solution of random satisfiability problems[J].Science,2002,297(5582):812-815.
[24] BOUSSEMART K,HEMERY F F,et al.Random constraint satisfaction[J].Easy Generation of Hard Instance Artificial Intelligence,2007,171(1):514-534.

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

A Warning Propagation Algorithm for Solving Minimum Cut

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李杨帅, 彭斐, 韩倩, 李小帅, 解光军. 一种针对QCA电路自动布局布线的混合策略研究[J]. 电子学报, 2023, 51(3): 666-674.
[2]	康海燕, 冀源蕊. 基于本地化差分隐私的时序位置发布方案研究[J]. 电子学报, 2022, 50(9): 2222-2232.
[3]	张明宇, 王琦, 于洋. 基于LSTM-DHMM的MOSFET器件健康状态识别与故障时间预测[J]. 电子学报, 2022, 50(3): 643-651.
[4]	刘芳, 朱天贺, 苏卫星, 刘阳. 基于高斯隐马尔可夫模型的人机共享控制区域化决策算法[J]. 电子学报, 2022, 50(11): 2659-2667.
[5]	王相海, 宋若曦, 曲思洁, 穆振华, 宋传鸣. 图像多尺度几何分析域隐马尔可夫树模型研究进展[J]. 电子学报, 2022, 50(1): 238-249.
[6]	李彦苍, 巩翔宇. 基于信息熵的改进狮群算法及其在组合优化中的应用[J]. 电子学报, 2021, 49(8): 1577-1585.
[7]	黄戈文, 蔡延光, 戚远航, 陈厚仁, 王世豪. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
[8]	许烁, 王阳, 孙成恺. 模块化可重构服务机器人群的任务规划[J]. 电子学报, 2016, 44(1): 101-109.
[9]	郑巧仙, 李明, 李元香, 唐秋华. 求解双边装配线平衡问题的改进蚁群算法[J]. 电子学报, 2014, 42(5): 841-845.
[10]	何玉文, 鲍长春, 夏丙寅. 基于AR-HMM在线能量调整的语音增强方法[J]. 电子学报, 2014, 42(10): 1991-1997.
[11]	钱洁, 郑建国. 引入逆学习的量子自适应禁忌搜索算法[J]. 电子学报, 2013, 41(6): 1069-1075.
[12]	王超;郭渊博;马建峰;裴庆祺;徐栋. 基于隐马尔可夫模型的资源滥用行为检测方法研究[J]. 电子学报, 2010, 38(6): 1383-1388.
[13]	姜慧研;何炜. 基于胸部CT图像的肺癌识别方法的研究[J]. 电子学报, 2009, 37(8): 1664-1668.
[14]	宋千;金添;周智敏. 基于HMM核超球面支持向量机的超宽带SAR未爆物检测[J]. 电子学报, 2009, 37(7): 1509-1515.
[15]	周雅兰;王甲海;印鉴. 一种基于分布估计的离散粒子群优化算法[J]. 电子学报, 2008, 36(6): 1242-1248.