Iterative linear best-first search

⚠️ Curated Limitations & Negative Results

• The high-level Algorithm 1 line 8 reverses the sibling/ancestor description of the branch to collapse relative to the Case 2 prose and low-level Algorithm 2. The mechanism above follows the latter two explicitly; the literal high-level discrepancy is retained and no repaired implementation is certified.
• The printed low-level outline leaves root/NULL-parent conventions, empty-child minima and complete infinity/exhausted-frontier handling incompletely specified. The compared RBFS listing explicitly includes an empty-successor return and a finite-value guard. ILBFS goal testing precedes collapse, and the outline is not a complete production interface for every dead end or unsolvable input.
• The path-and-children description does not provide a complete general graph duplicate-state, cycle or reopening policy. Generic best-first discussion assumes reopening for inconsistent heuristics, but that is not a demonstrated ILBFS graph implementation. No completeness, optimality or termination guarantee is extended here to arbitrary infinite spaces, zero-cost cycles or unspecified goal/cost assumptions.
• A generic collapse stores only a frontier summary and is described as lossy compression. Its monotone bounded-search restoration discussion must not be promoted to an exact inverse for arbitrary collapsed subtrees. The ILBFS-specific F>f regeneration argument depends on its own branch-switch and depth-first tie conventions; changing those conventions requires a new argument.
• O(b*d) is a retained-node model with bounded branching, attained depth and per-node data, not a fixed maximum-node budget or a total-byte guarantee. State encodings, heuristic tables, explicit queues, transient allocations and any duplicate/transposition tables require separate space accounting; SMA* memory-budget properties do not follow from shared backup/deletion ideas.
• The same-step comparison is to the full RBFS formulation reproduced in this source under compatible selection and tie conventions. It is not a global alias claim for every RBFS version or for SRBFS or Russell’s Iterative Expansion. In particular, unconditional first-visit inheritance and conditional inheritance can differ with nonmonotone evaluations, and the cited 1993 RBFS journal version remains a retained version question.
• The later 2024 text describes its depth-first tie rule as taking the node inserted first, while the inspected pinned comparator favors greater creation times for equal F and its child timestamps increase. This is a prose/code distinction at commit e0e5ec40751ab9108d9b0a36bbc81ac843f5ca8c; a complete trace-equivalence result or proof of cycle freedom is not supplied by that static comparison.
• The 2024 heap discussion conflates observing a minimum with extracting it and restoring heap order. Its arbitrary-node deletion procedures include linear search/removal work; for positive k their stated O(k*n+n) and O(k*(n+log n)) totals are both O(k*n) as n grows. No general asymptotic or measured runtime superiority is inferred from that discussion.
• The 2024 versions report different experiment designs and one v1 caption conflicts with its memory axis. The v2 table does not show a slower ILBFS time in every row. The pinned notebook source, imports and start-inclusive path-length bins do not establish reproduction of the v2 move-length experiment, and traced Python allocations are not total process memory. No code, notebook or benchmark was run for this draft.
• The 2015 work already reports an implementation, so the 2024 first-implementation assertion is retained as a source conflict rather than a historical fact. Pedagogical ease is not an evaluated learning outcome. The later epsilon paragraph’s RBFS_CR label does not establish equivalence to the distinct 2015 histogram method; source versions, author-name/publication metadata and all bibliography/retrieval questions remain explicit research context.