[Part1 Theory] TinyCSP

Dán dòng lệnh này vào terminal của bạn:

Mật khẩu để kết nối là

Xin hãy trả lời tất cả các câu hỏi. Lỗi nội tại hệ thống {} has not a valid extension. {} is too heavy.

Câu hỏi 1: N-Queens model

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

A NxN boolean decision matrix.

A decision vector of integers of size N.

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

An array of bitsets of size N.

Câu hỏi 2: CP - complete approach

Constraint Programming is a complete approach, it means that:

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

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

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

It can solve efficiently NP-complete problems.

Câu hỏi 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 declares and describes loudly the problem he wants to solve using a microphone.

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.

Câu hỏi 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.

Câu hỏi 5: TinyCSP - domain implementation

In TinyCSP, the implementation of the domains uses a

BitSet data structure.

A list of integer data-structure.

HashSet data structure.

TreeSet data structure.

Câu hỏi 6: TinyCSP - Backtracking

In TinyCSP, the domains are restored on backtracking using:

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

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.

Hạn chót	Không có hạn chót
Giới hạn nộp bài	2 bài nộp mỗi 1 giờ

Thông tin

Đăng nhập