Informasjon

Frist Ingen frist
Innleveringsgrense Ingen begrensning

Logg inn

[Module9 Theory] Black-Box Search Search


Spørsmål 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, ...) and, given a selected variable V, always tries 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.

Spørsmål 2: Last-Conflict Search and Conflict-Ordering Search

Select all the true statements:

Spørsmål 3: First-Fail Principle

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

Spørsmål 4: 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:

Spørsmål 5: Value Selection Heuristics

Select all the true statements: