Conditional Distribution Prediction for IDA*
Algorithms AIMech:ConditionalDistributionPredictionIDAStar DRAFT
Aliases: Conditional Distribution Prediction
A search-effort estimation procedure that predicts the number of expanded nodes in a complete IDA* threshold iteration by recursively propagating conditional heuristic-value frequencies and branching counts while excluding pruned ancestor paths.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 638 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 4, 0, 1 lines. All distinct match contents were inspected. Semantic matching covered 63 AIO and 302 native definitions, with every matched definition read. 9 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. Retain the recursive expanded-node estimator for a complete IDA* threshold iteration. It is distinct from the solution-returning IDA* search, IDA*IM online threshold-control integration, and latent-state tree models with observation emissions. The generic acronym CDP is not adopted as a global alias.
Claims & Grounded Evidence
5 Claims
Scope
#complete-contour-counting
The basic formulation estimates expanded nodes for a complete fixed-threshold IDA* iteration with unit-cost edges and nonnegative discrete heuristic values. A node must satisfy the evaluation threshold and be generated through expanded ancestors. Counting every node whose own depth plus heuristic meets the threshold can overcount when an inconsistent heuristic prunes an ancestor. The estimate is neither a solution-returning search procedure nor the expansion count before an early goal stop.
Mechanism
#conditional-count-recurrence
Starting from the root or a specified initial frontier, the recurrence multiplies eligible parent counts by conditional branching factors and child-heuristic probabilities, discards ineligible child counts at each depth, and sums expanded counts across depths. CDP1 conditions on parent heuristic; richer variants include grandparent heuristic and node type to represent effects such as reverse-operator pruning. Transition probabilities are normalized conditional frequencies, whereas propagated quantities are expected node counts and need not sum to one. Unequal parent degrees require matching the weighting of branching estimates and conditional probabilities.
Limitation
#context-and-exactness-boundary
Accurate pooled conditional tables alone do not guarantee accurate predictions for every start. Exact counting requires a context that preserves the relevant branching and successor-type frequencies, pruning rules and initialization. The source gives failure examples and special sufficient conditions for exactness; enriching context can also increase sampling sparsity. Thus exhaustive parameter estimation does not by itself certify the estimator on heterogeneous search trees.
Mechanism
#shallow-search-and-bpmx
An enhanced variant explicitly searches a shallow region and extrapolates from the reached frontier using the remaining threshold, trading extra work for more start-specific information. The BPMX extension models later-sibling suppression from earlier-child upward heuristic propagation for undirected unit-cost search with one-level propagation. Its power expression for sibling survival needs the corresponding conditional independence and ordering assumptions; correlated siblings require a joint survival calculation. These extensions are not unconditional exactness guarantees.
Limitation
#evaluation-and-boundary-estimates
The finite Rubik’s Cube and sliding-tile studies use particular heuristic contexts, sampling procedures and threshold-specific start sets. More conditioning or a shallow prefix does not improve every reported case. Exact potential-node counts provide an upper bound on actual expansions, but sampled approximations are not certified upper bounds. The independence-based lower estimate is empirical rather than a universal lower bound. Arbitrary edge-cost handling and A* graph-search duplicate effects require additional treatment beyond the basic depth-indexed recurrence.
⚠️ Curated Limitations & Negative Results
- The identity is the CDP count estimator, not IDA* itself, IDA*IM threshold selection, a hidden Markov tree, or wall-clock performance prediction. CDP1 and CDP2 are conditioning variants within this record.
- Complete-iteration counting, root initialization, reverse-operator pruning and the definition of expansion must be fixed. Equation 8 sums from depth zero despite its displayed child-level base case; the printed recurrences are not certified here as executable pseudocode.
- Conditional table construction needs matching population weights, especially with unequal degrees and rare-context enrichment. Sampled transition laws and mean branching need not describe every start or every sibling order.
- BPMX survival powers assume the modeled dependence and generation-order conditions. Noninteger average branching requires an interpretation beyond using it literally as a finite sum limit.
- All 43 pages of the author-hosted journal PDF were visually inspected. Other PDF versions, the 2008 conference full text, author software and benchmark replication were not inspected or executed. Constructed examples test boundaries only.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MarkovChain
Markov Chain
|
related_match | The one-step conditional child-heuristic table acts as a transition law on heuristic contexts; richer parent-history contexts enlarge that state description. This is a curator-inferred component relationship. The complete estimator multiplies by offspring counts and applies threshold pruning, so it is not equivalent to a probability-preserving Markov chain or an asserted subclass of the pinned network class. The mapping does not certify that real search states are Markov under a chosen compressed context. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
zahavi2010cdp
|
Uzi Zahavi, Ariel Felner, Neil Burch, Robert C. Holte
|
primary paper
full_text
|
ID: doi:10.1613/jair.2890
sha256:d66f9db3b41c…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T18:21:22Z
Updated: 2026-10-13T18:21:22Z