基于变量熵的警示传播算法求解最小割问题

doi:10.11772/j.issn.1001-9081.2025070904

《计算机应用》唯一官方网站 ›› 2026, Vol. 46 ›› Issue (9): 2931-2937.DOI: 10.11772/j.issn.1001-9081.2025070904

• 先进计算 • 上一篇

基于变量熵的警示传播算法求解最小割问题

胡思敏¹, 王晓峰¹^,², 丁红胜¹(), 宋家欢¹, 锁小娜¹, 颜冬¹

^1.北方民族大学计算机科学与工程学院，银川 750021
^2.图像图形智能处理国家民委重点实验室（北方民族大学），银川 750021

收稿日期:2025-08-11 修回日期:2025-09-11 接受日期:2025-09-12 发布日期:2025-11-05 出版日期:2026-09-10
通讯作者: 丁红胜
作者简介:胡思敏（1996—），女，陕西西安人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
王晓峰（1980—），男（回族），甘肃会宁人，副教授，博士，CCF会员，主要研究方向：机器学习、人工智能
丁红胜（1977—），男，甘肃甘谷人，副教授，硕士，主要研究方向：计算机组织与结构
宋家欢（2001—），男（满族），河北承德人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
锁小娜（1998—），女（回族），宁夏吴忠人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
颜冬（1999—），男（满族），辽宁本溪人，硕士研究生，CCF会员，主要研究方向：算法分析与设计。
基金资助:
宁夏自然科学基金资助项目(2024AAC03165);宁夏青年拔尖人才项目(2021)

Variable entropy-based warning propagation algorithm for solving minimum cut problem

Simin HU¹, Xiaofeng WANG¹^,², Hongsheng DING¹(), Jiahuan SONG¹, Xiaona SUO¹, Dong YAN¹

^1.School of Computer Science and Engineering，North Minzu University，Yinchuan Ningxia 750021，China
^2.Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission，（North Minzu University），Yinchuan Ningxia 750021，China

Received:2025-08-11 Revised:2025-09-11 Accepted:2025-09-12 Online:2025-11-05 Published:2026-09-10
Contact: Hongsheng DING
About author:HU Simin， born in 1996， M. S. candidate. Her research interests include algorithm analysis and design.
WANG Xiaofeng， born in 1980， Ph. D.， associate professor. His research interests include machine learning， artificial intelligence.
DING Hongsheng， born in 1977， M. S.， associate professor. His research interests include computer organization and architecture.
SONG Jiahuan， born in 2001， M. S. candidate. His research interests include algorithm analysis and design.
SUO Xiaona， born in 1998， M. S. candidate. Her research interests include algorithm analysis and design.
YAN Dong， born in 1999， M. S. candidate. His research interests include algorithm analysis and design.
Supported by:
Natural Science Foundation of Ningxia(2024AAC03165);Ningxia Youth Top Talent Project(2021)

摘要/Abstract

摘要：

最小割问题（MCP）是图论中的经典NP（Nondeterministic Polynomial）-难问题，在图像分割和网络可靠性分析等方面具有广泛应用。警示传播（WP）算法作为基于因子图的推理方法，在求解组合优化问题时表现出较强的可扩展性与结构适应能力；然而，该算法在求解MCP时，它的传播路径选择、因子图构建和收敛性方面仍存在不足。为此，提出一种基于变量熵的警示传播（EWP）算法求解MCP。首先，通过引入基于隐马尔可夫模型（HMM）驱动的跳点机制选取核心传播区域；同时，利用批量映射的因子图转换方式有效压缩图结构的维度；最后，结合边缘概率与变量熵的冻结传播策略，引导信息传播过程更快地收敛。实验结果表明，EWP算法在多种图规模中表现出良好性能，尤其在大规模图优化问题中具有较大的应用潜力。

关键词: 最小割问题, 警示传播算法, 隐马尔可夫模型, 因子图, 变量熵

Abstract:

The Minimum Cut Problem （MCP） is a classic NP （Nondeterministic Polynomial） -hard problem with broad applications in image segmentation and network reliability analysis. Warning Propagation （WP） algorithm， a factor graph-based inference method， has shown good scalability and structural adaptability when solving combinatorial optimization problems. However， its effectiveness on MCP is limited by path selection， factor graph construction， and convergence. Therefore， an Entropy-based Warning Propagation （EWP） algorithm was proposed to solve MCP. First， a Hidden Markov Model （HMM） -driven jump-point mechanism was introduced to select core propagation regions. At the same time， a batch-mapping factor graph transformation way was employed to reduce graph structural dimensionality effectively. Finally， a propagation freezing strategy that combined marginal probability and variable entropy was adopted to accelerate convergence. Experimental results demonstrate that EWP achieves good performance on graphs with different sizes， and especially has significant potential in large-scale graph optimization problems.

Key words: Minimum Cut Problem (MCP), Warning Propagation (WP) algorithm, Hidden Markov Model (HMM), factor graph, variable entropy

中图分类号:

TP301.6

胡思敏, 王晓峰, 丁红胜, 宋家欢, 锁小娜, 颜冬. 基于变量熵的警示传播算法求解最小割问题[J]. 计算机应用, 2026, 46(9): 2931-2937.

Simin HU, Xiaofeng WANG, Hongsheng DING, Jiahuan SONG, Xiaona SUO, Dong YAN. Variable entropy-based warning propagation algorithm for solving minimum cut problem[J]. Journal of Computer Applications, 2026, 46(9): 2931-2937.

图/表 8

图1 最小割问题的实例

Fig. 1 Instances of minimum cut problem

图2 无向图转化为因子图的过程

Fig. 2 Process of converting undirected graph into factor graph

表1 不同节点数时的随机图参数

Tab. 1 Random graph parameters with different numbers of nodes

n	m	α
10	30	3.0
20	50	2.5
50	115	2.3
100	240	2.4
200	520	2.6
500	1 050	2.1

图3 不同n在EWP算法上的收敛概率

Fig. 3 Convergence probability of EWP algorithm with different n

图4 n=10时WP算法与EWP算法的收敛概率对比

Fig. 4 Comparison of convergence probability between WP and EWP algorithms with n=10

图5 不同n在EWP算法上的因子图转换耗时

Fig. 5 Factor graph conversion time of EWP algorithm with different n

表2 不同算法的求解时间对比

Tab. 2 Comparison of solution time for different algorithms

n	不同算法的求解时间/ms
n	D算法	WP算法	EWP算法
100	0.01	0.39	0.02
200	0.07	0.41	0.09
300	0.14	0.35	0.16
400	0.27	0.30	0.20
500	0.33	0.29	0.21
600	0.35	0.29	0.22

图6 不同节点规模下的不同算法运行时间对比

Fig. 6 Comparison of running time of different algorithms under different node sizes

参考文献 44

[1]	Boykov Y， Veksler O， Zabih R. Fast approximate energy minimization via graph cuts ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2001， 23（11）： 1222-1239.
[2]	Boykov Y， Funka-Lea G. Graph cuts and efficient ND image segmentation ［J］. International Journal of Computer Vision， 2006， 70（2）： 109-131.
[3]	Ramesh V， Nagarajan S， Jung J J， et al. Max-flow min-cut algorithm with application to road networks ［J］. Concurrency and Computation： Practice and Experience， 2017， 29（11）： No.e4099.
[4]	Caccetta L， Hill S P. An application of branch and cut to open pit mine scheduling ［J］. Journal of Global Optimization， 2003， 27（2/3）： 349-365.
[5]	Karger D R. A randomized fully polynomial time approximation scheme for the all terminal network reliability problem ［C］// STOC 1995. New York： ACM， 1995： 11-17.
[6]	Ramanathan A， Colbourn C J. Counting almost minimum cutsets with reliability applications ［J］. Mathematical Programming， 1987， 39（3）： 253-261.
[7]	Botafogo R A. Cluster analysis for hypertext systems ［C］// SIGIR 1993. New York： ACM， 1993： 116-125.
[8]	Chatterjee S， Gilbert J R， Schreiber R， et al. Array distribution in data-parallel programs ［C］// LCP 1995. Berlin： Springer， 1995： 76-91.
[9]	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： 152-157.
[10]	Abdolahzadeh A， Aman M， Tayyebi J. Minimum st-cut interdiction problem ［J］. Computers and Industrial Engineering， 2020， 148： No.106708.
[11]	Fox K， Panigrahi D， Zhang F. Minimum cut and minimum k-cut in hypergraphs via branching contractions ［C］// SODA 2019. Philadelphia， PA： SIAM， 2019： 881-896.
[12]	Karger D R， Stein C. A new approach to the minimum cut problem ［J］. Journal of the ACM， 1996， 43（4）： 601-640.
[13]	Ghaffari M， Nowicki K. Massively parallel algorithms for minimum cut ［C］// PODC 2020. New York： ACM， 2020： 119-128.
[14]	Mukhopadhyay S， Nanongkai D. Weighted min-cut： sequential， cut-query， and streaming algorithms ［C］// STOC 2020. New York： ACM， 2020： 496-509.
[15]	Gawrychowski P， Mozes S， Weimann O. A note on a recent algorithm for minimum cut ［C］// SOSA 2021. Philadelphia， PA： SIAM， 2021： 74-79.
[16]	Beideman C， Chandrasekaran K， Wang W. Approximate minimum cuts and their enumeration ［C］// SOSA 2023. Philadelphia， PA： SIAM， 2023： 36-41.
[17]	Aissi H， Mahjoub A R. On the minimum s-t cut problem with budget constraints ［J］. Mathematical Programming， 2024， 203（1/2）： 421-442.
[18]	Wei W， Liu Y， Zhang Q. An optimal pruned traversal tree-based fast minimum cut solver in dense graph ［J］. Information Sciences， 2024， 652： No.119768.
[19]	Niaparast H， Moseley B， Singh K. Faster global minimum cut with predictions ［C］// ICML 2025. New York： JMLR.org， 2025： 46305-46319.
[20]	Kenneth-Mordoch Y， Krauthgamer R. Cut-query algorithms with few rounds ［C］// ESA 2025. Wadern： Leibniz-Zentrum für Informatik， 2025： No.100.
[21]	Braunstein A， Mézard M， Zecchina R. Survey propagation： an algorithm for satisfiability ［J］. Random Structures and Algorithms， 2005， 27（2）： 201-226.
[22]	王晓峰，许道云.警示传播算法收敛的充分条件［J］.软件学报， 2016， 27（12）： 3003-3013.
	Wang Xiaofeng， Xu Daoyun. Sufficient conditions for convergence of the warning propagation algorithm ［J］. Journal of Software， 2016， 27（12）： 3003-3013.
[23]	Cooley O， Lee J， Ravelomanana J B. Warning Propagation： stability and subcriticality ［PP/OL］. V2. arXiv （2024-05-24）［2025-08-20］. .
[24]	王辛，王晓峰，李卫民.一种求解最小割的警示传播算法［J］.电子学报， 2019， 47（11）： 2386-2391.
	Wang Xin， Wang Xiaofeng， Li Weiming. A warning propagation algorithm for solving minimum cut ［J］. Acta Electronica Sinica， 2019， 47（11）： 2386-2391.
[25]	Loeliger H A. An introduction to factor graphs ［J］. IEEE Signal Processing Magazine， 2004， 21（1）： 28-41.
[26]	Kschischang F R， Frey B J， Loeliger H A. Factor graphs and the sum-product algorithm ［J］. IEEE Transactions on Information Theory， 2001， 47（2）： 498-519.
[27]	Feige U， Mossel E， Vilenchik D. Complete convergence of message passing algorithms for some satisfiability problems ［J］. Theory of Computing， 2013， 9（19）： 617-651.
[28]	Shannon C E. A mathematical theory of communication ［J］. The Bell System Technical Journal， 1948， 27（3）： 379-423.
[29]	Cover T M， Thomas J A. Elements of information theory ［M］. New York： John Wiley & Sons， 1991.
[30]	Peng H， Long F， Ding C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（8）： 1226-1238.
[31]	Jaynes E T. Information theory and statistical mechanics ［J］. Physical Review， 1957， 106（4）： No.620.
[32]	Quinlan J R. Induction of decision trees ［J］. Machine Learning， 1986， 1（1）： 81-106.
[33]	Eddy S R. Hidden Markov models ［J］. Current Opinion in Structural Biology， 1996， 6（3）： 361-365.
[34]	Xu K， Li C， Tian Y， et al. Representation learning on graphs with jumping knowledge networks ［C］// ICML 2018. New York： JMLR.org， 2018： 5453-5462.
[35]	Harabor D， Grastien A. Online graph pruning for pathfinding on grid maps ［C］// AAAI 2011. Palo Alto： AAAI Press， 2011： 1114-1119.
[36]	Hamilton W L， Ying R， Leskovec J. Inductive representation learning on large graphs ［C］// NeurIPS 2017. Red Hook： Curran Associates Inc.， 2017： 1025-1035.
[37]	Shervashidze N， Schweitzer P， van Leeuwen E J， et al. Weisfeiler-Lehman graph kernels ［J］. Journal of Machine Learning Research， 2011， 12： 2539-2561.
[38]	Wainwright M J， Jordan M I. Graphical models， exponential families， and variational inference ［J］. Foundations and Trends in Machine Learning， 2008， 1（1/2）： 1-305.
[39]	Goodfellow I， Bengio Y， Courville A， et al. Deep learning ［M］. Cambridge： MIT Press， 2016.
[40]	Hoshino E A. The minimum cut cover problem ［J］. Electronic Notes in Discrete Mathematics， 2011， 37： 255-260.
[41]	Liberti L， Alfandari L， Plateau M C. Edge cover by connected bipartite subgraphs ［J］. Annals of Operations Research， 2011， 188（1）： 307-329.
[42]	Stoer M， Wagner F. A simple min-cut algorithm ［J］. Journal of the ACM， 1997， 44（4）： 585-591.
[43]	Karger D R. Global min-cuts in RNC， and other ramifications of a simple min-cut algorithm ［C］// SODA 1993. Philadelphia， PA： SIAM， 1993： 21-30.
[44]	Bhardwaj N， Lovett A J M， Sandlund B. A simple algorithm for minimum cuts in near-linear time ［C］// SWAT 2025. Wadern： Leibniz-Zentrum für Informatik， 2025： No.12.

基于变量熵的警示传播算法求解最小割问题

Variable entropy-based warning propagation algorithm for solving minimum cut problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 44

相关文章 15

编辑推荐

Metrics

[1]	高昊, 张庆科, 卜降龙, 李俊青, 张化祥. 基于协同变异与莱维飞行策略的教与学优化算法及其应用[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1355-1364.
[2]	霍纬纲, 王慧芳. 基于自编码器和隐马尔可夫模型的时间序列异常检测方法[J]. 计算机应用, 2020, 40(5): 1329-1334.
[3]	李添正, 王春桃. 基于马尔可夫随机场的加密二值图像有损压缩算法[J]. 计算机应用, 2020, 40(5): 1354-1363.
[4]	吴婉婷, 朱燕, 黄定江. 在线投资组合选择的半指数梯度策略及实证分析[J]. 计算机应用, 2019, 39(8): 2462-2467.
[5]	王金策, 邓越萍, 史明, 周云飞. 多时间尺度时间序列趋势预测[J]. 计算机应用, 2019, 39(4): 1046-1052.
[6]	杨世强, 罗晓宇, 乔丹, 柳培蕾, 李德信. 基于滑动窗口和动态规划的连续动作分割与识别[J]. 计算机应用, 2019, 39(2): 348-353.
[7]	张全贵, 蔡丰, 李志强. 基于耦合多隐马尔可夫模型和深度图像数据的人体动作识别[J]. 计算机应用, 2018, 38(2): 454-457.
[8]	高军强, 汤霞清, 张环, 郭理彬. 基于因子图算法的INS/GPS信息滞后处理方法[J]. 计算机应用, 2018, 38(11): 3342-3347.
[9]	郭雷勇, 李宇, 林胜义, 谭洪舟. 用于隐马尔可夫模型语音带宽扩展的激励分段扩展方法[J]. 计算机应用, 2017, 37(8): 2416-2420.
[10]	崔建华, 王忠勇, 张传宗, 张园园. 基于因子图和联合消息传递的无线网络协作定位算法[J]. 计算机应用, 2017, 37(5): 1306-1310.
[11]	李方伟, 李骐, 朱江. 改进的基于隐马尔可夫模型的态势评估方法[J]. 计算机应用, 2017, 37(5): 1331-1334.
[12]	王董礼, 曹鹏, 黄国策, 孙启禄, 李连宝. 基于隐马尔可夫模型的短波认知频率选择方法[J]. 计算机应用, 2016, 36(5): 1179-1182.
[13]	李强, 陈浩, 陈丁当. 基于隐马尔可夫模型的语音激活检测算法[J]. 计算机应用, 2016, 36(11): 3212-3216.
[14]	颜斌贾霞王小明郭银景郝建军. 相关分块衰落信道下基于因子图EM算法的解码方法[J]. 计算机应用, 2013, 33(03): 607-610.
[15]	刘卫李和成. 基于局部保持投影与隐马尔可夫模型的维文字符识别[J]. 计算机应用, 2012, 32(08): 2309-2312.