A generic arc-consistency algorithm and its specializations

摘要

Consistency techniques have been studied extensively in the past as a way of tackling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been proposed, originating from Waltz's filtering algorithm [27] and culminating in the optimal algorithm AC-4 of Mohr and Henderson [16]. AC-4 runs in O(ed2) in the worst case, where e is the number of arcs (or constraints) and d is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints.