<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>8876</REFNUM><AUTHORS><AUTHOR>Unsworth,C.</AUTHOR><AUTHOR>Prosser,P.</AUTHOR></AUTHORS><YEAR>2008</YEAR><TITLE>LDS : testing the hypothesis</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><PAGES>5</PAGES><ISBN>TR-2008-273</ISBN><LABEL>Unsworth:2008:8876</LABEL><ABSTRACT>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.</ABSTRACT></RECORD></RECORDS></XML>