2023年11月25日

算法代写 | CMSI 282 – Classwork 5

本次美国CS代写主要是算法相关的题目

Instructions:

This worksheet gives you some important practice with the fundamentals of CSPS!

 

  • Provide answers to each of the following questions and write your responses in the blanks. If you are expected to show your work in arriving at a particular solution, space will be provided for you.
  • Place the names of your group members below:

Problem 1 – CSP Formalization & Backtracking

Time for another rite of passage in this Tour de Algorithms we call 282: The N-Queens Problem.

The N-Queens Problem is a CSP in which the goal is to place  chess queens on an  chess board such that no queen can capture any other. For those unfamiliar with chess, Queens are the most powerful piece that, on any given turn, can move as many tiles as desired in horizontal, vertical, and diagonal directions. A Queen  is capturable if an attacker can move from its tile to that of  in a single turn.

 

Below, observe (left) a solution to the 4-Queens problem and (right) constraints violated on that same problem (the Queen at  can capture both the one at  and ).

In these problems, we have  Queen variables  to place with the implicit constraint that none may capture one another (too verbose to list explicitly).

 

  • For the purposes of improving the efficiency of backtracking, why would it be wasteful to represent each variable’s state as an tuple rather than simply their  (i.e., as a single integer)?

 

  • Using this representation (i.e., assigning each Queen to a specific row), would constraint propagation preprocessing be effective at pruning any domains? Why or why not?

Suppose we represent the partially specified assignments during backtracking on the N-Queens problem as a tuple of queens in which the tuple index specifies each Queen’s column, and int contents specify each Queen’s Row. For example:  denotes a partial specification in which  (because it’s at the 0th index, and therefore the Queen in the 0th column, and the value there is a 2), , and  have yet to be assigned.

 

Now during backtracking, suppose we apply forward checking to remove any inconsistent values from the domains of adjacent (in the constraint graph), unassigned variables based on the assignments made to variables thus far. This means that an assignment of , denoted by the partial assignment , would have the following domain restrictions by forward checking (with the constraint graph on the left and reductions in red on the right):

 

 

  • Draw the backtracking recursion tree with forward checking during backtracking that would solve the 4-Queens problem using the above partial-assignment-notation.

 

Problem 2 – Constraint Propagation

Since it’s relevant to your upcoming assignment, let’s talk about a nice numerical example; we’ll do something similar with Dates in HW 5, but for now, let’s just stick with numbers.

  • Variables:
  • Domains:
  • Constraints: