Improved limited discrepancy search
Algorithms AIMech:ImprovedLimitedDiscrepancySearch DRAFT
Aliases: ILDS
Korf’s discrepancy-search variant that uses a supplied maximum search depth and remaining discrepancy count to generate each path to that depth in the pass corresponding to its exact number of nonpreferred choices, avoiding the original method’s repeated maximum-depth paths.
Identity Notes & Concept Scope
ILDS is the 1996 improvement to LDS, not a generic label for any later discrepancy-search modification. Its exact-count guarantee concerns leaves at the specified maximum depth; shallower leaves and internal nodes can still be revisited. The supplied depth bound differs from a bound on the depths at which discrepancies are allowed. 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
2 Claims
Mechanism
#search-procedure
For each budget k from zero through the supplied maximum depth, recursively track remaining depth D and discrepancies k. In the binary Figure 3, visit the preferred child when D>k, leaving k unchanged; visit the nonpreferred child when k>0, reducing k by one. Both moves reduce D by one. When D=k, only nonpreferred choices remain possible along a path that reaches the depth bound. The printed procedure visits the preferred branch before the nonpreferred branch when both are allowed.
Limitation
#repeated-prefixes
Maximum-depth paths are generated once across discrepancy passes, but shorter leaves and internal nodes can recur. The paper’s uniform-tree overhead analysis and its negative number-partitioning results are distinct from a universal performance guarantee.
⚠️ Curated Limitations & Negative Results
- A valid upper bound on maximum depth is an input. A loose bound or pruning that creates shallower leaves reduces the benefit because those leaves may be visited on several passes.
- Visiting each maximum-depth leaf once does not mean visiting every internal node once; repeated prefixes remain.
- The complete uniform-tree expansion analysis is conditional on that tree shape. It does not establish an unconditional wall-clock advantage on pruned trees or early-terminated searches.
- The procedure’s discrepancy priority does not guarantee that the first goal is shortest or globally minimum-cost. No universal superiority over DFS is asserted.
- The 1996 prose gives a depth-three original-LDS path count inconsistent with its own displayed counting formula and the original paper’s trace. No literal 19-path count is adopted.
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
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Richard E. Korf
|
primary paper
full_text
|
sha256:55b3305027e7…
|
repeated-prefixes
|
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:26:52Z
Source File:
data/curated/ImprovedLimitedDiscrepancySearch.yaml