Questions: Forward and Backward Search Strategies in Problem Solving

Question 1

A mathematician needs to prove a specific theorem starting from standard axioms. Why is backward search typically more efficient than forward search for this problem?

• A. Mathematicians are trained to work backward, so it feels more natural
• B. The theorem has few valid predecessor lemmas, while axioms can be combined in essentially unlimited forward sequences
• C. Forward search requires more memory to store intermediate proof states
• D. Backward search avoids the need to verify whether intermediate steps are correct

Answer: (B)

The efficiency advantage comes from branching factor at each end. A theorem to be proved has few lemmas that could directly yield it — the goal state is highly constrained, producing a small number of predecessor states when searched backward. Starting from axioms and trying to derive the theorem forward generates an enormous number of possible combinations at each step. Backward search exploits the goal's constraint to prune the search space from the start.

Question 2

Problem A has an initial state with 3 forward successors and a goal with 30 predecessor states. Problem B has an initial state with 30 forward successors and a goal with 3 predecessor states. Assuming equal depth, which search direction is efficient for each?

• A. Forward for both — we always know the initial state better than the goal
• B. Backward for both — starting from the goal reduces ambiguity
• C. Forward for A, backward for B — search should start at the more constrained end
• D. Bidirectional for both — this is always optimal regardless of branching factor

Answer: (C)

Search efficiency depends on branching factor at each end of the problem space. Problem A's initial state has only 3 successors (a constrained start), so forward search stays narrow. Problem B's goal has only 3 predecessors (a constrained end), so backward search stays narrow. The principle is: start at the more constrained end to minimize nodes explored. Bidirectional search helps when both ends are similarly constrained, not as a universal default.

Question 3

Forward search is generally more efficient than backward search because problem solvers generally know more about their starting position than about the goal.

• T. True
• F. False

Answer: False

Efficiency depends on the branching factor — the number of successors or predecessors at each state — not on how well the problem solver 'knows' each end. When the goal is highly constrained (few legal predecessor states), backward search visits far fewer nodes even if the goal seems abstractly less familiar. The same problem type can warrant different search directions depending on constraint topology.

Question 4

Bidirectional search can dramatically reduce search complexity because each frontier only needs to reach the halfway point, reducing the effective search depth from d to d/2.

• T. True
• F. False

Answer: True

In exponential search trees, complexity is b^d where b is branching factor and d is depth. By searching from both ends simultaneously and meeting in the middle, each frontier searches only to depth d/2, yielding roughly 2×b^(d/2) rather than b^d — an enormous reduction for large d. Human expert problem solvers use an analogous strategy by alternating between working from givens and working back from the goal as intermediate subgoals emerge.

Question 5

Why should the choice between forward and backward search be based on problem structure rather than problem type, and what structural feature should guide the decision?

Model answer: The relevant structural feature is the branching factor at each end of the problem space — specifically, how many successors the initial state generates compared to how many predecessor states the goal generates when reversed. When one end is more tightly constrained (fewer legal transitions), searching from that end keeps the frontier narrow and avoids exploring dead-end branches. The same problem type may have different constraint topologies in different instances, so no single type always favors one search direction.

This is the key insight that separates genuine understanding from surface familiarity. Students who memorize 'use backward search for proofs' will fail when a proof instance happens to have a tightly constrained starting point. The principle is: locate the constraint and start there.