Constraint Satisfaction Problems Questions and Answers

Answer: A

A tree decomposition collects variables into overlapping clusters arranged in a tree, so the tree algorithm applies to the clusters and the cost is exponential only in the largest cluster size. That size minus one is the treewidth. Independence, edge deletion and simple ordering are different ideas. A measure of how far a graph is from being a tree, and an algorithm whose cost depends on that measure rather than on size, is a powerful and widely reused construction.

Answer: B

Treewidth measures how nearly tree like a graph is, and a problem of bounded treewidth is solvable in time exponential in that width and linear in the number of variables. Trees have width one. Path lengths, degrees and search depths are different quantities. A single number capturing the structural difficulty of a graph, and appearing in the exponent of an algorithm's complexity, is exactly the kind of parameter that makes structure exploitable.

Answer: C

Plain backtracking undoes the most recent assignment even when it had nothing to do with the failure, whereas backjumping returns directly to a variable in the conflict set and skips the intervening irrelevant work. Forward jumping, restarts and fixed step backtracking are different techniques. Undoing the decision that actually caused a failure, rather than the most recent one, is an idea that reappears in satisfiability solvers as conflict driven learning.

Answer: D

Recording which previously assigned variables eliminated each value gives the set to which the search should jump when every value has been eliminated. Constraint membership and neighbourhood are static properties of the problem, and values do not conflict with one another within a domain. Keeping a record of why a failure occurred, rather than only that it occurred, is what allows the search to respond intelligently rather than blindly.

Answer: A

When a partial assignment is shown to fail, storing it as a no-good prevents the search from reconstructing the same doomed combination by a different route. It is the same idea as clause learning in satisfiability solvers and it can transform performance. Ordering statistics, value pruning and solution caching are different techniques. Converting a failure into a permanent constraint is how a search learns from its own mistakes within a single run.

Answer: B

In local search over complete assignments, selecting a conflicted variable and giving it the value that minimises the number of violated constraints solves very large problems remarkably fast. A million queens is solved in seconds. Variable selection is usually random among conflicted ones, and the other options describe different quantities. A hill climbing rule on the count of violations turns a combinatorial search into an optimisation, with all the advantages and the local optimum risk that implies.

Answer: C

For large n solutions are extremely numerous and almost any starting point is within a few repairs of one, so a greedy repair heuristic succeeds almost immediately. Problems with few solutions or rugged landscapes defeat it. Solutions are many rather than unique, the constraints are binary, and no decomposition exists. That an algorithm's success depends on the solution density of the instance, rather than on the problem class, explains why local search performs so unevenly.

Answer: D

A tightly constrained problem with few solutions has a landscape full of assignments that violate one constraint and cannot be repaired without violating another, and the search stalls. Systematic methods with propagation do better there. Size, constraint arity and domain size affect the cost rather than the character of the difficulty. Matching the method to the instance's solution density, rather than to its size, is the judgement local search requires.

Answer: A

The natural formulation makes a state a consistent partial assignment and an action the assignment of a value to an unassigned variable, with the goal being a complete consistent assignment. That gives a tree of depth equal to the number of variables. The last option describes the local search formulation, which is a different and equally valid choice. Two formulations of the same problem, suiting different algorithms, is common and choosing between them is part of the design.

Answer: B

Since a solution is an assignment of values to all variables, the order in which they were assigned does not appear in it, so the search tree can be pruned to consider only one ordering at each level. That reduces the tree from n factorial times d to the n down to d to the n. Constraint checking happens throughout, orderings give different trees, and variables are central. Recognising a symmetry and refusing to search its equivalent branches is one of the largest available savings.