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

王辛; 王晓峰; 李卫民

doi:10.3969/j.issn.0372-2112.2019.11.021

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-07-16

- 一种求解最小割的警示传播算法
- A Warning Propagation Algorithm for Solving Minimum Cut
- 电子学报 2019年47卷第11期页码：2386-2391
- 作者机构：
  
  1. 北方民族大学计算机科学与工程学院,宁夏,银川,750021
  2. 上海大学计算机工程与科学学院,上海,200444
  3. 北方民族大学计算机科学与工程学院,宁夏,银川,750021
  4. 上海大学计算机工程与科学学院,上海,200444
- 作者简介：
- 基金信息：
  
  国家重点研发计划 (No.2017YFE0117500);国家自然科学基金 (No.61462001,No.61762019,No.61762002,No.61862051);北方民族大学重点科研项目 (No.2017KJ24,No.2017KJ25);2018宁夏回族自治区重点研发计划项目 (No.2018BEE0309);宁夏高等学校一流学科建设 (电子科学与技术学科)资助项目 (No.NXYLXK2017A07);宁夏自然科学基金 (No.2019AAC03120)
- DOI：10.3969/j.issn.0372-2112.2019.11.021
  中图分类号： TP301
- 网络出版：2019-11-25，
  
  纸质出版：2019
- 稿件说明：
移动端阅览
王辛, 王晓峰, 李卫民. 一种求解最小割的警示传播算法[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.
王辛, 王晓峰, 李卫民. 一种求解最小割的警示传播算法[J]. 电子学报, 2019,47(11):2386-2391. DOI： 10.3969/j.issn.0372-2112.2019.11.021.

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. DOI： 10.3969/j.issn.0372-2112.2019.11.021.

摘要

最小割问题（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.

关键词

Keywords

references

浏览量

183

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种针对QCA电路自动布局布线的混合策略研究

基于胸部CT图像的肺癌识别方法的研究

最优多用户检测问题研究

一种解决组合优化问题的改进型量子遗传算法

汉语连续语音识别中多项式拟合语音轨迹模型的研究