一种基于回溯求解约束满足问题的置信传播算法
A Belief Propagation Algorithm for Constraint Satisfaction Problem Based on Backtracking
摘要: 针对一个典型的具有可变取值域的随机约束满足问题模型即RB模型，提出一种基于回溯的置信传播的算法。该算法在置信传播方程不收敛时，通过回溯对上一个变量进行重新赋值，从而将消去变量的过程继续进行下去。数值结果表明：这种基于回溯的置信传播算法能在可满足性相变区域找到问题的解，有效地提高了置信传播算法的求解效率。
Abstract: In this paper, we propose a belief propagation algorithm based on backtracking for a typical model of random constraint satisfaction problem with variable range, namely RB model. In this algorithm, when the belief propagation equation does not converge, it reassigns the previous variable by backtracking, so as to continue the process of variable elimination. The numerical results show that the backtracking belief propagation algorithm can find the solution of the problem in the satisfia-bility phase transition region, and effectively improve the efficiency of the belief propagation algo-rithm.
文章引用：林童. 一种基于回溯求解约束满足问题的置信传播算法[J]. 应用数学进展, 2023, 12(3): 993-1002. https://doi.org/10.12677/AAM.2023.123101

参考文献

[1] Zhou, H.J., Zheng, Z.M. and Xu, K. (2011) A Message-Passing Approach to Random Constraint Satisfaction Problems with Growing Domains. Journal of Statistical Mechanics: Theory and Experiment, 2011, Article ID: P02019. [Google Scholar] [CrossRef] 
[2] 赵春艳, 郑志明. 一种基于变量熵求解约束满足问题的置信传播算法[J]. 中国科学(信息科学), 2012, 42(9): 1170-1180.
[3] 任雪亮. 改进的置信传播算法在求解最大约束满足问题的应用[D]: [硕士学位论文]. 长春: 东北师范大学, 2015.
[4] 吴拨荣, 赵春艳, 原志强. 置信传播和模拟退火相结合求解约束满足问题[J]. 计算机应用研究, 2019, 36(5): 1297-1301.
[5] Zhao, C.Y. and Fu, Y.R. (2021) Belief Propagation Guided Decimation Algorithms for Random Constraint Satisfaction Problems with Growing Domains. Journal of Statistical Mechanics: Theory and Experiment, 2021, Article ID: 033408. [Google Scholar] [CrossRef] 
[6] Zhao, C.Y., Fu, Y.R. and Zhao, J.H. (2022) A Residual-Based Message Passing Algorithm for Constraint Satisfaction Problems. Communications in Theoretical Physics, 74, Article ID: 035601. [Google Scholar] [CrossRef] 
[7] Gent, I.P., Macintyre, E., Prosser, P., Smith, B.M. and Walsh, T. (2001) Random Constraint Satisfaction: Flaws and Structure. Constraints, 6, 345-372. [Google Scholar] [CrossRef] 
[8] Prosser, P. (1996) An Empirical Study of Phase Transitions in Bi-nary Constraint Satisfaction Problems. Artificial Intelligence, 81, 81-109. [Google Scholar] [CrossRef] 
[9] Smith, B.M. and Dyer, M.E. (1996) Locating the Phase Tran-sition in Binary Constraint Satisfaction Problems. Artificial Intelligence, 81, 155-181. [Google Scholar] [CrossRef] 
[10] Achlioptas, D., Molloy, M.S.O., Kirousis, L.M., et al. (2001) Random Constraint Satisfaction: A More Accurate Picture. Constraints, 6, 329-344. [Google Scholar] [CrossRef] 
[11] Xu, K. and Li, W. (2000) Exact Phase Transitions in Random Con-straint Satisfaction Problems. Journal of Artificial Intelligence Research, 12, 93-103. [Google Scholar] [CrossRef] 
[12] Frieze, A. and Molloy, M. (2006) The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems. Random Structure and Algorithms, 28, 323-339. [Google Scholar] [CrossRef] 
[13] Smith, B.M. (2001) Constructing an Asymptotic Phase Transition in Ran-dom Binary Constraint Satisfaction Problems. Theoretical Computer Science, 265, 265-283. [Google Scholar] [CrossRef] 
[14] Molloy, M. (2003) Models for Random Constraint Satisfac-tion Problems. SIAM Journal of Computing, 32, 935-949. [Google Scholar] [CrossRef] 
[15] Xu, K. and Li, W. (2006) Many Hard Examples in Exact Phase Transitions. Theoretical Computer Science, 355, 291-302. [Google Scholar] [CrossRef] 
[16] Xu, K., Boussemart, F., Hemery, F. and Lecoutre, C. (2007) Ran-dom Constraint Satisfaction: Easy Generation of Hard (Satisfiable) Instances. Artificial Intelligence, 171, 514-534. [Google Scholar] [CrossRef] 

为你推荐