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.