Smoothed Analysis of Inconsistent A*
cs.DS · cs.AI
Quick verdict
First smoothed analysis of inconsistent A*: O(n²mκ) expected time under edge-weight noise; core proof sound, Dijkstra extension sketched, experiments small.
Summary
This paper gives the first smoothed analysis of A* search with inconsistent heuristics, addressing the gap between Martelli's Ω(2^n) worst-case reopening bound and the empirical efficiency of inconsistent heuristics in practice. Edge weights of worst-case graphs are independently perturbed with density bounded by κ on [0,1], while the heuristic h is adversarial but fixed before sampling. The main theorem bounds expected iterations by O(n²mκ). The proof links inconsistent A* to Pareto optimality via a bottleneck comparison over path prefixes (Definition 4), proves intermediate paths form a Pareto frontier (Lemmas 5-6), bounds indirect updates by (n−1) per direct update (Lemma 3), and adapts the Beier-Vöcking winner-gap technique to charge each direct update to an event of probability O(εκ) (Lemmas 7-8). Theorem 9 extends the bound to Dijkstra on negative-weight graphs without negative cycles, though its proof is only sketched. Experiments on Martelli's worst-case family (n=15-25, 100 trials per κ) show iteration counts falling from about 2^n as perturbation grows. Limitations: the heuristic cannot adapt to realized noise, the bound sits a factor m above the conjectured O(n²κ), experiments cover only the constructed adversarial family, and no code is reported available.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 2
● low 3
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- On κ-smoothed instances (edge weights with density bounded by κ), inconsistent A* completes in O(n²mκ) expected iterations for arbitrary heuristics, even inadmissible ones fixed before sampling (Theorem 2).
- Every indirect update is causally rooted in a unique direct update, with at most n-1 indirect updates per direct update (Lemma 3).
- Intermediate paths of inconsistent A* form a Pareto frontier under the (path length, bottleneck f-value) criteria (Lemmas 5-6), which enables a Beier-Vöcking winner-gap charging argument (Lemmas 7-8).
- The same O(n²mκ) smoothed bound holds for Dijkstra's algorithm on negative-weight graphs without negative cycles (Theorem 9).
- Martelli's exponential worst-case instances are empirically fragile: small random perturbations collapse iteration counts from about 2^n to much smaller values (Section 5, Figure 4, n=15-25).
Strengths
First polynomial smoothed bound for a long-open problem
Theorem 2's O(n²mκ) expected-iteration bound is the first smoothed-complexity result for A* under inconsistent heuristics, addressing exactly the theory-practice gap Felner et al. [1] articulated; it holds for arbitrary (even inadmissible) heuristics fixed before sampling.
Elegant, well-executed reduction to Pareto-frontier analysis
Definition 4 (bottleneck comparison over the longest non-common prefix) plus Lemma 6 maps intermediate paths onto a Pareto frontier, cleanly porting the Beier-Vöcking winner-gap machinery (Lemmas 7-8); the charging in Lemma 7 is verified sound since simple paths to v ending with edge e make G_{v,e,k} = deterministic + w_e, giving the εκ probability bound in Lemma 8.
Useful generality of the result
Fully specified, re-doable experiment on the canonical worst case
Weaknesses
Theorem 9 (negative-weight Dijkstra) has no proof
Experiments restricted to the constructed adversarial family
Heuristic cannot depend on realized noise
Bound loose and constants astronomically small
Lemma 3's proof is informal
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This paper claims the first smoothed analysis of A* search with inconsistent heuristics, targeting the long-standing gap between Martelli's Ω(2^n) worst-case reopening bound [3] and the practical efficiency argued by Felner et al. [1]. The model (Section 2) independently perturbs every edge weight of a worst-case graph with probability density bounded by κ on [0,1]; the heuristic h may be adversarial and even inadmissible, but must be fixed before the noise is sampled. The headline result (Theorem 2) bounds expected iterations by O(n²mκ); Theorem 9 extends the bound to Dijkstra on negative-weight graphs without negative cycles; Section 5 numerically demonstrates fragility of Martelli's worst-case family.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does 'smoothed analysis of A*' mean in this paper?
Smoothed analysis measures an algorithm's performance on worst-case inputs after small random noise is added. Here, each edge weight of a worst-case search graph is independently redrawn from a distribution whose probability density is bounded by κ, while the (possibly inconsistent, even inadmissible) heuristic is chosen adversarially before the noise is sampled. The paper proves A* then finishes in O(n²mκ) expected iterations instead of the Ω(2^n) worst case, explaining why exponential blow-up is rarely seen in practice.
Why can inconsistent heuristics make A* exponentially slow?
With an inconsistent heuristic, A* may later discover a cheaper path to a node it has already expanded and must reopen it. Martelli (1977) constructed instances where such reopenings cascade, forcing on the order of 2^n node expansions. This paper shows those pathological instances are mathematically fragile: slight independent random perturbation of edge weights makes the expected running time polynomial.
Does the result apply to Dijkstra's algorithm with negative edge weights?
Yes. Via the standard potential transformation w'(u,v)=w(u,v)+h(v)-h(u), inconsistent A* is equivalent to Dijkstra's algorithm on negative-weight graphs without negative cycles. Theorem 9 states the same O(n²mκ) expected iteration bound for that setting, although the paper only sketches the proof rather than giving it in full.
Is code or data available for the experiments?
The extracted text contains no code or data availability statement. However, Section 5 provides complete formulas for Martelli's worst-case family (edge weights and heuristic values), Algorithm 1 pseudocode with reopening, and the perturbation protocol (uniform noise on [-γ,γ] clipped at zero, 100 runs per noise level, n=15, 20, 25), so the experiments are straightforwardly reimplementable.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1-4 are not analyzable from the text extraction; Figure 4 experiment values are described only qualitatively (iteration counts vs 1/κ on log-log axes).
- Theorem 9's proof is absent from the paper itself (asserted 'essentially identical' to Theorem 2), so the second contribution could not be verified in detail.
- Referee-level checking of Lemmas 5-8 was done on the extracted text; the extraction appears complete (12 pages) but truncation or an appendix in the PDF cannot be fully ruled out.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.