ark*_*ark 6 algorithm complexity-theory artificial-intelligence constraint-satisfaction
为什么Arc-Consistency Algorithm O(cd 3)的复杂性？
小智 9
我将假设您正在参考AC-3一致性算法.这个算法在这里很好地简单描述.我将参考这个算法的解释.
首先,让我们计算方法的复杂性REVISE(方法修改两个域之间的一个弧).对于一个域中的每个值,它正在检查第二个域的所有值.因此,在复杂REVISE的方法将是d 2哪里d is maximum domain size.
现在,最坏的情况下会被REVISE召唤多少次？最初,队列中存在所有弧.每次REVISE调用时,都会从队列中删除一个弧.这将是该方法的调用.但我们也将弧线添加回队列.我们能做多少次？好吧,只有当弧从指向的域中删除一个值时,我们才会将弧添加回队列.一个弧指向一个域,因此我们只能将其添加为该域中值的数量.所以在最坏的情况下,我们将每个弧添加回队列d次.
REVISE在最大e + ed次调用e is number of arcs.
当我们把它们放在一起时,我们发现整个算法的复杂性是O((e + ed)d 2),即O(ed 3).