[Part5 Theory] AllDifferent Constraint

Pregunta 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)?

An inconsistency is detected.

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

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

Pregunta 2: AllDifferent: Forward-Checking Consistency

Select all the true statements:

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

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

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).

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.

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.

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.

Pregunta 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)?

An inconsistency is detected.

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

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

Pregunta 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 label of value 2 in the residual graph is 2.

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

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

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

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

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

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

Pregunta 5: AllDifferent: Régin's Domain-Consistent Filtering Algorithm

Select all the true statements:

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 alternating path.

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.

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.

Fecha de entrega	Sin fecha de envío
Tiempo límite de envío	Se han enviado 2 tareas cada 1 hora (s)

Información

Inicia sesión

Pregunta 1: AllDifferent: Bound Consistency

Pregunta 2: AllDifferent: Forward-Checking Consistency

Pregunta 3: AllDifferent: Domain Consistency

Pregunta 4: AllDifferent: Data Structures for Régin's Domain-Consistent Filtering Algorithm

Pregunta 5: AllDifferent: Régin's Domain-Consistent Filtering Algorithm

Información

Inicia sesión