notes.npwitknpwitk.com ↗

Chapter 4 - Informed Search

Updated 4 Oct 2026

Introduction

  • Uniform-Cost Search explores states in all directions based on distances from start
  • To obtain solutions more quickly, we can use additional information to guide node expansion
  • This leads to informed search algorithms

4.1 Evaluation Function

Definition

  • Evaluation function f(n): estimates the cost when a node n is selected as part of the solution
  • The node with the lowest evaluation value is chosen first
  • Allows selection of nodes more likely to lead to quick solutions

Comparison

  • Uninformed Search: explores without additional guidance
  • Informed Search: uses evaluation function to guide search toward goal

4.2 Heuristic Functions

Definition and Properties

  • Heuristic function h(n): estimates the cost to reach a goal node from node n
  • Problem-specific function with one constraint: if nn is a goal node, then h(n)=0h(n) = 0
  • Takes a node as input but evaluates only the state associated with that node
  • Can be used alone or as part of an evaluation function

4.3 Greedy Best-first Search (GBFS)

Algorithm Overview

  • Chooses to expand the node estimated to be closest to the goal
  • Always selects the node with the smallest h(n)h(n) from the frontier
  • Evaluation function: f(n)=h(n)f(n) = h(n)
  • Expands nodes based on heuristic values without considering cost to reach those nodes

Example: Romania Route-Finding Problem

  • Uses straight-line distance as heuristic function
  • Straight-line distance heuristics (hSLD) for cities:
    • Arad: 366, Bucharest: 0, Craiova: 160, Drobeta: 242
    • Eforie: 161, Fagaras: 176, Giurgiu: 77, Hirsova: 151
    • Iasi: 266, Lugoj: 244, Mehadia: 241, Neamt: 234
    • Oradea: 380, Pitesti: 100, Rm Vilcea: 193, Sibiu: 253
    • Timisoara: 329, Urziceni: 80, Vaslui: 199, Zerind: 374

Search Process

  • Expands states in direction toward goal
  • Visits only 4 states before finding solution in Romania example
  • However: obtained solution is not optimal

Completeness

  • Tree Search: Incomplete - may get stuck in cycles even in finite state spaces
  • Graph Search: Complete in finite state spaces

Optimality

  • Not optimal: does not always return the solution with minimum cost
  • Focuses only on estimated distance to goal, ignoring actual cost to reach current node

Algorithm Overview

  • Minimizes total cost from initial node to goal node
  • Evaluation function: f(n)=g(n)+h(n)f(n) = g(n) + h(n)
    • g(n)g(n): actual cost to reach node nn from initial node
    • h(n)h(n): heuristic function (estimated cheapest cost from nn to goal)
    • f(n)f(n): estimated cost of cheapest solution through nn

Example: Romania Route-Finding Problem

  • Search process showing ff-values:
    • Arad: f=0+366=366f = 0 + 366 = 366
    • Sibiu: f=140+253=393f = 140 + 253 = 393
    • Oradea: f=291+380=671f = 291 + 380 = 671
    • Rm Vilcea: f=220+193=413f = 220 + 193 = 413
    • And so on...

Advantages

  • Focuses on expanding nodes in direction to goal
  • Considers cumulative actual cost when selecting nodes
  • Can obtain optimal solution

Optimality Conditions

  • A* using tree search is optimal if h(n)h(n) is an admissible heuristic
  • Admissible heuristic: never overestimates the cost to reach the goal
  • Formally: ∀n,h(n)≤C∗(n)\forall n, h(n) \leq C^*(n), where C∗(n)C^*(n) is actual optimal cost to reach goal from nn
  • A* using graph search is optimal if h(n)h(n) is a consistent (monotone) heuristic
  • Consistent heuristic: for every node nn and successor pp of nn:
    h(n)≤c(n,p)+h(p)h(n) \leq c(n,p) + h(p)
  • Analogous to triangle inequality in geometry
  • Ensures f(n)f(n) is non-decreasing along any path

Completeness

  • A* with consistent heuristic has these properties:
    • Expands all nodes nn such that f(n)<C∗f(n) < C^*
    • May expand some nodes with f(n)=C∗f(n) = C^*, including goal
    • Does not expand any node with f(n)>C∗f(n) > C^*
  • Complete if there are only finitely many nodes with f(n)≤C∗f(n) \leq C^*

4.5 Admissible Heuristic Design

Requirements

  • Never overestimates cost to reach goal
  • Should be fast and efficient to compute
  • Otherwise, benefits of informed search are diminished

4.5.1 Creating Admissible Heuristics from Relaxed Problems

General Approach

  • Many search problems have constraints
  • Relax some constraints to make problem easier
  • Compute cost of relaxed solution directly
  • This cost ≤\leq cost of original solution
  • Provides realistic estimate of original cost

Example: Romania Route-Finding

  • Original constraint: must follow roads on map
  • Relaxed version: can travel in straight lines
  • Heuristic: straight-line distances between cities
  • Easy to compute and admissible

Example: 8-Puzzle Problem

Original Constraints:

  • Tile can move from A to B if:
    1. A is adjacent to B (horizontally/vertically)
    2. B is blank

Three Relaxed Problems:

Relaxed Problem (a): Remove both constraints

  • Tile can move to any location
  • h1(n)h_1(n): number of misplaced tiles
  • Example: for goal state [123456780]\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 0 \end{bmatrix}, state [724506831]\begin{bmatrix} 7 & 2 & 4 \\ 5 & 0 & 6 \\ 8 & 3 & 1 \end{bmatrix} has h1=6h_1 = 6

Relaxed Problem (b): Remove constraint (2) only

  • Tile can move to adjacent location, ignoring blank
  • h2(n)h_2(n): sum of Manhattan distances from each tile to goal position
  • Manhattan distance = ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|
  • More accurate than h1h_1

Relaxed Problem (c): Remove constraint (1) only

  • Tile can move to blank location, ignoring adjacency
  • h3(n)h_3(n): number of swaps between misplaced tiles and blank
  • Similar to h1h_1 but more complex to compute

Implementation Notes

  • Both GBFS and A* can be implemented by modifying uniform-cost search
  • Use ff-value as priority in min-heap
  • Need to implement problem-specific heuristic function

Key Takeaways

Algorithm Comparison

  • Uniform-Cost Search: explores uniformly, guaranteed optimal
  • Greedy Best-first: fast but not optimal
  • A*: optimal (with admissible/consistent heuristics) and efficient

Heuristic Quality

  • Better heuristics lead to more efficient search
  • h2h_2 (Manhattan distance) typically better than h1h_1 (misplaced tiles)
  • Consistency is stronger condition than admissibility
  • Consistent heuristics are also admissible

Practical Considerations

  • Heuristic computation time vs. search efficiency trade-off
  • Domain knowledge crucial for designing good heuristics
  • Relaxed problems provide systematic way to create admissible heuristics