Neural Sync Active

🎨 Designing Heuristic Functions

Registry Synced

🎨 Designing Heuristic Functions

165 words

1 min read

Reading compass

Now · 1. 🎯 Learning Objectives

🎨 Designing Heuristic Functions

1. 🎯 Learning Objectives

Design heuristics by problem relaxation
Use pattern databases for 8-puzzle/15-puzzle
Explain admissible vs informed trade-off

2. 📖 Core Content

3.1 Relaxation

Remove constraints from problem → easier problem → optimal cost is admissible heuristic. 8-puzzle relaxations:

Relax "slide tile" to "move tile to any adjacent square" → Manhattan
Relax "tile cannot occupy same square" → Hamming
Relax both → 0 (trivial, useless)

3.2 Pattern Databases

Store optimal cost-to-goal for a subset of tiles (pattern). Use as heuristic for full problem. Example: 15-puzzle with 7-tile pattern database: precompute distances for all 7-tile configurations (~16M entries = ~64 MB).

3.3 Heuristic Quality

More informed ≠ better if computation cost outweighs pruning savings
Dominance: h₁ dominates h₂ if h₁(N) ≥ h₂(N) for all N
Effective branching factor: b* = N^{1/d} where N = nodes expanded, d = solution depth Join Discord PreviousBest First SearchNextHeuristic Functions