Back

13_Heuristic_Functions

Loading views...
← PreviousNext →

Heuristic Functions

What is a Heuristic Function?

A heuristic function h(n) estimates the cost from node n to the nearest goal. It provides "informed" guidance to search algorithms.

Key Characteristics:

  • Domain-specific: Tailored to specific problems
  • Estimation: Not exact, but hopefully close
  • Non-negative: h(n) ≥ 0
  • Goal state: h(goal) = 0

Role of Heuristics

Without Heuristic (Uninformed Search):

  • Blind exploration
  • Equal treatment of all nodes
  • Examples: BFS, DFS, UCS

With Heuristic (Informed Search):

  • Guided exploration toward goal
  • Prioritize promising nodes
  • Examples: Greedy Best-First, A*
  • Result: Often dramatically faster!

Properties of Heuristic Functions

1. Admissibility

Definition:

A heuristic h(n) is admissible if it never overestimates the actual cost to reach the goal.

Formal: h(n) ≤ h*(n)

Where h*(n) is the true optimal cost from n to goal.

Why Important:

  • Guarantees optimality in A* search
  • Ensures we don't prematurely reject optimal paths
  • Foundation for correctness proofs

Examples:

8-Puzzle Heuristics:

h₁(n) = Number of misplaced tiles

  • Admissible ✓
  • Reason: Each tile must move at least once to reach correct position
  • Never overestimates

h₂(n) = Manhattan distance

  • Admissible ✓
  • Sum of horizontal + vertical distances for each tile
  • Reason: Each move reduces Manhattan distance by at most 1

h₃(n) = Tiles out of place × 10

  • NOT admissible ✗
  • Overestimates actual cost

Route Finding:

Straight-line distance

  • Admissible ✓
  • Direct path is always shortest
  • Actual road distance ≥ straight-line distance

Checking Admissibility:

Ask: "Can the actual cost from n to goal be less than h(n)?"

  • If yes → NOT admissible
  • If no → Admissible

2. Consistency (Monotonicity)

Definition:

A heuristic h(n) is consistent (or monotonic) if for every node n and every successor n' generated by action a:

h(n) ≤ c(n, a, n') + h(n')

Where c(n, a, n') is the cost of action a from n to n'.

Triangle Inequality:

Similar to triangle inequality in geometry:

    n ---c(n,a,n')---> n'
    |                  |
 h(n)|                 |h(n')
    |                  |
    v                  v
  goal <----h*(n')---- goal

h(n) ≤ c(n, a, n') + h(n')

Why Important:

  • Consistency implies admissibility
  • Ensures f(n) values never decrease along path
  • Allows efficient implementation (no reopening needed)
  • Stronger property than admissibility

Relationship:

  • Consistent → Admissible ✓
  • Admissible → Consistent ✗ (not always)

Examples:

Manhattan Distance (8-Puzzle):

  • Each move changes position by distance 1
  • Manhattan distance changes by at most 1
  • Therefore: h(n) ≤ 1 + h(n')
  • Consistent ✓

Straight-line Distance (Route Finding):

  • Direct distance never decreases more than actual travel
  • Forms valid triangle
  • Consistent ✓

Comparing Heuristics

Dominance

Definition:

Heuristic h₂ dominates h₁ if:

h₂(n) ≥ h₁(n) for all nodes n

and both are admissible

Why It Matters:

  • Dominating heuristic is always better
  • Expands fewer nodes
  • Finds solution faster
  • Never loses optimality (if both admissible)

Example (8-Puzzle):

  • h₁(n) = misplaced tiles
  • h₂(n) = Manhattan distance
  • For any state: h₂(n) ≥ h₁(n)
  • h₂ dominates h₁

Result: A with h₂ expands fewer nodes than A with h₁

Designing Good Heuristics

Relaxed Problems

Strategy:

Remove constraints from original problem to create easier version. Solution cost to relaxed problem = heuristic value.

8-Puzzle Example:

Original: Tile moves into adjacent empty space

Relaxed 1: Tile can move to any adjacent square

→ Heuristic: Manhattan distance

Relaxed 2: Tile can move to any square

→ Heuristic: Misplaced tiles count

Advantages:

  • Automatically admissible
  • Often easy to compute
  • Conceptually clear

Pattern Databases

Idea:

Pre-compute exact solution costs for subproblems, use as heuristic.

Example (8-Puzzle):

  • Consider only tiles 1, 2, 3, 4
  • Ignore other tiles
  • Pre-compute costs for all configurations
  • Store in database
  • Lookup during search

Advantages:

  • Very accurate heuristics
  • Can combine multiple patterns

Disadvantages:

  • Memory intensive
  • Pre-computation time

Combining Heuristics

If you have multiple admissible heuristics h₁, h₂, ..., hₘ:

h(n) = max(h₁(n), h₂(n), ..., hₘ(n))

Result: Still admissible and dominates all component heuristics!

Common Heuristics by Problem

8-Puzzle / 15-Puzzle:

  1. Misplaced Tiles: Count tiles not in goal position
  2. Manhattan Distance: Sum of distances from goal
  3. Linear Conflict: Manhattan + conflicts in rows/cols
  4. Pattern Databases: Pre-computed subproblem costs

Route Finding:

  1. Straight-line Distance: Euclidean distance to goal
  2. Minimum Spanning Tree: Lower bound on remaining cost

Traveling Salesperson:

  1. MST of Unvisited Cities
  2. Minimum Edge Costs

Heuristic Quality Metrics

1. Effective Branching Factor (b*)

Measure of heuristic efficiency:

  • N = total nodes generated
  • d = solution depth
  • b satisfies: N = 1 + b + (b)² + ... + (b)^d

Interpretation:

  • b* close to 1: Excellent heuristic
  • b* = b (actual branching): Poor heuristic (no better than uninformed)

2. Nodes Expanded

Fewer nodes = better heuristic

3. Computation Time

Fast computation preferred, even if less accurate

Key Principles

✅ Admissibility: Never overestimate → Ensures optimality

✅ Consistency: Satisfies triangle inequality → Efficient implementation

✅ Dominance: Higher values better (if admissible)

✅ Accuracy: Closer to h* = fewer nodes expanded

✅ Efficiency: Fast to compute vs. accuracy trade-off

Summary Table

Property Definition Importance
Admissible h(n) ≤ h*(n) Guarantees optimality
Consistent h(n) ≤ c(n,a,n') + h(n') Efficiency + Admissibility
Dominance h₂(n) ≥ h₁(n) ∀n Better search performance
← PreviousNext →