Reduced branching-factor algorithms for constraint satisfaction problems Academic Article uri icon

abstract

  • This paper investigates connections between the worst-case complexity of CSP search algorithms and their practical efficiency. We prove that a well-known search algorithm FC- CBJ together with the Fail-First ordering heuristic has a worst-case complexity of O∗((d− 1) n) rather than O∗(dn), where d and n are the maximal domain size and the number of variables of the given CSP, respectively. This result shows that heuristic methods designed only for practical purposes can be useful for reducing worst-case complexity. To show that low-complexity CSP algorithms can be useful in practice, we take an existing “purely- theoretical” approach that solves CSP in O∗([d/2] n) and, based on this approach, design two algorithms 2FC and 2MAC that are an order of magnitude better than their prototypes, FC and MAC, respectively, on a number of benchmark domains.¿ From this result we infer …

publication date

  • January 1, 2005