[Part1 Theory] TinyCSP

עליך להדביק את הפקודה הזאת במסוף שלך:

הסיסמה להתחברות אל

נא לענות על כל השאלות. שגיאה פנימית ל־{} אין סיומת תקפה. {} כבדה מדי.

שאלה 1: N-Queens model

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

A decision vector of integers of size N.

An array of bitsets of size N.

A NxN boolean decision matrix.

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

שאלה 2: CP - complete approach

Constraint Programming is a complete approach, it means that:

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

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

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

It can solve efficiently NP-complete problems.

שאלה 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 has to implement all the steps of how to find a solution in his favorite programming language.

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

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

שאלה 4: TinyCSP - Fix point

In TinyCSP.java, the fix-point computation:

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

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.

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.

שאלה 5: TinyCSP - domain implementation

In TinyCSP, the implementation of the domains uses a

A list of integer data-structure.

HashSet data structure.

BitSet data structure.

TreeSet data structure.

שאלה 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.

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

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

מועד הגשה	אין מועד הגשה
מגבלת הגשות	2 הגשות כל 1 שעות

מידע

כניסה