Data-driven vs goal-driven search

Two directions, one graph

Given a state space $[N, A, S, GD]$ you can walk it from either end, and both directions find exactly the same solutions — the choice is about efficiency, never correctness. This is exam Q2, and it recurs as forward-vs-backward chaining in production systems (Module 5).

• Data-driven search (forward chaining). Start from the given facts $S$ and apply operators/rules to generate new facts, growing what is known until a state satisfying $GD$ appears. You reason from what you have toward what you want.
• Goal-driven search (backward chaining). Start from the goal $GD$, find operators/rules whose result matches the goal, and treat their requirements as new subgoals. Recurse until the subgoals are met by the known facts $S$. You reason from what you want back toward what you have.

How to choose

The deciding question is always: which direction has the smaller branching factor? Pick the end that fans out less. Concretely:

Prefer data-driven (forward) when — most or all data are given up front; there are many possible goals but few rules apply to the data; or it is hard to state a goal in advance. This fits interpretation problems: classify geological data, interpret a mass spectrum (DENDRAL), monitor sensor streams. The risk is generating many irrelevant facts if the data don't constrain the space.

Prefer goal-driven (backward) when — a single goal or hypothesis is clearly given; many rules match the data (forward search would fan out wildly); or data must be acquired on demand rather than given. This fits diagnosis and theorem proving: MYCIN works backward from candidate diseases, asking only the questions a live hypothesis needs. Because only rules that could contribute to the goal are ever explored, no irrelevant facts are generated.

Worked example — the descendant query

Suppose a genealogy where each person has up to 3 children but exactly 1 set of parents, and you ask "is person I a descendant of person T, ten generations back?"

• Forward from $T$: each step branches by the child count $\approx 3$, so ten generations explore on the order of $3^{10}\approx 59,000$ people — most of them irrelevant cousins of $I$.
• Backward from $I$: each step follows the single parent link upward, branching $\approx 1$, so the search is essentially a straight line of ~10 nodes (with the small fan-out of "which parent").

The goal ($I$) is given and the backward branching factor is far smaller, so goal-driven search wins decisively — the same answer for a tiny fraction of the work. That branching-factor comparison is the heart of a good Q2 answer.