NPTEL AI:Constraint Satisfaction Assignment Answer

NPTEL AI:Constraint Satisfaction Assignment Answer

by

1. Select the true statements.

  • A constraint in a CSP is a restriction on the values a variable or a combination of variables can take.
  • A solution to a CSP is the set of values assigned to all the variables, such that they satisfy all the constraints.
  • A solution to a CSP is the set of values, assigned to some variables, that satisfy some of the constraints.
  • In a Binary CSP, each constraint is between two variables.
  • In a Binary CSP, the domain of each variable contains exactly two values.
Answer :- A constraint in a CSP is a restriction on the values a variable or a combination of variables can take, A solution to a CSP is the set of values assigned to all the variables, such that they satisfy all the constraints, In a Binary CSP, each constraint is between two variables,

2. Two constraint networks over the same set of variables are equivalent IF AND ONLY IF __________ .

  • the constraints in the two networks are the same
  • the constraint graphs of the two networks are the same
  • the matching diagrams of the two networks are the same
  • the solutions expressed by the two networks are the same
Answer :- the solutions expressed by the two networks are the same

3. Select the true statements.

  • Every constraint network has a dual binary constraint network.
  • Every constraint network can be converted to an equivalent binary constraint network over the same set of variables.
Answer :- Every constraint network has a dual binary constraint network.

4. Consider the constraint network R = ( {x1, x2, x3}, {D1, D2, D3}, {R12, R23} ) where D1=D2=D3={t,h,e,b,a,n,d} and R12 = { (b,a), (b,e), (h,a), (h,e) } and R23 = { (a,t), (e,n) }. How many solutions does this network have? Enter a number.

Answer :- (Type: Numeric) 4

5. R123 = { (b,a,n), (b,a,t), (b,e,t), (h,a,t), (h,e,n) } is a relation whose scope is (x1, x2, x3), let R12, R23 and R13 be the projections of R123. Select the true statements.

  • The composition of R12, R23, R13 is a equal to R123
  • The composition of R12, R23, R13 is a subset of R123
  • The composition of R12, R23, R13 is a superset of R123
  • None of the above
Answer :- The composition of R12, R23, R13 is a superset of R123

6. An L-shaped solid block is shown in the figure. The view is from a camera located above the block, that is looking down at the roof and walls of the block, the bottom side is hidden from the camera.

Determine the edge labels (convex, concave, arrow) and junction labels in the 2D line drawing. What is the label of the edge AD?

  • Convex
  • Concave
  • Arrow from A to D
  • Arrow from D to A
Answer :- Arrow from A to B

8. What is the label of the edge BC?

  • Convex
  • Concave
  • Arrow from B to C
  • Arrow from C to B
Answer :- Convex

9. Determine the labels of the junctions A, B, C, D and E? Enter the junction labels of A, B, C, D and E, in that order, as a comma separated list.

Answer format: L2,T4,W1,L3,T2

Answer :- (Type: String) Y1,W1,Y3,W3,L1

10. Solve the 2D line drawing by assigning edge labels and junction labels from the catalog. Enumerate all the solutions. How many solutions exist for this line drawing?

fig w01 line drawing good 5

Enter the number of solutions in the textbox.

Answer :- (Type: Numeric) 2

11. Solve the 2D line drawing by assigning edge labels and junction labels from the catalog. Enumerate all the solutions. How many solutions exist for this line drawing?

fig w01 line drawing error 6

Enter the number of solutions in the textbox.

Answer :- (Type: Numeric) 0

12. An assignment to a subset of variables of a network is consistent if __________ .

  • every variable gets a value only from its domain.
  • every constraint whose scope is contained in the subset is satisfied.
  • if at least one constraint is satisfied by the assignment.
  • if it can be extended to every other variable.
Answer :- every constraint whose scope is contained in the subset is satisfied.

13. Which of the following statements are true for a CSP having N variables each of which has a domain of size K?

  • The number of different relations is 2k2n2, while the number of different binary constraint networks is 2kn
  • The number of different relations is 2kn, while the number of different binary constraint networks is  2k2n2
  • The number of different relations is k2n2, while the number of different binary constraint networks is k^n
  • The number of different relations is kn, while the number of different binary constraint networks is k2n2
Answer :- The number of different relations is 2kn, while the number of different binary constraint networks is  2k2n2

14. An edge in a matching diagram __________ .

  • exists between variables that are related
  • exists between consistent values of two variables
  • matches the variables with the same arity
  • identifies two variables that have same number of values
Answer :- exists between consistent values of two variables

15. A composition of two relations RXY and RYZ identifies __________ .

  • paths of length 2 from values in X to values in Y in the matching diagram
  • paths of length 2 from values in X to values in X in the matching diagram
  • paths of length 2 from values in X to values in Z in the matching diagram
  • paths of length 2 from values in Y to values in Z in the matching diagram
Answer :- paths of length 2 from values in X to values in Z in the matching diagram

16. Projecting a relation ρ onto each pair of its variables will give the _________ of relation ρ.

  • Equivalent network
  • Primal constraint
  • Dual constraint
  • Minimal network
  • None of the above
Answer :- None of the above

17. Given a constraint network with four variables x1, x2, x3 and x4 having domains D1={a,b,c}, D2={1,2,3}, D3={4,5,6}, and D4={A,B,C}, and one constraint ρ1234 ={(a,2,5,A), (b,1,5,B), (a,1,4,A)}.

The number of constraints in the projection network P(ρ) for the above network is __________ .

Answer :- (Type: Numeric) 6

18. Given the above network with constraint ρ1234, which of the following tuple(s) will be present in the solution of projection network P(ρ) of ρ:

  • (a,1,4,A)
  • (a,1,5,A)
  • (a,2,4,A)
  • (b,1,4,B)
Answer :- (a,1,4,A) (a,1,5,A)

19. Given a constraint network with three variables x1, x2 and x3 all defined on the same domain values {red,blue}, the constraints in the network are R12=R23={(red,blue), (blue,red)}. If you construct a minimal network for the given CSP, the number of edges in the matching diagram of the minimal network will be __________ .

Answer :- 6

20. If a CSP is arc consistent then __________ .

  • it always has a solution
  • it always has a unique solution
  • it may not have a solution
  • none of the above
Answer :- it may not have a solution

21. What are the colours in the domain of region A after arc consistency has been achieved on the corresponding CSP? Mark all colours in the domain of A.

  • red
  • blue
  • green
  • none of the above
Answer :- blue green

Leave a Comment