Tag: Academic

The binary constraint satisfaction problem (bcsp) is an important area of research because so many problems can be represented in this form [Kumar92].

General Definitions arc consistency The domains of a variable Vi is such that for each constraint Ci,j Vi is consistent with the constraint for some permissible value of Vj for every value in the domain of Vi That is for every value x in Di (the domain of i) there exists some y in Dj such that Ci,j is satisfied.

Preface This section contains pseudocode of the algorithms used in the paper as well as a brief discussion of each algorithm. Definitions for the Algorithms These definition are based on the descriptions in [Prosser93] and [Kondrak97].

Preface This section outlines the algorithms used to generate the problems the various algorithms were tested against. known-vars A set containing the variables for which a constraint involving them has been generated.

Results Hypotheses 1 and 2 The hypothesis that achieving arc consistency using AC-3 is sufficient to solve the Zebra problem can be quickly disproved using the benchmark Zebra problem presented earlier in this paper.

Bibliography [Kondrak94] Kondrak Grzegorz A Theoretical Evaluation of Selected Backtracking Algorithms. Technical Report TR94-10, University of Alberta Fall 1994. [Kondrak97] Kondrak Grzegorz van Beek Peter A Theoretical Evaluation of Selected Backtracking Algorithms.