Lab: Search Algorithms in Python

Unit 3: Search Techniques for Problem Solving — Lab

In this lab, you will implement two search algorithms from scratch in Python, then verify their behavior against known correct answers. By the end of the lab, you will have working BFS and A* code that you can adapt for any graph or grid problem.

Learning Objectives

By completing this lab, you will be able to:

  1. Implement breadth-first search (BFS) on an explicit graph and return the correct path

  2. Implement A* search on a grid using Manhattan distance as the heuristic

  3. Explain why BFS finds the shortest hop-count path and A* finds the lowest-cost path

  4. Verify algorithm correctness using provided test cases

  5. Interpret the difference in nodes expanded between BFS and A*

Prerequisite concepts from this unit:

  • BFS (Section 3.3) — FIFO frontier, level-by-level expansion, optimal for uniform costs

  • A* (Section 3.4) — priority queue ordered by f(n) = g(n) + h(n), optimal with admissible h

  • Admissibility (Section 3.5) — h(n) ≤ h*(n) for all n; Manhattan distance is admissible on grids with 4-directional movement

  • Graph search (Section 3.2) — explored set prevents re-expansion of visited states

Setup

This lab runs in Google Colab (no local installation required) or any Jupyter-compatible environment with Python 3.8+.

Option A — Google Colab (recommended):

  1. Open colab.research.google.com

  2. Select File → Upload notebook

  3. Upload the Search_Lab_Student.ipynb file (download below)

  4. Run Runtime → Run all to confirm the environment loads

Option B — Local Jupyter:

  1. Install dependencies: pip install notebook

  2. Launch: jupyter notebook Search_Lab_Student.ipynb

Starter Notebook:

Search_Lab_Student.ipynb

The notebook contains:

  • All import statements and helper functions

  • Four task cells (Tasks 1–4) with # YOUR CODE HERE markers

  • Six test cells that check your implementation automatically

  • Markdown cells explaining each task

Lab Tasks Overview

The four tasks:

  1. Task 1: Implement BFS on a small city map graph — return the path from source to destination

  2. Task 2: Add path-cost tracking to your BFS and verify it finds the minimum-hop path

  3. Task 3: Implement A* on a 10×10 grid with obstacles — use Manhattan distance as h(n)

  4. Task 4: Compare BFS and A* on the same grid — count nodes expanded and explain the difference

Task Descriptions

Task 1: BFS on a Graph

You are given a Python dictionary representing a city map:

city_map = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E', 'G'],
    'G': ['F']
}

Implement a function bfs(graph, start, goal) that returns the path from start to goal as a list of node names. Your implementation must use a FIFO queue (the collections.deque class) and maintain an explored set to avoid revisiting nodes.

Expected output: bfs(city_map, 'A', 'G') should return ['A', 'C', 'F', 'G'] (3 hops — the shortest path).

Task 2: Verify BFS Optimality

The test cell for Task 2 checks multiple source/destination pairs and verifies that your BFS always returns the minimum-hop path. You do not need to write new code for this task — just confirm all tests pass after completing Task 1.

If a test fails, examine your BFS implementation:

  • Are you using a deque correctly (append to right, popleft from left)?

  • Are you tracking the explored set and the path correctly?

  • Are you returning the path by tracing parent pointers, not just the goal node?

Task 3: A* on a Grid

You are given a 10×10 grid represented as a 2D list where 0 = open and 1 = obstacle. The agent starts at (0, 0) (top-left) and must reach (9, 9) (bottom-right). Movement is 4-directional (up, down, left, right); each move costs 1.

Implement a_star(grid, start, goal) that:

  • Uses a min-priority queue (the heapq module) ordered by f(n) = g(n) + h(n)

  • Uses Manhattan distance as the heuristic: h(r, c) = |r - goal_r| + |c - goal_c|

  • Maintains an explored set (graph search)

  • Returns the path as a list of (row, col) tuples, or None if no path exists

Tip: Python’s heapq provides a min-heap. Push tuples (f_value, g_value, state, path) to keep the priority queue ordered by f.

Task 4: BFS vs. A* Node Count Comparison

Run both algorithms on the provided test grid and record the number of nodes each algorithm expands. Answer the reflection questions in the notebook Markdown cell:

  1. Which algorithm expanded more nodes?

  2. Why does A* expand fewer nodes on this grid?

  3. What would happen to A* if the heuristic were zero (h(n) = 0)?

  4. Is Manhattan distance still admissible if diagonal moves were allowed? Why or why not?

Grading Criteria

Component Description Points

Task 1: BFS implementation

Correct path returned; uses deque; maintains explored set

25

Task 2: BFS tests pass

All 5 BFS test cases return minimum-hop paths

15

Task 3: A* implementation

Correct path returned; uses heapq with f(n) = g(n) + h(n); graph search

35

Task 4: Reflection

Node counts recorded; all 4 reflection questions answered substantively (2–3 sentences each)

25

Total

100

Common pitfalls:

  • BFS: Forgetting to add a node to the explored set when it is added to the frontier (not when expanded) can cause BFS to explore the same node multiple times.

  • A*: Using a regular Python list as a priority queue instead of heapq will produce incorrect expansion order. Always use heapq.heappush and heapq.heappop.

  • Both: Make sure you reconstruct the full path from start to goal, not just return the goal node. Use a dictionary mapping each state to its parent.

Submission Instructions

  1. Complete all four tasks in the notebook

  2. Confirm all test cells show "PASS" (or explain any failures in a comment)

  3. Download your completed notebook: File → Download → Download .ipynb

  4. Submit via the Unit 3 Lab assignment in the course LMS

Want to see these algorithms visualized?

Next: Unit 3 Wrap-Up and Self-Assessment →

Lab code adapted from aima-python, MIT License, Copyright 2016 aima-python contributors.

This work is licensed under CC BY-SA 4.0.