Computing at Glasgow University
Paper ID: 8876
DCS Tech Report Number: TR-2008-273

LDS : testing the hypothesis
Unsworth,C. Prosser,P.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers : 5
Publisher: Dept of Computing Science, University of Glasgow
Year: 2008

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.

PS/PS.GZ PDF Bibtex entry Endnote XML