Engineering Commons^™

On Path Consistency For Binary Constraint Satisfaction Problems, Christopher G. Reeson

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Constraint satisfaction problems (CSPs) provide a flexible and powerful framework for modeling and solving many decision problems of practical importance. Consistency properties and the algorithms for enforcing them on a problem instance are at the heart of Constraint Processing and best distinguish this area from other areas concerned with the same combinatorial problems. In this thesis, we study path consistency (PC) and investigate several algorithms for enforcing it on binary finite CSPs. We also study algorithms for enforcing consistency properties that are related to PC but are stronger or weaker than PC.

We identify and correct errors in the literature …

A Comparative Study Of Generalized Arc-Consistency Algorithms, Olufikayo S. Adetunji

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

In this thesis, we study several algorithms for enforcing Generalized Arc­-Consistency (GAC), which is the most popular consistency property for solving Constraint Satisfaction Problems (CSPs) with backtrack search. The popularity of such algorithms stems from their relative low cost and effectiveness in improving the performance of search. Virtually all commercial and public- domain constraint solvers include some implementation of a generic GAC algorithm. In recent years, several algorithms for enforcing GAC have been proposed in the literature that relies on increasingly complex data structures and mechanisms to improve performance. In this thesis, we study, assess, and compare a basic algorithm …