Geek Answers Handbook

Why is the complexity of the Arc-Consistency O (cd ^ 3) algorithm?

Why is the complexity of the Arc-Consistency O (cd 3 ) algorithm ?

+4
source share
1 answer

I will assume that you are referring to the AC-3 consistency algorithm. This algorithm is well and simply described here . I will refer to this decryption algorithm.

First, let's calculate the complexity of the method REVISE(the method revises one arc between two domains). For each value in one domain, it checks all the values ​​of the second domain. Thus, the complexity of the method REVISEwould be d 2 where d is maximum domain size.

, , , REVISE? . , REVISE, . . . ? , , , . , , . d .

REVISE e + ed , e is number of arcs.

, , O ((e + ed) d 2), O (ed 3).

+4

More articles:


All Articles