Home / Curated / Algorithms / Limited discrepancy search

Limited discrepancy search

Algorithms AIMech:LimitedDiscrepancySearch DRAFT

Aliases: LDS

A backtracking tree-search strategy that repeatedly explores paths under an increasing upper limit on deviations from a successor-ordering heuristic; in the original binary formulation, taking the nonpreferred child consumes one discrepancy.

Identity Notes & Concept Scope The original LDS searches paths with at most k discrepancies in each pass. It differs from Korf’s improved LDS, which avoids revisiting leaves at the supplied maximum depth by allocating an exact discrepancy count there, and from depth-bounded discrepancy search, which bounds where deviations may occur. The original 1995 Figure 1 explores the nonpreferred child first when discrepancy budget remains; Korf’s 1996 presentation of original LDS uses the opposite within-pass order. The names do not establish identical visit sequences. No normalized identity match was found across the 442 AIO and 141 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads and incidental substrings such as builds in records, source text and dependencies, not existing concept records.

Claims & Grounded Evidence

3 Claims

Mechanism #search-procedure

Run a depth-first probe with budget k, starting with k=0 and increasing through a sufficient maximum depth for a finite binary tree. When the budget is zero, follow the heuristic-preferred child. With positive budget, the original Figure 1 first probes the nonpreferred child with k−1 and then the preferred child with k. Return when a goal is found. Each pass permits at most k deviations, so earlier paths may be revisited in later passes.

supports Source: Limited Discrepancy Search · Locator: Section 3 and Figure 1, printed p. 608 / PDF p. 2; Section 5.5, printed p. 611 / PDF p. 5

Scope #original-versus-improved

Korf distinguishes original at-most-k passes from an exact-count-at-maximum-depth modification, and presents a left-child-first original probe. This differs from the right-child-first positive-budget probe printed in the 1995 paper; the two presentations share a budget principle, not necessarily a visit order.

supports Source: Improved Limited Discrepancy Search · Locator: Printed pp. 286–287 / PDF pp. 1–2; Figures 2–3
supports Source: Limited Discrepancy Search · Locator: Figure 1, printed p. 608 / PDF p. 2

Limitation #problem-dependence

Discrepancy search depends on the successor heuristic and search-tree structure. The 1996 study includes negative results against DFS, so the original method is not characterized by universal runtime superiority.

supports Source: Improved Limited Discrepancy Search · Locator: A Simpler Algorithm and Negative Result and Conclusions, printed pp. 290–291 / PDF pp. 5–6

⚠️ Curated Limitations & Negative Results

Completeness applies to exhaustive passes on a finite tree with a sufficient discrepancy/depth limit and adequate resources. A fixed early-pass cutoff is not a decision procedure for unsolvability.
The first goal found is not generally a minimum-cost or shortest-path goal. Successor preference is a search-order heuristic, not an admissible cost bound.
The curated original mechanism is binary. Counting any alternate child as one discrepancy and assigning rank-based discrepancy costs are distinct multiway extensions requiring an explicit policy.
Repeated at-most-k passes revisit paths. The subsequent ILDS paper qualifies the original redundancy argument and supplies cases where discrepancy search has no advantage over ordinary DFS.
The original paper references an LDS-BBS appendix that is not present in the inspected seven-page download. The bounded-backtracking hybrid is not asserted as part of this record.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No suitable AIO counterpart for this graph/state-space search procedure was identified in the inspected snapshot. Using graphs, evaluation functions or a search subroutine in an AI system does not equate the algorithm with a learned model, a learning task or a mathematical function.

Search Scope: All 442 pinned AIO labels and scoped synonyms and 141 preceding native identities were compared. Both updated checkouts were searched including hidden and ignored files. Exact CLASS nodes and edges for GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask, MathematicalFunction and ReinforcementLearning were inspected, alongside semantic search for search, planning, heuristic, path, traversal, symbolic, reasoning and graph terminology.

Examined AIO Candidate	Rejection Reason
`AIO:GraphLanguageModel`	A language model operating on structured graph representations is not a graph traversal or shortest-path algorithm.
`AIO:ReasoningLLM`	Language-task deductive inference does not denote general state-space search.
`AIO:NeuroSymbolicLLM`	A language-model architecture combining neural and symbolic components is not the search procedure itself.
`AIO:MachineLearningTask`	Building methods that learn from data is not the identity of an algorithm traversing a specified graph.
`AIO:MathematicalFunction`	The search procedure is distinct from the mathematical functions it may evaluate.
`AIO:ReinforcementLearning`	A learning task balancing exploration and exploitation is distinct from deterministic graph/state-space traversal.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Limited Discrepancy Search William D. Harvey, Matthew L. Ginsberg	primary paper full_text	sha256:aa484ed1115a…
`original-versus-improved`	Improved Limited Discrepancy Search Richard E. Korf	primary paper full_text	sha256:55b3305027e7…
`problem-dependence`	Improved Limited Discrepancy Search Richard E. Korf	primary paper full_text	sha256:55b3305027e7…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T06:26:52Z

Updated: 2026-10-11T06:29:45Z

Source File: data/curated/LimitedDiscrepancySearch.yaml