Show simple item record

Inherent Choice in the Search Space of Constraint Satisfaction Problem Instances

dc.contributor.authorBoukeas, George
dc.contributor.authorStamatopoulos, Panagiotis
dc.contributor.authorHalatsis, Constantin
dc.contributor.authorZissimopoulos, Vassilis
dc.description.abstractConstructive methods obtain solutions to constraint satisfaction problem instances by iteratively extending consistent partial assignments. In this research, we study the solution paths in the search space of constructive methods and examine their distribution among the assignments of the search space. By properly employing the entropy of this distribution, we derive measures of the average amount of choice available within the search space for constructing a solution. The derived quantities directly reflect both the number and the distribution of solutions, an ”open question” in the phase transition literature. We show that constrainedness, an acknowledged predictor of computational cost, is an aggregate measure of choice deficit. This establishes a connection between an algorithm-independent property of the search space, such as the inherent choice available for constructing a solution, and the algorithm-dependent amount of resources required to actually construct a solution.en_UK
dc.publisherSpringer Berlin Heidelbergen_UK
dc.relation.ispartofseriesMethods and Applications of Artificial Intelligence;pp 362-370
dc.rights© Springer-Verlag Berlin Heidelbergen_UK
dc.subjectConstraint satisfactionen_UK
dc.subjectMathematical foundationsen_UK
dc.titleInherent Choice in the Search Space of Constraint Satisfaction Problem Instancesen_UK
dc.typeBook chapteren_UK

Files in this item


This item appears in the following Collection(s)

Show simple item record

© Springer-Verlag Berlin Heidelberg
Except where otherwise noted, this item's license is described as © Springer-Verlag Berlin Heidelberg