Search Algorithms: BFS, DFS, Best-First, A*, Branch and Bound

1. State space vs. search space

State space is the full graph of all possible states and moves. It exists implicitly. Search space is the part you actually generate and keep in memory via parent pointers while running the algorithm. The exam graph is the state space; the tree of parent pointers you draw is the search space.

The graph is generated on the fly. You never hold the whole map. You hold two lists:

• OPEN: frontier, nodes generated but not yet expanded.
• CLOSED: nodes already expanded (inspected).

Solved mini-example. Start \(S\), neighbours \(A,B\). OPEN = \(\{S\}\). Expand \(S\), then CLOSED = \(\{S\}\), OPEN = \(\{A,B\}\). The search space so far is two parent pointers \(A \to S, B \to S\). The rest of the state space does not exist in memory yet.

2. MoveGen and GoalTest

MoveGen(n) returns the neighbours of \(n\), in this course in alphabetical order. GoalTest(n) returns true iff \(n\) is the goal; it is checked when a node is picked for expansion, not when it is generated.

OPEN = [S]; CLOSED = []
parent = {}
while OPEN not empty:
    n = pick(OPEN)            # pick rule = the algorithm
    if GoalTest(n): return path(n)   # follow parent pointers to S
    move n to CLOSED
    for m in MoveGen(n):      # alphabetical
        if m not in OPEN+CLOSED or found-cheaper-path(m):
            parent[m] = n; add/update m in OPEN

Solved mini-example. MoveGen(S) = [A, B]. GoalTest(G) = true only. If OPEN = [A, B] and the algorithm picks B first, B is expanded before A. That ordering difference is the entire difference between BFS, DFS, Best, A*, and B and B. The loop is identical; only pick() changes.

3. The five pick rules: one table

Let \(g(n)\) = actual edge cost from \(S\) to \(n\) along the best known parent chain. Let \(h(n)\) = heuristic estimate from \(n\) to \(G\). Let \(f(n) = g(n) + h(n)\).

Memory hook: Best looks forward (\(h\)), B and B looks backward (\(g\)), A* looks both ways (\(f\)). BFS and DFS do not look at costs at all.

Solved mini-example (finish vs optimal). DFS on a finite graph with a visited check finishes, but the first path it finds to \(G\) is the deepest one, not the cheapest. So "finishes = yes" and "optimal = no" are two separate columns. Students lose marks by mixing them.

Path vs. inspection order. Inspection order is the sequence of nodes picked out of OPEN. The path is only the parent chain from \(G\) back to \(S\), a subsequence of the inspection order. Exam trap: writing the full inspection order when asked for the path. Always reconstruct via parent pointers.

4. Interactive traces: one graph, five algorithms

Teaching graph used below. It is designed so the algorithms disagree: Best-First is lured by \(C\) (\(h=2\)) down the expensive \(S \to C \to F \to G\) corridor (cost 13), while A* and B and B find \(S \to A \to D \to G\) (cost 9). BFS and DFS ignore costs entirely. MoveGen is alphabetical, tie-break by label.

5. Solved PYQ: the grid map with the river

5a. Full question

5b. Answers first

Best: S,D,A,G. A*: S,F,A,G. B and B: S,F,E,C,G. Shortest: Branch and Bound. Heuristic: Inadmissible.

Schematic of the PYQ situation (not to scale): Best dives straight at G through D; A* corrects one step via F; only B and B walks the long way round the river via E and C. Toggle the paths below.

5c. Step by step solution

1. Write h on every node first (G = 0). h = Manhattan distance on the grid. This step is compulsory: every pick below depends on it. Note the river: nodes whose straight line to G crosses water get a small h but a large true cost. That mismatch is what breaks admissibility later.
2. Best-First gives S,D,A,G. From S, the neighbour with smallest h is D, so expand D. From D, the OPEN nodes include A and F; A has the smaller h, so expand A. From A, G itself is a neighbour with h = 0, which beats everything in OPEN, so expand G and stop. Path from parents: S,D,A,G. The algorithm never looked at edge costs, so it paid the expensive D to A crossing.
3. A* gives S,F,A,G. Label each OPEN node with g + h. S to D looks good on h alone, but its g + h loses to S to F after one step, because the D corridor piles up real cost against the river while F stays cheap. So A* expands F before D, then A, then G. Path: S,F,A,G. Better than Best, but still not the true shortest on this map.
4. Branch and Bound gives S,F,E,C,G. Label OPEN with g only. It spreads in cost order from S and discovers the cheap detour through F, E, C to G. Each edge is cheap, so the total is least. The first G popped from a g-sorted OPEN is the optimum by definition. Path: S,F,E,C,G. Skip cyclic paths (S,F,S...) as instructed.
5. Shortest path: Branch and Bound. Compare totals: B and B is the definition of shortest here, and it beats both A* and Best on this map. Tick Branch and Bound.
6. Heuristic: inadmissible. Find one witness node with h(n) above h*(n), the true cheapest cost from n to G. The river guarantees such a node: Manhattan distance ignores water, so a node whose straight line crosses the river has small h but large true cost. One witness suffices. Extra check: A* and B and B returned different paths with A* worse. With an admissible h, A* must return the optimum, so this disagreement alone proves inadmissibility.

6. Second flavor: water jugs (digit strings)

Some papers replace the map with three jugs. A state is a digit string ABC = litres in jugs a, b, c. Capacities: a = 5, b = 3, c = 2. Start 320, goal 401. Two sub-questions: shortest path as states, and the move sequence producing it.

Sanity check on MoveGen: MoveGen(212) = {032, 302, 410, 230}. From (2,1,2): aETb empties a into b ending exactly full (032); bEa empties b into a with room to spare (302); cEa empties c into a short of full (410); cETb empties c into b ending exactly full (230). Read each neighbour the same way: which jug emptied, which got topped, what is left.

Answers first: path 320,122,131,401; moves aTc,cTb,bEa. Trace: 320 --aTc--> 122 (c topped 0 to 2, a 3 to 1). 122 --cTb--> 131 (b topped 2 to 3, c 2 to 1). 131 --bEa--> 401 (b emptied 3 to 0 into a with room left, a 1 to 4).

6b. Walkthrough: BFS jug by jug (separate from the graph visualiser above)

7. Theory appendix: DFID, unknown heuristics, wA*

Three recurring theory questions sit beside the map. They need no graph, only the rules below. Answers are official keys, verified against the key symbols and re-derived by hand and by script.

Why this step. DFID re-runs depth-first search at each depth limit. If a node already on CLOSED is pruned, a shorter route discovered later is lost. Classic miss: \(D\) gets closed via the long route \(S \to A \to C \to D\), then \(B\) is refused as a second parent of \(D\), so the short route \(S \to B \to D \to G\) is never built and a longer path to \(G\) is returned instead. "Inspects" means generates and considers, not prunes. The lecture fix is exactly the keyed variant: let closed nodes back into OPEN and keep CLOSED only for parent info (or store the full path at each node).

Why this step. A* and WA* are optimal only if \(h\) is admissible, which is unknown here, so both are out. SMGS trades optimality for memory, so it is out. DFS is never optimal. BFS is optimal only for unit costs, so it drops out in the general-costs variant. Dijkstra and B and B use only \(g\) and stay optimal regardless of \(h\).

Why this step. As \(w\) grows, \(w \cdot h\) swamps \(g\) and the OPEN order converges to pure \(h\) order, which is Best-First (verified by script: the \(f\)-sorted order equals the \(h\)-sorted order for large \(w\)). At \(w = 0\), \(f = g\), which is exactly Dijkstra (verified: the orders match). Greedy search on \(h\) alone can walk past the optimum, so optimality goes even with an admissible \(h\).

Answers first: Q5 = new as well as closed nodes (both variants). Q6 = BFS, Dijkstra, B and B for unit costs; Dijkstra, B and B for general costs. Q7 = Best-First plus not-optimal for large \(w\); Dijkstra plus always-optimal for \(w = 0\).

8. Admissibility: the one-line test

\(h\) is admissible iff \(h(n) \le h^*(n)\) for every node \(n\), where \(h^*(n)\) is the true cheapest cost from \(n\) to \(G\). G itself has \(h(G)=0\). Consequences: A* is optimal iff \(h\) is admissible; B and B is optimal regardless; Best is never guaranteed optimal.

Solved mini-example. Node X has \(h(X)=6\). True cheapest X to G is 4 (say X to Y to G costs 1+3). Since 6 is above 4, \(h\) is inadmissible. One counterexample kills admissibility. If the true cost were 7 instead, this node passes, but you must still check all nodes.

Exam shortcut: if A* and B and B return different paths with A* worse, \(h\) is certainly inadmissible, because an admissible \(h\) would have forced A* onto the optimum. If they agree, \(h\) may be admissible (still verify with \(h \le h^*\)). Older papers add sometimes admissible and not enough information distractors: one violating node still kills admissibility outright, and mere agreement of A* with B and B never proves it, so pick a concrete verdict whenever the graph decides one.

9. Exam checklist (write this on the rough sheet)

1. Copy the graph, write edge costs and \(h\) on each node, mark S and G (\(h=0\)).
2. Fix MoveGen = alphabetical, tie-break = label. Never deviate.
3. Maintain OPEN, CLOSED, and parent pointers in a table, one row per expansion.
4. Best: sort OPEN by \(h\). A*: by \(g+h\). B and B: by \(g\). BFS: queue. DFS: stack.
5. GoalTest on expansion, not generation. Reconstruct the path from parents; report inspection order separately if asked.
6. Shortest = the B and B path, by definition. Admissible iff every \(h \le h^*\).