# AI search techniques

> CIE A-Level Computer Science · 9618
> Source: https://www.owlsprep.com/study/cie-9618-u13-ai-search-techniques/

This sub-topic covers core AI search techniques for solving state-space problems, tested in CIE 9618 Paper 1. We cover both uninformed blind search and informed heuristic search, their complexity, guarantees and exam use cases.

**Prerequisites:** [Basic algorithm complexity analysis](https://www.owlsprep.com/study/as-a-level-algorithm-complexity/); [Graph traversal fundamentals](https://www.owlsprep.com/study/graph-traversal-algorithms/)

## Learning objectives

- Distinguish between uninformed and informed search methods for state-space problems
- Apply breadth-first, depth-first and A* search to simple problem graphs
- Compare time and space complexity of common search techniques
- Explain the role of admissible heuristics in optimal A* search

## Uninformed (Blind) Search

**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. 2. Dequeue A, add A to expansion order, enqueue unvisited neighbours B, C. Expansion order: [A]
3. 3. Dequeue B, add B to expansion order, enqueue unvisited neighbours D, E. Expansion order: [A, B]
4. 4. Dequeue C, add C to expansion order, enqueue unvisited neighbour F. Expansion order: [A, B, C]
5. 5. Dequeue D, add to expansion order (no unvisited neighbours). Expansion order: [A, B, C, D]
6. 6. Dequeue E, add to expansion order (no unvisited neighbours). Expansion order: [A, B, C, D, E]
7. 7. Dequeue F, add to expansion order, enqueue unvisited neighbour G. Expansion order: [A, B, C, D, E, F]
8. 8. 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.

## Time and Space Complexity

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.

**Check your understanding**

Test your understanding:

1. What is the space complexity of BFS for a goal at depth $d$?

   - $O(bd)$
   - $O(b^d)$
   - $O(b^m)$

   *Answer:* $O(b^d)$

   *Why:* Correct! BFS stores all nodes up to depth $d$, leading to exponential space complexity.

2. Which algorithm guarantees the shortest path in an unweighted graph?

   - DFS
   - BFS
   - Neither

   *Answer:* BFS

   *Why:* Correct! BFS explores all nodes at each depth before moving deeper, so the first time it reaches the goal is via the shortest path.

## Informed Search: A* Algorithm

**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.

**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. 2. Select the node with the lowest $f(n)$ (B), add B to expansion order.
4. 3. Expand B, calculate $f(G) = (3+2) + 0 = 5$. G is the goal.
5. 4. 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.

## Exam Comparison of Search Techniques

**Comparing methods**

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

**Exam command terms**

- **Compare** — State similarities and differences, including complexity, guarantees and use cases *(Compare BFS and DFS search techniques)*

- **Calculate** — Show all intermediate steps for node expansion and cost calculation *(Calculate the expansion order for A* search)*

## Common pitfalls

- **Wrong:** Claiming DFS always finds the shortest path in unweighted graphs
  - Why it fails: DFS explores branches depth-first, so the first time it reaches the goal is not necessarily the shortest path
  - Correct: Always state that BFS (for unweighted graphs) and A* (with admissible heuristic) are the only techniques that guarantee a shortest path
- **Wrong:** Mixing up BFS and DFS space complexity
  - Why it fails: Many students incorrectly state DFS has higher space complexity than BFS
  - Correct: Remember: BFS space = $O(b^d)$, DFS space = $O(bm)$, BFS has far higher space complexity for large problems
- **Wrong:** Claiming A* always gives an optimal solution regardless of heuristic
  - Why it fails: A* only guarantees optimality if the heuristic is admissible (never overestimates true cost)
  - Correct: Always check if the heuristic is admissible before confirming A* will output an optimal path
- **Wrong:** Counting the goal node as expanded when it is first discovered, not when it is selected
  - Why it fails: 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: 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

## 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 |

## 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.

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u13-ai-search-techniques/