Saving Support-Checks Does Not Always Save Time

摘要

Arc-consistency algorithms are the workhorse of backtrackers that maintain arc-consistency (MAC). This paper will provide experimental evidence that, despite common belief to the contrary, it is not always necessary for a good arc-consistency algorithm to have an optimal worst-case time-complexity. Sacrificing this optimality allows MAC solvers that (1) do not need additional data structures during search, (2) have an excellent average time-complexity, and (3) have a space-complexity that improves significantly on that of MAC solvers that have optimal arc-consistency components. Results will be presented from an experimental comparison between MAC-2001, MAC-3 d and related algorithms. MAC-2001 has an arc-consistency component with an optimal worst-case time-complexity, whereas MAC-3 d does not. MAC-2001 requires additional data structures during search, whereas MAC-3 d does not. MAC-3 d has a O(e+nd) of space-complexity, where n is the number of variables, d the maximum domain size, and e the number of constraints. We shall demonstrate that MAC-2001's space-complexity is O(edmin(n,d)). Our experimental results indicate that MAC-2001 was slower than MAC-3 d for easy and hard random problems. For real-world problems things were not as clear.