AI search techniques

CIE A-Level Computer Science· Unit 13: Computational thinking & problem solving· 15 min read

1. Uninformed (Blind) Search★★☆☆☆⏱ 4 min

📘 Definition

Uninformed Search

Search algorithms that do not use any problem-specific heuristic information to guide exploration, relying only on the structure of the state space. Also called blind search.

Example:

Finding an exit in a maze with no information about how far you are from the exit

Two of the most common uninformed search methods tested in CIE are breadth-first search (BFS) and depth-first search (DFS). They follow different traversal strategies with different trade-offs:

- Breadth-First Search (BFS): Explores all nodes at the current depth level before moving to nodes at the next depth level. Uses a FIFO queue for node storage. Guarantees the shortest path in unweighted graphs.
- Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Uses a LIFO stack (or recursion) for storage. Does not guarantee the shortest path.

📐 Worked Example

Given an unweighted graph with start node A and goal node G, edges: A → B, A → C; B → D, B → E; C → F; F → G. List the order of node expansion for BFS.

1
1. Initialize queue with start node A, mark A as visited.
2
1. Dequeue A, add A to expansion order, enqueue unvisited neighbours B, C. Expansion order: [A]
3
1. Dequeue B, add B to expansion order, enqueue unvisited neighbours D, E. Expansion order: [A, B]
4
1. Dequeue C, add C to expansion order, enqueue unvisited neighbour F. Expansion order: [A, B, C]
5
1. Dequeue D, add to expansion order (no unvisited neighbours). Expansion order: [A, B, C, D]
6
1. Dequeue E, add to expansion order (no unvisited neighbours). Expansion order: [A, B, C, D, E]
7
1. Dequeue F, add to expansion order, enqueue unvisited neighbour G. Expansion order: [A, B, C, D, E, F]
8
1. Dequeue G (goal node), add to expansion order. Final order: [A, B, C, D, E, F, G]

Exam tip:

Always remember that BFS only guarantees the shortest path for unweighted graphs. If step costs vary, it will not find the optimal path.

2. Time and Space Complexity★★★☆☆⏱ 3 min

CIE regularly asks for complexity comparisons, measured using: $b$ = branching factor (average number of neighbours per node), $d$ = depth of the shallowest goal node, $m$ = maximum depth of the state space.

Algorithm	Time Complexity	Space Complexity	Shortest Path Guarantee
BFS	$O (b^{d})$	$O (b^{d})$	Yes
DFS	$O (b^{m})$	$O (bm)$	No

BFS has exponential space complexity because it stores all nodes at the current depth level, making it impractical for large state spaces. DFS only stores nodes along the current active path, so it has much lower memory requirements, but can get stuck on infinite deep branches.

✓ Quick check

Test your understanding:

What is the space complexity of BFS for a goal at depth $d$ ?
- $O (b d)$
- $O (b^{d})$
- $O (b^{m})$
Reveal answer
1 —
Correct! BFS stores all nodes up to depth $d$ , leading to exponential space complexity.
Which algorithm guarantees the shortest path in an unweighted graph?
- DFS
- BFS
- Neither
Reveal answer
1 —
Correct! BFS explores all nodes at each depth before moving deeper, so the first time it reaches the goal is via the shortest path.

3. Informed Search: A* Algorithm★★★★☆⏱ 5 min

📘 Definition

Informed Search

Search algorithms that use problem-specific heuristic information to estimate how close a state is to the goal, prioritising more promising paths to find solutions faster than uninformed search.

📘 Definition

Admissible Heuristic

A heuristic function that never overestimates the actual cost to reach the goal from the current state. A* search guarantees an optimal solution if the heuristic is admissible.

A* search is the most common informed search method tested in CIE. It uses the cost function:

f(n) = g(n) + h(n)

- $g (n)$ = actual cost from the start node to node $n$
- $h (n)$ = heuristic estimate of the cost from node $n$ to the goal

📐 Worked Example

Start node S, goal node G. Edge costs: S→A = 2, S→B = 3, A→G = 5, B→G = 2. Heuristics: $h (S) = 6$ , $h (A) = 4$ , $h (B) = 1$ , $h (G) = 0$ . Find the A* expansion order and optimal path. Confirm heuristic is admissible.

1
1. Calculate $f (n)$ for neighbours of S:
2
For A: $f (A) = 2 + 4 = 6$ . For B: $f (B) = 3 + 1 = 4$ .
3
1. Select the node with the lowest $f (n)$ (B), add B to expansion order.
4
1. Expand B, calculate $f (G) = (3 + 2) + 0 = 5$ . G is the goal.
5
1. Check admissibility: True cost from A to G = 5, heuristic $h (A) = 4$ (does not overestimate). True cost from B to G = 2, heuristic $h (B) = 1$ (does not overestimate). Heuristic is admissible.
6
Final expansion order: [S, B, G]. Optimal path: S → B → G, total cost = 5.

Exam tip:

Always show your calculation of $f (n)$ for every step of A* to get full marks, even if the answer seems obvious.

4. Exam Comparison of Search Techniques★★★☆☆⏱ 3 min

Methods compared

CIE often asks to select the right search technique for a given problem. Below is a summary of key trade-offs:

BFS

Used for small, shallow unweighted problems where shortest path is required

+ Pros: Guarantees shortest path, simple to implement

− Cons: Exponential space complexity, not for large problems

DFS

Used for large deep problems where memory is limited

+ Pros: Very low space complexity, simple to implement

− Cons: No shortest path guarantee, risk of infinite loops

A* Search

Used for practical search problems where a good heuristic is available

+ Pros: Optimal (with admissible heuristic), much faster than uninformed search

− Cons: High worst-case space complexity, performance depends on heuristic quality

5. Common Pitfalls

Wrong move:

Claiming DFS always finds the shortest path in unweighted graphs

Why:

DFS explores branches depth-first, so the first time it reaches the goal is not necessarily the shortest path

Correct move:

Always state that BFS (for unweighted graphs) and A* (with admissible heuristic) are the only techniques that guarantee a shortest path

Wrong move:

Mixing up BFS and DFS space complexity

Why:

Many students incorrectly state DFS has higher space complexity than BFS

Correct move:

Remember: BFS space = $O (b^{d})$ , DFS space = $O (bm)$ , BFS has far higher space complexity for large problems

Wrong move:

Claiming A* always gives an optimal solution regardless of heuristic

Why:

A* only guarantees optimality if the heuristic is admissible (never overestimates true cost)

Correct move:

Always check if the heuristic is admissible before confirming A* will output an optimal path

Wrong move:

Counting the goal node as expanded when it is first discovered, not when it is selected

Why:

CIE follows the standard A* process where a node is only expanded when it is selected as the lowest f(n) node from the open list

Correct move:

Only add the goal node to your expansion order when it is selected for expansion, not when it is first added to the open list

6. Quick Reference Cheatsheet

Technique	Type	Space Complexity	Optimal Path Guarantee	Use Case
BFS	Uninformed	$O (b^{d})$	Yes (unweighted)	Small shallow problems
DFS	Uninformed	$O (bm)$	No	Large deep problems, limited memory
A*	Informed	$O (b^{d})$ (worst)	Yes (if admissible)	Practical search with good heuristic

7. Frequently Asked

Do I need to memorize complexity values for exams?

Yes, CIE examiners regularly ask for comparisons of time and space complexity, so you should memorize the big-O values for each common search technique.

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 1
Search algorithm comparison
2023 · 1
A* search path calculation
2024 · 1
Uninformed search complexity question

Going deeper

syllabusCIE 9618 2026 Syllabus Page 32Official search techniques syllabus section

What's Next

AI search techniques form the foundation of many advanced AI applications, from route navigation to game pathfinding and automated planning. For CIE 9618, this topic is frequently combined with complexity analysis and graph traversal questions, so mastering these core concepts will help you answer a wide range of problem-solving questions in Paper 1. The search strategies you learn here also extend directly to constraint satisfaction problems, another common AI topic tested in the syllabus.