COMP2121›Heuristics in Problem Solving

Artificial IntelligenceTopic 5 of 19Regular Notes

Heuristics in Problem Solving

2 minread

424words

Beginnerlevel

📘 Problem Solving by Searching: Heuristics

1. What is a Heuristic?

A heuristic is a technique used in informed search algorithms that provides an estimate of the cost or distance from a given state to the goal.

Denoted as h(n): the estimated cost from node n to the goal.
Used to guide the search process more intelligently by predicting which paths are more promising.

Think of it as a “rule of thumb” or a “best guess” that helps AI make decisions faster.

2. Why Use Heuristics?

Improves efficiency by reducing the number of states explored.
Helps avoid blind or exhaustive searching.
Essential for complex or large problem spaces (e.g., games, maps, puzzles).

3. Good Heuristic Qualities

Property	Description
Admissibility	A heuristic is admissible if it never overestimates the actual cost to reach the goal. Guarantees optimal solutions with A*.
Consistency (Monotonicity)	For every node $n$ and successor $n'$ , the heuristic satisfies:
$h(n) \leq c(n, n') + h(n')$ .
Ensures A* doesn't need to revisit nodes.
Efficiency	It should reduce the number of nodes expanded significantly.
Accuracy	The closer the heuristic is to the actual cost, the better.

4. Common Heuristic Examples

Problem	Heuristic	Explanation
Map routing	Straight-line distance (Euclidean)	Distance from current location to destination
8-puzzle	Number of misplaced tiles	Counts how many tiles are not in correct position
8-puzzle	Manhattan distance	Total distance tiles are away from their goal positions (row + column)
Chess	Material advantage	Value of current pieces vs. opponent’s

5. Role in Informed Search Algorithms

Algorithm	Use of Heuristic
Greedy Best-First Search	Uses only h(n) (chooses node that looks closest to goal)
*A Search**	Uses f(n) = g(n) + h(n) (combines path cost + heuristic estimate)

6. Designing Heuristics

A good heuristic should:

Be problem-specific.
Be easy to compute.
Be admissible (for optimal A* results).
Capture meaningful insights into the problem.

✅ Summary Table

Term	Definition
Heuristic (h(n))	Estimated cost from node n to the goal
Admissible	Never overestimates the actual cost
Consistent	Satisfies triangle inequality: $h(n) \leq c(n, n') + h(n')$
Role	Guides search, improves efficiency

Previous topic 4

Problem Solving by Searching: Uninformed searching

Next topic 6

Local searching algorithms

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.

COMP2121›Heuristics in Problem Solving

Artificial IntelligenceTopic 5 of 19Regular Notes

Heuristics in Problem Solving

2 minread

424words

Beginnerlevel

📘 Problem Solving by Searching: Heuristics

1. What is a Heuristic?

A heuristic is a technique used in informed search algorithms that provides an estimate of the cost or distance from a given state to the goal.

Denoted as h(n): the estimated cost from node n to the goal.
Used to guide the search process more intelligently by predicting which paths are more promising.

Think of it as a “rule of thumb” or a “best guess” that helps AI make decisions faster.

2. Why Use Heuristics?

Improves efficiency by reducing the number of states explored.
Helps avoid blind or exhaustive searching.
Essential for complex or large problem spaces (e.g., games, maps, puzzles).

3. Good Heuristic Qualities

Property	Description
Admissibility	A heuristic is admissible if it never overestimates the actual cost to reach the goal. Guarantees optimal solutions with A*.
Consistency (Monotonicity)	For every node $n$ and successor $n'$ , the heuristic satisfies:
$h(n) \leq c(n, n') + h(n')$ .
Ensures A* doesn't need to revisit nodes.
Efficiency	It should reduce the number of nodes expanded significantly.
Accuracy	The closer the heuristic is to the actual cost, the better.

4. Common Heuristic Examples

Problem	Heuristic	Explanation
Map routing	Straight-line distance (Euclidean)	Distance from current location to destination
8-puzzle	Number of misplaced tiles	Counts how many tiles are not in correct position
8-puzzle	Manhattan distance	Total distance tiles are away from their goal positions (row + column)
Chess	Material advantage	Value of current pieces vs. opponent’s

5. Role in Informed Search Algorithms

Algorithm	Use of Heuristic
Greedy Best-First Search	Uses only h(n) (chooses node that looks closest to goal)
*A Search**	Uses f(n) = g(n) + h(n) (combines path cost + heuristic estimate)

6. Designing Heuristics

A good heuristic should:

Be problem-specific.
Be easy to compute.
Be admissible (for optimal A* results).
Capture meaningful insights into the problem.

✅ Summary Table

Term	Definition
Heuristic (h(n))	Estimated cost from node n to the goal
Admissible	Never overestimates the actual cost
Consistent	Satisfies triangle inequality: $h(n) \leq c(n, n') + h(n')$
Role	Guides search, improves efficiency

Previous topic 4

Problem Solving by Searching: Uninformed searching

Next topic 6

Local searching algorithms

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.