Constraint Satisfaction Problems Questions and Answers

Q: Consider the following statements about constraint satisfaction. 1. The minimum remaining values heuristic selects the most constrained variable 2. Arc consistency alone decides satisfiability for tree structured problems 3. Forward checking detects inconsistency between two unassigned variables Which of the statements given above is or are correct?

The first two are correct. Forward checking propagates only from the newly assigned variable to its neighbours, so an inconsistency between two unassigned variables is missed until one is reached, and arc consistency is what catches it. Knowing precisely where each level of inference stops looking is what makes the progression from forward checking through arc consistency to path consistency a sequence rather than a list.

Q: Consider the following pairings in constraint satisfaction. Forward checking - prunes neighbours of the assigned variable Arc consistency - prunes values with no support in a neighbour Backjumping - returns to a variable in the conflict set Min conflicts - systematic search over partial assignments How many of the pairs given above are correctly matched?

The first three are correct. Min conflicts is a local search operating on complete assignments, repairing violations, rather than a systematic method building partial ones. The distinction matters because the two families have entirely different guarantees: systematic search can prove unsatisfiability while local search can only fail to find a solution, which is a much weaker statement.

Q: What is node consistency?

Node consistency is the weakest condition, requiring only that unary constraints be applied to each domain, which is done once at the start. Arc consistency handles binary constraints and path consistency triples. Graph connectivity, domain emptiness and pairwise assignment are different notions. A hierarchy of consistency conditions, each considering more variables at once, gives a scale on which the cost and the pruning power can be traded.

Q: Which consistency condition considers triples of variables?

Path consistency looks at triples: for every consistent assignment to two variables there must be a value for a third consistent with both, which prunes more than arc consistency and costs considerably more. It is the k equal to three case of k consistency. Graph paths and traversal are different notions. Each step up the hierarchy considers one more variable and costs an order more work, which is why the higher levels are rarely enforced in full.

Q: How is the general consistency hierarchy defined?

The general condition says that any consistent partial assignment of size k minus one can be extended to any further variable, with node, arc and path consistency being the cases of one, two and three. Strong n consistency for n variables permits a backtrack free solution but costs exponential effort to establish. Constraint arity, block assignment and domain size are different quantities. A parameterised family in which the extremes are trivial and intractable leaves the useful cases in the middle.

Q: Why is strong n consistency not used in practice?

Enforcing consistency at every level up to the number of variables takes exponential time, so the theoretical prize of a backtrack free search is paid for in advance at the same price. In practice arc consistency, occasionally strengthened, is the sweet spot. Constraint arity, domain uniformity and solution knowledge are not the obstacle. A guarantee whose cost equals the cost of the thing it guarantees is a theoretical result rather than a practical technique, and recognising that is what keeps effort where it pays.

Q: Where does the practical sweet spot of propagation lie?

Arc consistency prunes substantially at a cost that is polynomial and modest, and specialised propagators for global constraints add strength where it is worth having. Node consistency alone is far too weak, and the higher levels cost more than they save on most problems. Finding the level of inference at which the pruning gained exceeds the effort spent is an empirical question whose answer has been remarkably stable across the field.

41.

Consider the following statements about constraint satisfaction.

1. The minimum remaining values heuristic selects the most constrained variable

2. Arc consistency alone decides satisfiability for tree structured problems

3. Forward checking detects inconsistency between two unassigned variables

Which of the statements given above is or are correct?

A.1 and 2 only
B.1 and 3 only
C.2 and 3 only
D.1, 2 and 3

Answer: A

The first two are correct. Forward checking propagates only from the newly assigned variable to its neighbours, so an inconsistency between two unassigned variables is missed until one is reached, and arc consistency is what catches it. Knowing precisely where each level of inference stops looking is what makes the progression from forward checking through arc consistency to path consistency a sequence rather than a list.

Discuss in Forum

42.

Match each heuristic with what it selects.

List I

A. Minimum remaining values

B. Degree heuristic

C. Least constraining value

D. Min conflicts

List II

P. the variable with fewest legal values

Q. the variable constraining most others

R. the value ruling out fewest options

S. the value violating fewest constraints

Select the correct match.

A.A-P, B-R, C-Q, D-S
B.A-P, B-Q, C-R, D-S
C.A-Q, B-P, C-S, D-R
D.A-R, B-S, C-P, D-Q

Answer: B

The first three guide systematic backtracking, choosing a variable then a value, while the fourth belongs to local search over complete assignments. Two heuristics choose variables and two choose values, and noticing which is which prevents them being confused. The variable heuristics seek early failure and the value heuristics seek to avoid it, which is the asymmetry that makes the set coherent.

Discuss in Forum

43.

Consider the following pairings in constraint satisfaction.

Forward checking - prunes neighbours of the assigned variable

Arc consistency - prunes values with no support in a neighbour

Backjumping - returns to a variable in the conflict set

Min conflicts - systematic search over partial assignments

How many of the pairs given above are correctly matched?

A.Only two
B.All four
C.Only three
D.Only one

Answer: C

The first three are correct. Min conflicts is a local search operating on complete assignments, repairing violations, rather than a systematic method building partial ones. The distinction matters because the two families have entirely different guarantees: systematic search can prove unsatisfiability while local search can only fail to find a solution, which is a much weaker statement.

Discuss in Forum

44.

Three of the following are forms of inference during search. Which is the odd one out?

Least constraining value

Forward checking

Arc consistency

Path consistency

A.Forward checking
B.Arc consistency
C.Path consistency
D.Least constraining value

Answer: D

Forward checking and the consistency conditions all deduce that certain values cannot appear in any solution and delete them. Least constraining value is an ordering heuristic that decides what to try first and deletes nothing. Separating inference, which shrinks the problem, from heuristics, which reorder the search, is the clearest way to organise the techniques, since the two can be combined freely.

Discuss in Forum

45.

Assertion (A): The minimum remaining values heuristic is often called fail first.

Reason (R): Choosing the most constrained variable makes any failure appear as early as possible.

Select the correct answer from the options below.

A.Both A and R are true, and R is the correct explanation of A
B.Both A and R are true, but R is not the correct explanation of A
C.A is true but R is false
D.A is false but R is true

Answer: A

Both are true and the second is the reason for the name. Because the subtree below a node grows exponentially with depth, detecting an inconsistency near the root removes far more work than detecting the same one deeper. Seeking failure rather than avoiding it is counter-intuitive until the exponential is taken into account, which makes this a good test of whether the complexity argument has been absorbed.

Discuss in Forum

46.

What is node consistency?

A.Every pair of adjacent nodes has a consistent assignment
B.Every value in a domain satisfies the unary constraints on it
C.Every node in the constraint graph has at least one neighbour
D.Every variable has at least one value left in its domain

Answer: B

Node consistency is the weakest condition, requiring only that unary constraints be applied to each domain, which is done once at the start. Arc consistency handles binary constraints and path consistency triples. Graph connectivity, domain emptiness and pairwise assignment are different notions. A hierarchy of consistency conditions, each considering more variables at once, gives a scale on which the cost and the pruning power can be traded.

Discuss in Forum

47.

Which consistency condition considers triples of variables?

A.Every variable lies on a path to every other variable
B.Every arc along a path has been made consistent in both directions
C.Every consistent pair extends consistently to any third variable
D.Every path in the constraint graph can be traversed consistently

Answer: C

Path consistency looks at triples: for every consistent assignment to two variables there must be a value for a third consistent with both, which prunes more than arc consistency and costs considerably more. It is the k equal to three case of k consistency. Graph paths and traversal are different notions. Each step up the hierarchy considers one more variable and costs an order more work, which is why the higher levels are rarely enforced in full.

Discuss in Forum

48.

How is the general consistency hierarchy defined?

A.Every constraint involves at most k variables in the problem
B.The problem can be solved by assigning k variables at a time
C.Every variable has at least k values remaining in its domain
D.Any consistent assignment to k minus one variables extends to a kth

Answer: D

The general condition says that any consistent partial assignment of size k minus one can be extended to any further variable, with node, arc and path consistency being the cases of one, two and three. Strong n consistency for n variables permits a backtrack free solution but costs exponential effort to establish. Constraint arity, block assignment and domain size are different quantities. A parameterised family in which the extremes are trivial and intractable leaves the useful cases in the middle.

Discuss in Forum

49.

Why is strong n consistency not used in practice?

A.Establishing it costs as much as solving the problem
B.It applies only to problems with binary constraints
C.It requires every domain to contain the same values
D.It cannot be checked without first finding a solution

Answer: A

Enforcing consistency at every level up to the number of variables takes exponential time, so the theoretical prize of a backtrack free search is paid for in advance at the same price. In practice arc consistency, occasionally strengthened, is the sweet spot. Constraint arity, domain uniformity and solution knowledge are not the obstacle. A guarantee whose cost equals the cost of the thing it guarantees is a theoretical result rather than a practical technique, and recognising that is what keeps effort where it pays.

Discuss in Forum

50.

Where does the practical sweet spot of propagation lie?

A.Strong n consistency established before the search begins
B.Arc consistency, sometimes strengthened for particular constraints
C.Node consistency alone, since anything more would be too expensive
D.Full path consistency enforced after every assignment

Answer: B

Arc consistency prunes substantially at a cost that is polynomial and modest, and specialised propagators for global constraints add strength where it is worth having. Node consistency alone is far too weak, and the higher levels cost more than they save on most problems. Finding the level of inference at which the pruning gained exceeds the effort spent is an empirical question whose answer has been remarkably stable across the field.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Constraint Satisfaction Problems Questions and Answers || Constraint Satisfaction Problems MCQ Questions and Answers || Constraint Satisfaction Problems GK Questions and Answers || Constraint Satisfaction Problems GK MCQ Questions || Constraint Satisfaction Problems Multiple Choice Questions and Answers || Constraint Satisfaction Problems GK || GK on Constraint Satisfaction Problems || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Constraint Satisfaction Problems Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications