CS7649-Homework 3 Solved

Problem 1
Prove that the complexity of AC-3 is 𝑂(𝑒𝑘3). You are welcome to look up sources online to help with the proof, but the proof must be detailed and derived using your own words – no copy+pasting! Lec6  

From Lec 6, the basic summary of the Algorithm: 

AC-3 (CSP) 

Input: CSP = 𝑋,𝐷, 𝐶 

Output: CSP’, the largest arc-consistent subset of CSP 

1. FOR every 𝐶ij   𝐶                                                                    # O(e) + ……. 2. 𝑄 ← 𝑄   {<𝑥𝑖, 𝑥𝑗> , <𝑥𝑗, 𝑥𝑖>} 

3.      ENDFOR 

4.      While 𝑄 ≠        # Iterations of while loop determined by # of times line 7 is true (as well as e, k, and n)

5.      Select and delete arc <𝑥𝑖, 𝑥𝑗> from Q 

6.      Revise (𝑥𝑖, 𝑥𝑗)                                                                            # O(k^2) 

7.      IF Revise(𝑥𝑖, 𝑥𝑗) caused a change to 𝐷𝑖                                       #*O(ek) 

8.      𝑄 ← 𝑄   <𝑥𝑘, 𝑥𝑖  |  ≠  ,   ≠   

9.      ENDIF 

10.  ENDWHILE 

 Complexity of AC-3? =   +     2) = O(ek^3) 

Calculate the complexity of the method revise (method revises one arc between two domains).  

For each value in one domain, it is looking at all the values of the 2nd domain. So the complexity of the revise method would be k2 (k is the maximum domain size). 

Worst case scenario, how many times will be the revise be called? At first, all the arcs are in the queue. Every time the revise is called, one arc is removed from the queue. That would be e calls of the method.  

But we are also adding arcs back to the queue. We are adding an arc back to the queue only if a value was deleted from the domain the arc is pointing to. One arc is pointing to one domain, so we can only add it as many times as the number of values in that domain. So worst case, we are adding every arc back to the queue k times. revise is called at maximum e + ek times (e is the number of arcs). 

When we put everything from above, we get complexity of the whole algorithm as O(e+ek*k2) which simplifies to O(ek3). 

Problem 2
For this problem, you will draw block diagrams describing the flow of Backtrack Search with Forward Checking and Dynamic Variable Ordering. An example block diagram for HOTPO is shown below. Please follow the same conventions for your solutions.  


Part A) Draw a block-diagram describing Backtrack Search with Forward Checking and Dynamic Variable Ordering, based upon slide 63 (“Procedure Dynamic-Var_Forward-Checking(x,D,C)”).  

 

Part B) Draw a block-diagram describing Backtrack Search with Forward Checking and Dynamic Variable Ordering, based upon slide 57 (“Procedure Select-Value-FC()”), which is a subroutine for the program you described in Part A.

              

Problem 3
Implement the following algorithms to solve the n-queens problem, which is defined as the problem of placing n queens on a chess board of size n by n such that no queen can “take” another queen (i.e., no two queens should be on the same row, column or diagonal).

•       Standard Search                                                                               function: standard()

•       Backtrack Search                                                                              function: BT()

•       Backtrack Search with Forward Checking (FC)                      function: BT_w_FC()

•       Iterative Repair (Min-Conflict Heuristic)                                  function: iterative_repair()

Generate a plot like the one below by trying n = {1,2,…} for each algorithm until the search method can no longer find a solution within 10 minutes of computation time. Include the plot in your PDF submission.