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.