Computational Complexity Analysis of Backtrack-free and Random-walk Strategies on Constraint Satisfaction Problems with Growing Domains
Xu We · 2014
Constraint satisfaction problems(CSP)with growing domains are a kind of important practical models in complexity theory,but the algorithm performance research is still rare.By the study on a typical CSP with growing domains,RB model,it is discovered that the backtrack-free strategy works better than the random-walk strategy when the size of problems is huge.Different from CSP with fixed domains such as SAT,this is a special property to CSP with growing domain.Moreover,the performances in experiments and theoretic analysis for these two strategies were also given.