Paper ID: 8876
DCS Tech Report Number: TR-2008-273
LDS : testing the hypothesis
Tech Report (internal)
DCS Technical Report Series
Page Numbers : 5
Publisher: Dept of Computing Science, University of Glasgow
Limited Discrepancy Search (LDS, due to Harvey and Ginsberg) is based on the premise that heuristic decisions
are relatively inaccurate near the top of search, and that early mistakes are expensive to correct.
The LDS process addresses this by first probing with the heuristic. If this fails LDS then starts again,
allowing the search process to go against the heuristic once, i.e. take one discrepancy in all
possible ways. If this fails then search starts again, but this time two discrepancies are allowed,
and so on to a maximum number. Korf improved LDS (to give ILDS) by eliminating the
re-exploration of leaf nodes. However, in ILDS discrepancies are delayed, counter to the intuition behind LDS.
Furthermore LDS and ILDS are presented only for problems with binary domains. We present a new
version of LDS, one that takes discrepancies in the order prescribed by Harvey and Ginsberg, incorporates
Korf's redundancy elimination, whilst dealing with domains of arbitrary size. We then put Harvey and
Ginsberg's premise to the test, i.e. are heuristics more accurate at the top of search and
is it better to take discrepancies late or take them early? Our experiments suggest that
discrepancy order makes little difference, casting doubt on the intuition behind LDS.