Constraint Satisfaction Problems Questions and Answers

Q: How is a constraint satisfaction problem specified?

A constraint problem gives a set of variables, a domain of permitted values for each and a set of constraints restricting which combinations are allowed, and a solution is an assignment satisfying all of them. The classical search formulation is different, and rules and objectives belong to other frameworks. Adopting a representation in which the structure of a problem is visible, rather than hidden inside a successor function, is what makes the specialised algorithms possible.

Q: What advantage does the constraint formulation have over general search?

Because the state is described by variables, an algorithm can detect that a partial assignment already violates a constraint and discard every completion of it at once, which an atomic representation cannot express. The space is the same size, search is still required and the problems remain NP hard in general. Recognising that the gain comes from the representation rather than from any cleverness in the algorithm connects this topic directly to the earlier discussion of state representations.

Q: What is a constraint graph?

Drawing a node for each variable and an edge for each binary constraint exposes the structure of the problem, and that structure determines which algorithms will be efficient. A tree shaped graph is solvable in linear time, and a nearly tree shaped one is nearly as easy. Search trees, statistics and domain contents are different objects. Making the structure of a problem visible so that it can be exploited is the practical reason for drawing the graph at all.

Q: What is a global constraint?

A global constraint such as all different relates any number of variables and has a specialised propagation algorithm far stronger than decomposing it into pairwise inequalities. It need not involve every variable, and it can in principle be decomposed, though at a heavy loss of propagation strength. Providing an efficient algorithm for a commonly occurring pattern, rather than expressing it in primitives, is what makes constraint programming systems practical.

Q: Why is all different stronger than a set of pairwise inequalities?

Three variables each with the same two valued domain are pairwise satisfiable but cannot all differ, and only a global algorithm using matching theory detects that immediately. Readability and storage are genuine but minor benefits. The example is the standard demonstration that decomposition loses information, and it justifies the whole apparatus of specialised global constraints in constraint programming systems.

Q: What is backtracking search in a constraint problem?

Backtracking chooses an unassigned variable, tries each value consistent with the assignment so far and recurses, returning when no value works. It is depth first search specialised to this representation, and its memory is linear. Backward search, restarts and recording failures describe other techniques, the last being no-good learning. A basic algorithm that is transformed by the heuristics layered on it is the pattern of this whole topic.

Q: What does the minimum remaining values heuristic choose?

Choosing the most constrained variable first means failure is detected as early as possible, pruning the tree near the root where the saving is greatest. It is often called the fail first heuristic for that reason. Constraint counts are the degree heuristic, value selection is a separate decision, and recency is not used. Ordering so that failure comes early, rather than late, is counter-intuitive until one notices that the cost of failure grows with the depth at which it occurs.

A cryptarithmetic problem of the type SEND + MORE MONEY Can be solved efficiently using

A.depth first technique
B.breadth first technique
C.constraint satisfaction technique
D.bidirectional technique

Exam Year(s)

UGC NET - 2012,

Answer: C

A cryptarithmetic problem such as SEND + MORE = MONEY is solved efficiently by constraint satisfaction. Each letter must be given a different digit so that the sum is right, and the constraints on the digits and on the carries cut down the search at once. Depth first, breadth first and bidirectional search try assignments blindly and do not use the constraints in the same way, so they take much longer. The keyed answer is the constraint satisfaction technique.

Discuss in Forum

The map colouring problem can be solved using which of the following technique ?

A.Means-end analysis
B.Constraint satisfaction
C.AO* search
D.Breadth first search

Exam Year(s)

UGC NET - 2013,

Answer: B

The map colouring problem can be solved by constraint satisfaction, which is option (B). The regions are the variables, the colours are their values, and the constraint is that two neighbouring regions must have different colours, so a solution is an assignment satisfying all the constraints.

Means-end analysis reduces the difference between a state and the goal, AO* is a search of AND-OR graphs, and breadth first search is a blind search that would not use the constraints. So (A), (C) and (D) are less suited to the problem.

Discuss in Forum

Assume that each alphabet can have a value between 0 to 9 in a cryptoarithmetic problem

CROSS

+ROADS

--------

DANGER

Which of the following statement is true ?

(i) No two alphabets can have the same numeric value.
(ii) Any two alphabets may have the same numeric value.
(iii) D = 0
(iv) D = 1

A.(i) and (iii)
B.(i) and (iv)
C.(ii) and (iii)
D.(ii) and (iv)

Exam Year(s)

UGC NET - 2013,

Answer: B

The statements true are (i) and (iv): no two letters can share a value, and D = 1. The sum CROSS + ROADS = DANGER has nine different letters (C, R, O, S, A, D, N, G, E), and in a cryptarithmetic puzzle each letter stands for a different digit, so statement (i) holds and (ii) fails. Adding two five-digit numbers gives at most a six-digit number whose leading digit is the carry, which can only be 1, so D = 1 and not 0.

One solution is 96233 + 62513 = 158746, in which D = 1. The options with (iii) or (ii) are therefore wrong.

Discuss in Forum

How is a constraint satisfaction problem specified?

A.By variables, their domains and constraints between them
B.By an initial state, actions, a goal test and a path cost
C.By a set of rules and a procedure for applying them
D.By an objective function to be maximised over a state space

Answer: A

A constraint problem gives a set of variables, a domain of permitted values for each and a set of constraints restricting which combinations are allowed, and a solution is an assignment satisfying all of them. The classical search formulation is different, and rules and objectives belong to other frameworks. Adopting a representation in which the structure of a problem is visible, rather than hidden inside a successor function, is what makes the specialised algorithms possible.

Discuss in Forum

What advantage does the constraint formulation have over general search?

A.The problem can be solved in polynomial time in every case
B.Inconsistent partial assignments can be pruned without enumeration
C.The state space is smaller than in the general formulation
D.Solutions can be found without any search being performed

Answer: B

Because the state is described by variables, an algorithm can detect that a partial assignment already violates a constraint and discard every completion of it at once, which an atomic representation cannot express. The space is the same size, search is still required and the problems remain NP hard in general. Recognising that the gain comes from the representation rather than from any cleverness in the algorithm connects this topic directly to the earlier discussion of state representations.

Discuss in Forum

What is a constraint graph?

A.A plot of the number of consistent assignments against depth
B.The graph of values in each variable's domain
C.Variables as nodes with edges joining constrained pairs
D.The graph of the search tree explored during backtracking

Answer: C

Drawing a node for each variable and an edge for each binary constraint exposes the structure of the problem, and that structure determines which algorithms will be efficient. A tree shaped graph is solvable in linear time, and a nearly tree shaped one is nearly as easy. Search trees, statistics and domain contents are different objects. Making the structure of a problem visible so that it can be exploited is the practical reason for drawing the graph at all.

Discuss in Forum

What is a global constraint?

A.One that applies to every variable in the problem
B.One that cannot be expressed as a set of binary constraints
C.One imposed by the environment rather than the problem
D.One relating an arbitrary number of variables

Answer: D

A global constraint such as all different relates any number of variables and has a specialised propagation algorithm far stronger than decomposing it into pairwise inequalities. It need not involve every variable, and it can in principle be decomposed, though at a heavy loss of propagation strength. Providing an efficient algorithm for a commonly occurring pattern, rather than expressing it in primitives, is what makes constraint programming systems practical.

Discuss in Forum

Why is all different stronger than a set of pairwise inequalities?

A.Its propagation can detect infeasibility the pairwise version misses
B.It is easier for a human being to read and to write
C.It requires fewer constraints to be stored in memory
D.It applies to variables with continuous domains as well

Answer: A

Three variables each with the same two valued domain are pairwise satisfiable but cannot all differ, and only a global algorithm using matching theory detects that immediately. Readability and storage are genuine but minor benefits. The example is the standard demonstration that decomposition loses information, and it justifies the whole apparatus of specialised global constraints in constraint programming systems.

Discuss in Forum

What is backtracking search in a constraint problem?

A.Recording every failed assignment so it is never repeated
B.Assigning variables one at a time and undoing on failure
C.Searching backwards from a complete assignment to the empty one
D.Repeatedly restarting from a different variable ordering

Answer: B

Backtracking chooses an unassigned variable, tries each value consistent with the assignment so far and recurses, returning when no value works. It is depth first search specialised to this representation, and its memory is linear. Backward search, restarts and recording failures describe other techniques, the last being no-good learning. A basic algorithm that is transformed by the heuristics layered on it is the pattern of this whole topic.

Discuss in Forum

10.

What does the minimum remaining values heuristic choose?

A.The value that rules out the fewest options for others
B.The variable that was assigned least recently
C.The variable with the fewest legal values left
D.The variable involved in the fewest constraints

Answer: C

Choosing the most constrained variable first means failure is detected as early as possible, pruning the tree near the root where the saving is greatest. It is often called the fail first heuristic for that reason. Constraint counts are the degree heuristic, value selection is a separate decision, and recency is not used. Ordering so that failure comes early, rather than late, is counter-intuitive until one notices that the cost of failure grows with the depth at which it occurs.

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