Research map / Learning theory and algorithms / Combinatorial and search optimization
Problem Difficulty and the Phase Transition in Heuristic Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use stronger heuristic h4 instead of h1 | GBFS on random graph instances · Abstract model, gamma~1.65 crossover | median nodes expanded: h1 expands about 2x h4 | Helped |
| use stronger heuristic h4 instead of h1 | GBFS on random graph instances · Abstract model, gamma~4.75 | median nodes expanded: approximately 100 times fewer nodes | Helped |
| use stronger heuristic h4 instead of h1 | GBFS on random graph instances · Abstract model, gamma~20 | median nodes expanded: approximately 900 times fewer nodes | Helped |
| use informed heuristic h4 instead of uninformed h0 | GBFS · Abstract model, less constrained region | median nodes expanded: no reduction for h0 vs h4 expands ~2,500x fewer at gamma 20 | Helped |
| use h'gap_8 instead of h'gap_2 | GBFS · 8-Pancake, gamma ~1.55 | median nodes expanded: 1,715 -> 981 | Helped |
| use h'gap_8 instead of h'gap_2 | GBFS · 8-Pancake, gamma ~3.5 | median nodes expanded: 380 -> 33 | Helped |
| use h'gap_8 instead of h'gap_2 | GBFS · 8-Pancake, gamma ~60 | median nodes expanded: 344 -> 5 | Helped |
| use h'gap_4 instead of h'gap_2 | GBFS · 8-Pancake, gamma ~1.55 | median nodes expanded: 1,715 -> 1,921 | Hurt |
Closest papers by meaning
- On the Completeness of Best-First Search Variants That Use Random Exploration (AAAI 2016 · similarity 0.86)
- Local Search for Hard SAT Formulas: The Strength of the Polynomial Law (AAAI 2016 · similarity 0.86)
- A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search (AAAI 2020 · similarity 0.86)
- Novelty vs. Potential Heuristics: A Comparison of Hardness Measures for Satisficing Planning (AAAI 2024 · similarity 0.84)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.84)
- Rectangle Search: An Anytime Beam Search (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.