Computer Science – Computational Complexity
Scientific paper
2000-05-09
Annals of Mathematics and Artificial Intelligence, 33:21-37, 2001.
Computer Science
Computational Complexity
20 pages, submitted to Annals of Mathematics and Artificial Intelligence
Scientific paper
In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. It is proved that Model GB in which each constraint is easy to satisfy exhibits non-trivial behaviour (not trivially satisfiable or unsatisfiable) as the number of variables approaches infinity. A detailed analysis to obtain an asymptotic estimate (good to 1+o(1)) of the average number of nodes in a search tree used by the backtracking algorithm on Model GB is also presented. It is shown that the average number of nodes required for finding all solutions or proving that no solution exists grows exponentially with the number of variables. So this model might be an interesting distribution for studying the nature of hard instances and evaluating the performance of CSP algorithms. In addition, we further investigate the behaviour of the average number of nodes as r (the ratio of constraints to variables) varies. The results indicate that as r increases, random CSP instances get easier and easier to solve, and the base for the average number of nodes that is exponential in r tends to 1 as r approaches infinity. Therefore, although the average number of nodes used by the backtracking algorithm on random CSP is exponential, many CSP instances will be very easy to solve when r is sufficiently large.
Li Wangrong
Xu Ke
No associations
LandOfFree
An Average Analysis of Backtracking on Random Constraint Satisfaction Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Average Analysis of Backtracking on Random Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Average Analysis of Backtracking on Random Constraint Satisfaction Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-214434