An average analysis of backtracking on random constraint satisfaction problems

Authors
Citation
K. Xu et W. Li, An average analysis of backtracking on random constraint satisfaction problems, ANN MATH A, 33(1), 2001, pp. 21-37
Citations number
18
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Engineering Mathematics
Journal title
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
ISSN journal
1012-2443 → ACNP
Volume
33
Issue
1
Year of publication
2001
Pages
21 - 37
Database
ISI
SICI code
1012-2443(2001)33:1<21:AAAOBO>2.0.ZU;2-G
Abstract
In this paper we propose a random CSP model, called Model GB, which is a na tural generalization of standard Model B. This paper considers Model GB in the case where each constraint is easy to satisfy. In this case Model GB ex hibits non-trivial behaviour (not trivially satisfiable or unsatisfiable) a s the number of variables approaches infinity. A detailed analysis to obtai n 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 prese nted. 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 CS P algorithms. In addition, we further investigate the behaviour of the aver age number of nodes as r (the ratio of constraints to variables) varies. Th e 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 expo nential in n tends to 1 as r approaches infinity. Therefore, although the a verage 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 suffic iently large.