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

• 作者: 李卫民 王晓峰 王辛
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 组合优化 最小割 警示传播算法 隐马尔可夫模型 概率算法 马尔科夫化
• 年，卷（期）: 2019,（11）
• 所属期刊栏目: 学术论文
• 页码范围: 2386-2391
• 页数: 6页
• 分类号: TP301
• 字数: 4415字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2019.11.021

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李卫民	上海大学计算机工程与科学学院	7	11	2.0	3.0
2	王晓峰	北方民族大学计算机科学与工程学院	14	23	4.0	4.0
3	王辛	北方民族大学计算机科学与工程学院	7	1	1.0	1.0