2013/09/11 by Junping Zhou, Weihua Su, Zhou, Junping +3
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences #cs.AI
paper · pdf · doi:10.48550/arxiv.1309.2747
14 pages, 2 figures, 3 tables
arxiv created 2013/09/11 · openalex publication_date 2013/09/11 · arxiv updated 2013/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a new approximate method for counting the number of the solutions for constraint satisfaction problem (CSP). The method derives from the partition function based on introducing the free energy and capturing the relationship of probabilities of variables and constraints, which requires the marginal probabilities. It firstly obtains the marginal probabilities using the belief propagation, and then computes the number of solutions according to the partition function. This allows us to directly plug the marginal probabilities into the partition function and efficiently count the number of solutions for CSP. The experimental results show that our method can solve both random problems and structural problems efficiently.