COMP2121›Problem Solving by Searching: Informed searching

Artificial IntelligenceTopic 3 of 19Regular Notes

Problem Solving by Searching: Informed searching

3 minread

480words

Beginnerlevel

📘 Problem Solving by Searching: Informed Searching

1. What is Informed Search?

Informed Search (also called heuristic search) uses additional knowledge (heuristics) about the problem to guide the search towards the goal more efficiently.

Unlike uninformed search, it uses information about the goal’s location.
This helps reduce the number of states explored and find solutions faster.

2. What is a Heuristic?

A heuristic is a function, denoted as h(n), that estimates the cost or distance from a given state n to the goal.

Good heuristics improve search efficiency.
Example: In pathfinding, h(n) might be the straight-line distance from node n to the goal.

3. Popular Informed Search Algorithms

Algorithm	Description	Uses	Optimal?	Complete?
Greedy Best-First Search	Expands the node that appears closest to the goal based on h(n)	Fastest search when heuristic is good	No	No (can get stuck)
A*	Combines path cost so far (g(n)) + heuristic estimate (h(n)) to select nodes	Finds optimal path efficiently	Yes (if h(n) is admissible)	Yes

**4. How Does A* Work?**

Evaluation function:
$f(n) = g(n) + h(n)$
- $g(n)$ = cost from start node to current node $n$
- $h(n)$ = estimated cost from $n$ to goal
A* expands nodes with the lowest $f(n)$ value first.
It balances between exploring nodes close to the start and those close to the goal.

5. Properties of Heuristics

Property	Meaning
Admissible	Heuristic never overestimates the true cost to reach the goal (always optimistic)
Consistent (Monotonic)	For every node $n$ and successor $n'$ , $h(n) \leq c(n,n') + h(n')$ , where $c(n,n')$ is the step cost
Effective heuristic	One that is as close as possible to the actual cost

6. Example: Finding Route on a Map

Goal: Find shortest path from city A to city B.
Heuristic (h(n)): Straight-line distance (Euclidean distance) to city B.
Using A*, the search will prioritize routes that seem promising based on the combined actual cost so far and the heuristic estimate.

✅ Summary

Concept	Explanation
Informed Search	Search that uses heuristics to guide search
Heuristic (h(n))	Estimates cost from current state to goal
Greedy Best-First	Uses only heuristic, fast but not guaranteed
A*	Uses cost so far + heuristic, guaranteed optimal (with admissible heuristic)

Previous topic 2

Introduction to Reasoning and Knowledge Representation

Next topic 4

Problem Solving by Searching: Uninformed searching

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.

COMP2121›Problem Solving by Searching: Informed searching

Artificial IntelligenceTopic 3 of 19Regular Notes

Problem Solving by Searching: Informed searching

3 minread

480words

Beginnerlevel

📘 Problem Solving by Searching: Informed Searching

1. What is Informed Search?

Informed Search (also called heuristic search) uses additional knowledge (heuristics) about the problem to guide the search towards the goal more efficiently.

Unlike uninformed search, it uses information about the goal’s location.
This helps reduce the number of states explored and find solutions faster.

2. What is a Heuristic?

A heuristic is a function, denoted as h(n), that estimates the cost or distance from a given state n to the goal.

Good heuristics improve search efficiency.
Example: In pathfinding, h(n) might be the straight-line distance from node n to the goal.

3. Popular Informed Search Algorithms

Algorithm	Description	Uses	Optimal?	Complete?
Greedy Best-First Search	Expands the node that appears closest to the goal based on h(n)	Fastest search when heuristic is good	No	No (can get stuck)
A*	Combines path cost so far (g(n)) + heuristic estimate (h(n)) to select nodes	Finds optimal path efficiently	Yes (if h(n) is admissible)	Yes

**4. How Does A* Work?**

Evaluation function:
$f(n) = g(n) + h(n)$
- $g(n)$ = cost from start node to current node $n$
- $h(n)$ = estimated cost from $n$ to goal
A* expands nodes with the lowest $f(n)$ value first.
It balances between exploring nodes close to the start and those close to the goal.

5. Properties of Heuristics

Property	Meaning
Admissible	Heuristic never overestimates the true cost to reach the goal (always optimistic)
Consistent (Monotonic)	For every node $n$ and successor $n'$ , $h(n) \leq c(n,n') + h(n')$ , where $c(n,n')$ is the step cost
Effective heuristic	One that is as close as possible to the actual cost

6. Example: Finding Route on a Map

Goal: Find shortest path from city A to city B.
Heuristic (h(n)): Straight-line distance (Euclidean distance) to city B.
Using A*, the search will prioritize routes that seem promising based on the combined actual cost so far and the heuristic estimate.

✅ Summary

Concept	Explanation
Informed Search	Search that uses heuristics to guide search
Heuristic (h(n))	Estimates cost from current state to goal
Greedy Best-First	Uses only heuristic, fast but not guaranteed
A*	Uses cost so far + heuristic, guaranteed optimal (with admissible heuristic)

Previous topic 2

Introduction to Reasoning and Knowledge Representation

Next topic 4

Problem Solving by Searching: Uninformed searching

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.