%0 Journal Article %A 王辛 %A 王晓峰 %A 李卫民 %T 一种求解最小割的警示传播算法 %D 2019 %R 10.3969/j.issn.0372-2112.2019.11.021 %J 电子学报 %P 2386-2391 %V 47 %N 11 %X 最小割问题(minimum cut problem)是NP(Non-deterministic Polynomial)难问题,警示传播算法(warning propagation)是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法. %U https://www.ejournal.org.cn/CN/10.3969/j.issn.0372-2112.2019.11.021