[Part1 Theory] TinyCSP

Lim denne kommandoen inn i din terminal:

Passord for å koble til er

Vennligst svar på alle spørsmål. Intern feil {} har ikke gyldig filetternavn. {} veier for mye.

Spørsmål 1: N-Queens model

For solving the N-Queens problem, which decision model would you recommend?

An array of bitsets of size N.

A decision vector of integers of size N.

A set of 2D coordinates where each queen is positioned.

A NxN boolean decision matrix.

Spørsmål 2: CP - complete approach

Constraint Programming is a complete approach, it means that:

It has the potential to discover all the feasible solutions to a combinatorial problem or to prove that no solution exists

It can solve efficiently NP-complete problems.

It can model any type of problems with a rich modeling language.

It can be extended by adding new functionality such as new constraints to make it more complete for the users.

Spørsmål 3: CP - declarative

Constraint Programming is declarative, it means that:

The user expresses the properties (constraints) that need to be satisfied using an API or dedicated domain specific language.

The user is not limited to linear constraints or closes as it is the case for linear programming or SAT.

The user has to implement all the steps of how to find a solution in his favorite programming language.

The user declares and describes loudly the problem he wants to solve using a microphone.

Spørsmål 4: TinyCSP - Fix point

In TinyCSP.java, the fix-point computation:

Executes the propagate method of all the constraints in each round, even if the domains of the variables in the scope of the constraints were not modified between successive executions.

Is randomized, choosing randomly one constraint to propagate and stopping whenever the chosen constraint declares it didn’t remove any value.

Uses a propagation Queue that only contains the constraints involving a variable with a recently modified domain.

Executes all the propagate method of all the constraints exactly once.

Spørsmål 5: TinyCSP - domain implementation

In TinyCSP, the implementation of the domains uses a

A list of integer data-structure.

HashSet data structure.

TreeSet data structure.

BitSet data structure.

Spørsmål 6: TinyCSP - Backtracking

In TinyCSP, the domains are restored on backtracking using:

A clone mechanism, making a copy of only of the domain of the variable chosen for branching and restoring the domain of that specific variable on backtrack.

The set of removed values is stored at each node and reinserted on backtrack to that node.

A clone mechanism, making a copy of all the domains before modification by the branching and restoring it on backtrack.

There is no need to restore domains on backtrack, the call stack of the DFS recursion will deal with it automatically.

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

Informasjon

Logg inn