Heuristics and A-Star Search

Tags: #◇Computer Science #◇CSINTSY #◇Heuristics and A-Star Search #◇Problem Solving #◇M2

---

◇Overview

Informed search, unlike uninformed search, exploits partial knowledge about the problem to guide the exploration of the state space. This domain knowledge is often encapsulated in a heuristic function, $h(s)$, which estimates the cost from state $s$ to the goal.

Greedy Best-First Search (GBFS) Expands the node that appears closest to the goal (lowest $h(s)$). Characteristics: Complete if the state space is finite. Not optimal. Devolves to BFS or DFS if $h(s) = 0$.

A Search* Combines Uniform Cost Search and Greedy Best-First Search by considering both the accumulated path cost $g(s)$ and the estimated cost to the goal $h(s)$. Characteristics: Complete for finite spaces. Optimal if the heuristic is admissible. If $h(s) = 0$, A* devolves into UCS.

Admissibility:
A heuristic $h(s)$ is admissible if it never overestimates the true cost to reach the goal: $h(s) \leq h^*(s)$, where $h^*(s)$ is the true optimal cost.

◇Important Formulas

Heuristic Function evaluation in A Search*
$f(s) = g(s) + h(s)$
Where: $g(s)$ = Cost accumulated from start node to current node $s$. $h(s)$ = Estimated cost from node $s$ to goal node.

Admissibility Condition
$h(s) \leq h^*(s)$

Consistency (Monotonicity) Condition
$h(u) \leq c(u, a, v) + h(v)$
Theorem: A consistent heuristic guarantees that when A* selects a state for expansion, the optimal path to that state has already been found. No re-expansion of explored states is required.

◇Theoretical Framework: A* State Space Expansion & Evaluation

A* Min-Priority Queue Execution Pipeline

◇Worked Examples

8-Puzzle Heuristics:

1. Number of misplaced tiles: $h(s)$ = count of tiles not in their goal position.
2. Total Manhattan Distance: $h(s)$ = sum of horizontal and vertical distances of each tile from its target location.

A Algorithm Walkthrough:*

1. Add $s_{start}$ to FRONTIER with priority $h(s_{start})$.
2. While FRONTIER is not empty:
   • Remove state $s$ with the lowest priority $p$. Let $c$ be the cost up to $s$.
   • If $\text{IsEnd}(s)$ then return the solution.
   • Add $s$ to EXPLORED.
   • For each action $a \in \text{Actions}(s)$:

• Get successor $s' = \text{Succ}(s, a)$
• If $s'$ is not yet in EXPLORED, update $s'$ in FRONTIER with priority $c + \text{Cost}(s, a) + h(s')$.

◇References & Navigation

• Previous Topic: ◇Uniform Cost Search
• Next Topic: ◇Adversarial Games
• Related Notes: ◇Informed Search, ◇Dijkstra's Algorithm (Advanced)