Question regarding CONSTRAINST SATISFACTION PROBLEM. Look at the 2 algorithms be

Question

Question regarding CONSTRAINST SATISFACTION PROBLEM.

Look at the 2 algorithms below (Revise and ac-3) and derive each of their time complexity . Show steps and explanations.

// make (x,y) arc consistent by removing // values without support. return true if some value is removed and false o/w. Algorithm: REVISE (x, y)) { delete = False; for each value a in the doma in of x if no b in the domain of ysuch that (a,b) satifies Cxy remove a from the domain of x; delete- True; ) return (delete); Main algorithm: // Queue Q: arcs of form (i,j) algorithm AC-3(V, D, C) { Q { all arcs (i,j) in C); while Q not empty { select and del an arc (i,j) from Q: if REVISE ( (i,j))

Explanation / Answer

The complexity of functon REVISE(x, y) is O(M*N) where M and N are the number of elements in the domain of X and Y, respectively.

Explanation: In order to remove 'a' from the domain of x, we need to find a pair (a, b) satisfying cxy. In order to do so, we would need to iterate through all the elements, say 'a' from the domain for x. For each element 'a', we need to again iterate through the domain of Y to find b, such that (a, b) satisfying cxy

Hence, the number of steps = M*N

Therefore, time complexity = O(M*N)

The complexity of main method is O(K*M*N) where K is the number of arcs in C.

In main method, we first push all the arcs (x, y) into a queue and run the algorithm REVISE((i, j)) for each arc in the queue.

Therefore, time complexity of this method = O(K*M*N)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.