Improved Limited Discrepancy Search

Abstract

We present an improvement to Harvey and Ginsberg's limited discrepancy search algorithm. Our version eliminates much of the redundancy in the original algorithm, generating each search path from the root to the maximum search depth only once. For a uniform-depth 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. We also show that the overhead of the improved algorithm on a uniform-depth b-ary tree is only a factor of b=(b\\Gamma1) compared to depth-first search. This constant factor is greater on a heavily pruned tree. Finally, we present empirical results showing the utility of limited discrepancy search, as a function of problem difficulty, on the NP-Complete problem of number partitioning. 1 Introduction: Limited Discrepancy Search The best-known tree-search algorithms are breadth-first and depth-first search. Breadth-first search is rarely used in pra...