Informações

Prazo de entrega Sem prazo
Limite de submissão No limitation

Entrar

[Module3 Theory] Consistency, Element and Sum Constraints


Questão 1: 1D Element: Domain Consistency

Assume an Element constraint for \(T[y]=z\), with:

  • \(D(y) = \{0,1,2,3,4\}\)
  • \(T = [5,5,5,10,8]\)
  • \(D(z) = \{5,10\}\)

What is the domain of \(y\) after a domain-consistent filtering?

Questão 2: 2D Element: Domain Consistency

Assume an Element constraint for \(T[x][y]=z\), with:

  • \(D(x) = \{0,1,2\}\)
  • \(D(y) = \{3\}\)
  • \(T = [[1,8,9,6],[1,9,2,4],[9,8,9,8],[1,9,2,5]]\)
  • \(D(z) = \{2,...,6\}\)

What is the domain of \(z\) after a domain-consistent filtering?

Questão 3: 1D Element: Domain Consistency

Assume an Element constraint for \(T[y]=z\), with:

  • \(D(y) = \{0,1,2,3,4\}\)
  • \(T = [5,5,5,10,8]\)
  • \(D(z) = \{5,6,7,8,9,10\}\)

What is the domain of \(z\) after a domain-consistent filtering?

Questão 4: Stable Matching: Modeling

In the stable matching problem, the constraint "the company of the student of company c is c" is modeled with:

Questão 5: Consistency for AllDifferent

Consider the \(\mathit{AllDifferent}(x_1,x_2,x_3,x_4)\) constraint. This constraint is satisfied if, and only if, all the values taken by \(x_1,x_2,x_3,x_4\) are different.

Assume that after the constraint has been propagated, the domains are \(D(x_1)=\{1,3,4\}, D(x_2)=\{1,3\}, D(x_3)=\{1,3\}, D(x_4)=\{1,4,5\}\).

Select all correct statements:

Questão 6: Consistency

A binary constraint \(C(X,Y)\) is represented visually below, with the feasible region as green polygons.

The domains \(D(X)\) and \(D(Y)\) are represented as small green rectangles on the axes (the lower and upper bounds are extended in a red dashed box).

insertion

The image displays the domains after the constraint has been propagated and values of the domains have been removed.

Select all the correct statements given the current represented domains:

Questão 7: General Assertions

Consider a constraint satisfaction problem with three finite-domain integer variables \(X\), \(Y\), and \(Z\) and the constraint \(C(X,Y,Z)\) on \(X\), \(Y\), and \(Z\). Select all the correct statements:

Questão 8: Range consistency

Bound and domain consistencies are not the only forms of consistency. We now define range consistency. A constraint \(C\) is range-consistent if, and only if:

\(\forall 1 \leq i \leq n: \forall v \in D_i: \exists (v_1,\dots,v_{i-1},v_{i+1},\dots,v_n) \in\) \([\min(D_1),\max(D_1)] \times \dots \times [\min(D_{i-1}),\max(D_{i-1})] \times [\min(D_{i+1}),\max(D_{i+1})] \times \dots \times [\min(D_n),\max(D_n)]\) \(: C(v_1,\dots,v_{i-1},v,v_{i+1},\dots,v_n)\)

Select all the correct statements:

Questão 9: Binary Sum

Consider the constraint \(X+Y=0\) with \(D(X)=[100,110]\) and \(D(Y)=[-1000,120] \cap [-105, 1000]\). Assuming a correct filtering algorithm (it does not remove any solutions) for the constraint achieves bound consistency (after its filtering the constraint is bound consistent), what is the domain \(D(X)\) after the filtering?

Write your answer in the format \(\{v_1,v_2,...,v_n\}\) with \(\forall i: v_i < v_{i+1}\). For instance, write \(\{6,10,13\}\) but not \(\{13,6,10\}\).