Improved Limited Discrepancy Search

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Search Control

We present an improvement to Harvey and Ginsberg’s limited discrepancy search algorithm, which eliminates much of the redundancy in the original, by generating each path from the root to the maximum search depth only once. For a complete binary tree of depth d, this reduces the asymptotic complexity from O((d+2/2)(2^d)) to O(2^d). The savings is much less in a partial tree search, or in a heavily pruned tree. The overhead of the improved algorithm on a complete b-ary tree is only a factor of b/(b - 1) compared to depth-first search. While this constant factor is greater on a heavily pruned tree, this improvement makes limited discrepancy search a viable alternative to depth-first search, whenever the entire tree may not be searched. Finally, we present both positive and negative empirical results on the utility of limited discrepancy search, for the problem of number partitioning.