|
|
Pure Mathematics 2024
基于边际概率分布重新进行单变量选取的置信传播算法求解约束满足问题
|
Abstract:
针对RB模型这一类具有增长取值域的随机约束满足问题，提出一种基于边际概率分布重新进行单变量选取的置信传播算法。该算法在置信传播方程不收敛时，通过边际概率分布顺序由大到小找到下一个变量进行重新赋值，从而消去变量的过程。实验结果表明：这种重新挑选变量进行赋值的置信传播算法能在可满足相变区域找到问题的解，有效地提高了置信传播地求解效率。
Aiming at the RB model which has a growing value range of stochastic constraint satisfaction problem, a belief propagation algorithm based on marginal probability distribution is proposed. When the belief propagation equation does not converge, the algorithm finds the next variable to be reassigned by the order of marginal probability distribution from large to small, so as to eliminate the process of variables. Experimental results show that the belief propagation algorithm based on reselecting variables for assignment can find the solution of the problem in the region that can satisfy the phase change, and effectively improves the efficiency of belief propagation.
| [1] | Prosser, P. (1996) An Empirical Study of Phase Transitions in Binary Constraint Satisfaction Problems. Artificial Intelligence, 81, 81-109. https://doi.org/10.1016/0004-3702(95)00048-8 |
| [2] | Smith, B.M. and Dyer, M.E. (1996) Locating the Phase Transition in Binary Constraint Satisfaction Problems. Artificial Intelligence, 81, 155-181. https://doi.org/10.1016/0004-3702(95)00052-6 |
| [3] | Gent, I.P., Macintyre, E., Prosser, P., et al. (2001) Random Constraint Satisfaction: Flaws and Structure. Constraints, 6, 345-372. https://doi.org/10.1023/A:1011454308633 |
| [4] | Achlioptas, D., Molloy, M.S.O., Kirousis, L.M., et al. (2001) Random Constraint Satisfaction: A More Accurate Picture. Constraints, 6, 329-344. https://doi.org/10.1023/A:1011402324562 |
| [5] | Molloy, M. (2003) Models for Random Constraint Satisfaction Problems. SIAM Journal of Computing, 32, 935-949. https://doi.org/10.1137/S0097539700368667 |
| [6] | Frieze, A.M. and Molloy, M. (2006) The Satisfiability Threshold for Randomly Generated Binary Constrint Satisfaction Problems. Random Structures and Algorithms, 28, 323-339. https://doi.org/10.1002/rsa.20118 |
| [7] | Xu, K. and Li, W. (2000) Exact Phase Transitions in Random Constraint Satisfaction Problems. Journal of Artificial Intelligence Research, 12, 93-103. https://doi.org/10.1613/jair.696 |
| [8] | Xu, K. and Li, W. (2006) Many Hard Examples in Exact Phase Transitions. Theoretical Computer Science, 355, 291-302. https://doi.org/10.1016/j.tcs.2006.01.001 |
| [9] | Xu, K., Boussemart, F., Hemery, F. and Lecoutre, C. (2007) Random Constraint Satisfaction: Easy Generation of Hard (Satisfiable) Instances. Artificial Intelligence, 171, 514-534. https://doi.org/10.1016/j.artint.2007.04.001 |
| [10] | Zhao, C., Zhou, H., Zheng, Z. and Xu, K. (2011) A Message-Passing Approach to Random Constraint Satisfaction Problems with Growing Domains. Journal of Statistical Mechanics: Theory and Experiment, 2, P02019. https://doi.org/10.1088/1742-5468/2011/02/P02019 |
| [11] | 赵春艳, 郑志明. 一种基于变量熵求解约束满足问题的置信传播算法[J]. 中国科学: 信息科学, 2012, 42(9): 1170-1180. |
| [12] | 王晓峰, 许道云. RB模型实例集上置信传播算法的收敛性[J]. 软件学报, 2016, 27(11): 2712-2724. |
| [13] | 原志强, 赵春艳. 两种改进的模拟退火算法求解大值域约束满足问题[J]. 计算机应用研究, 2017, 34(12): 3611-3616. |
| [14] | 吴拨荣, 赵春艳, 原志强. 置信传播和模拟退火相结合求解约束满足问题[J]. 计算机应用研究, 2019, 36(5): 1297-1301. |
| [15] | 李飞龙, 赵春艳, 范如梦. 基于禁忌搜索算法求解随机约束满足问题[J]. 计算机应用, 2019, 39(12): 3584-3589. |
| [16] | 范如梦, 赵春艳, 李飞龙. 启发式回溯算法求解约束满足问题[J]. 计算机应用研究, 2020, 38(4): 1438-1442. |
| [17] | 赵春艳, 范如梦, 刘雅楠. 不同约束紧度下约束满足问题的相变现象[J]. 计算机应用研究, 2020, 37(12): 2739-2743. |
| [18] | 张学才, 赵春艳. 基于动态度的回溯算法求解大值域约束满足问题[J]. 计算机应用研究, 2022, 39(5): 1427-1431. |
| [19] | 林童. 一种基于回溯求解约束满足问题的置信传播算法[J]. 应用数学进展, 2023, 12(3): 993-1002. https://doi.org/10.12677/aam.2023.123101 |
