An examination of probabilistic value-ordering heuristic

Searching for solutions to constraint satisfaction problems (CSPs) is NP-hard in general. Heuristics for variable and value ordering have proven useful by guiding towards more fruitful areas of the search space and hence reducing the amount of time spent searching for solutions. This thesis introduces a new approximation method for static value ordering that decomposes the CSP into a set of subproblems and shows that it performs better on average than a competing method of Dechter and Pearl [11]. We use a probabilistic approximation method as a unifying framework for comparing several static heuristics. We examine the accuracy of the approximations as well as their ability to impart an ordering of values that requires fewer backtracks on average in the search process than random.;Bayesian networks are probabilistic inference structures which provide a way of representing and computing joint probabilities for random variables. We combine our decomposition heuristic into a Bayesian network representation that uses information about the current state of the search to advise on the next move. (Abstract shortened by UMI.).