Arc consistency: parallelism and domain dependence

摘要

This paper discusses how better arc consistency algorithms for constraint satisfaction can be developed by exploiting parallelism and domain-specific problem characteristics. A massively parallel algorithm for arc consistency is given, expressed as a digital circuit. For a constraint satisfaction problem with n variables and a labels, this algorithm has a worst-case time complexity of O(na), significantly better than that of the optimal uniprocessor algorithm. An algorithm of intermediate parallelism suitable for implementation on a SIMD machine is also given. Analyses and implementation experiments are shown for both algorithms.