Information

Deadline No deadline
Submission limit No limitation

Sign in

[Part8] Search


Question 1: Conflict-Ordering Search

Consider seven variables X, Y, Z, A, B, C, D such that:

  • X, Y, Z have the domain \(\{0, 1\}\) and there are no constraints on these variables.
  • A, B, C, D have the domain \(\{0, 1, 2\}\) and there is a single constraint: A, B, C, D are all different, implemented using forward checking.

Consider a conflict-ordering search that, by default, considers the variables in the order given above (first X, then Y, then Z, then A, then B, ...) and always tries, given a selected variable V, Equal(V, V.min()) on the left branch, and NotEqual(V, V.min()) on the right branch.

There are no solutions. How many nodes will be visited by the solver?

Hint: Draw the tree.

Question 2: Last-Conflict Search and Conflict-Ordering Search

Select all the true statements:

Question 3: Discrepancy
insertion

What is the discrepancy limit to generate this binary search tree?

Question 4: First-Fail Principle

Select all variable selection heuristics that are not in the spirit of the first-fail principle:

Question 5: Search-Tree Size

Consider a model with 10 decision variables X1, X2, ..., X10 and the AllDifferent([X1,X2,...,X10]) constraint. Select all the true statements:

Question 6: Value Selection Heuristics

Select all the true statements: