Menu
Why is the complexity of Arc-Consistency Algorithm O(cd3)?
265
(Arc Consistency) The pair (X, Y) of constraint variables is arc consistent if for each value there exists a value such that the assignments X = x and Y = y satisfy all binary constraints between X and Y. A CSP is arc consistent if all variable pairs are arc consistent.
The algorithm AC-3 operates on constraints, variables, and the variables' domains (scopes). A variable can take any of several discrete values; the set of values for a particular variable is known as its domain. A constraint is a relation that limits or constrains the values a variable may have.
In the A* search algorithm, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that Dijkstra's algorithm requires in solving the shortest path problem (no negative cost edges).
Node consistency requires that every unary constraint on a variable is satisfied by all values in the domain of the variable, and vice versa. This condition can be trivially enforced by reducing the domain of each variable to the values that satisfy all unary constraints on that variable.
I will asume that you are refering to AC-3 consistency algorithm. This algorithm is nicely and simply described here. I will be refering to this decsription of the algorithm.
First, lets calculate the complexity of the method REVISE (method revises one arc between two domains). For each value in one domain, it is examining all the values of the second domain. So the complexity of the REVISE method would be d2 where d is maximum domain size.
Now, how many times, at worst, will be the REVISE called? Initially, there are all the arcs 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. How many times can we do that? Well, we are adding 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 at worst, we are adding every arc back to the queue d times.
REVISE is called at maximum e + ed times where e is number of arcs.
When we put it all together, we find out that the complexity of the whole algorithm is O((e+ed)d2) which is O(ed3).
57
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
