[Part5 Theory] AllDifferent Constraint

Spørsmål 1: AllDifferent: Bound Consistency

Consider the following domains:

D(X1) = {0,2}, D(X2) = {0,2}, D(X3) = {2,3,4,5}

What is the domain of X3 after bound-consistent filtering of the constraint AllDifferent(X1,X2,X3)?

D(X3) = {3,4,5}

An inconsistency is detected.

D(X3) = {2,3,4,5}

Spørsmål 2: AllDifferent: Forward-Checking Consistency

Select all the true statements:

The forward-checking filtering algorithm for AllDifferent removes the same values as the binary decomposition.

The forward-checking filtering algorithm removes all the infeasible values: it achieves domain consistency.

Deactivating a constraint is not a reversible operation: the constraint will never be called again for the remainder of the search tree, even after backtracking.

A deactivated constraint will not be propagated, but since it is in the stacks of the constraints on the variables, the constraint will nevertheless be scanned.

Whatever the (deterministic) heuristic used for the variable and value selection for the n-Queens problem, the search tree explored with forward-checking filtering for AllDifferent is the same as with the binary decomposition (same number of nodes).

The forward-checking filtering algorithm without the sparse-set trick (thus scanning all the variables every time in order to possibly remove a value) is faster than the binary decomposition.

Spørsmål 3: AllDifferent: Domain Consistency

Consider the following domains:

D(X1) = {0,2}, D(X2) = {0,2}, D(X3) = {2,3,4,5}

What is the domain of X3 after domain-consistent filtering of the constraint AllDifferent(X1,X2,X3)?

D(X3) = {2,3,4,5}

D(X3) = {3,4,5}

An inconsistency is detected.

Spørsmål 4: AllDifferent: Data Structures for Régin's Domain-Consistent Filtering Algorithm

Consider the following domains:

D(X1) = {0,2}, D(X2) = {0,2}, D(X3) = {1,2,3,4}

and the constraint AllDifferent(X1,X2,X3). Select all the true statements for domain-consistent filtering:

The node indices 2 and 4 are in two different strongly connected components.

The number of strongly connected components in the residual graph is 2.

The node label of value 2 in the residual graph is 6.

The number of strongly connected components in the residual graph is 3.

The node label of value 2 in the residual graph is 5.

The node indices 2 and 4 are in the same strongly connected component.

The node label of value 2 in the residual graph is 2.

Spørsmål 5: AllDifferent: Régin's Domain-Consistent Filtering Algorithm

Select all the true statements:

Given a maximum matching (in the variable-value graph), the domain-consistent filtering algorithm for \(AllDifferent(X_1,\dots,X_n)\) can be implemented to run in \(O(|D(X_1)|+\dots+|D(X_n)|)\) time.

The maximum matching needs to be stored in a stateful data-structure since it may not be valid anymore on backtrack.

An edge belongs to some maximum matching (in the variable-value graph) if and only if for every maximum matching, it belongs to an even alternating cycle.

An edge belongs to some maximum matching (in the variable-value graph) if and only if for every maximum matching, it belongs to an alternating path.

Frist	Ingen frist
Innleveringsgrense	2 innleveringer hver 1 time(r)

Informasjon

Logg inn

Spørsmål 1: AllDifferent: Bound Consistency

Spørsmål 2: AllDifferent: Forward-Checking Consistency

Spørsmål 3: AllDifferent: Domain Consistency

Spørsmål 4: AllDifferent: Data Structures for Régin's Domain-Consistent Filtering Algorithm

Spørsmål 5: AllDifferent: Régin's Domain-Consistent Filtering Algorithm

Informasjon

Logg inn