BreadthAndDepth

Trying to find something in a multidimensional space? There are two major approaches. One can look broadly but shallowly at first, repeatedly plowing the same ground, working deeper and deeper until the goal is achieved. Or one can plunge a needle straight through the realm of possibilities, probing all the way down in various places until finding success.

The first way, breadth-first search, makes sense in many circumstances:

• when the target is easily recognized and likely to be seen near the surface;
• when survey information from a quick scan provides valuable guidance, perhaps even a partial answer that enhances the efficiency of later search passes;
• when the space of possibilities is huge (or infinite) and time is limited; and
• when the cost of probing deep and then returning to the top level is too high.

Contrariwise, the other method, depth-first search, has at times its own advantages:

• when the goal is known not to be near the surface;
• when superficial information is deceptive or valueless; and
• when tunneling down is relatively cheap, but storing broad-area survey data is costly or infeasible.

In real life, the right approach depends on the problem; often a mixed strategy is best. Logic programming (as implemented, for example in the PROLOG language) applies depth-first search toward a goal --- but with programmer-controlled modifications to "cut one's losses" and give up when a line of reasoning leads into impenetrable thickets. Most computer chess programs apply a breadth-first iterative-deepening method --- gathering information from positions a few half-moves ahead to optimize later analyses that go further into the future of the game.

We do the same in writing or drawing ... sketching out the general scene in broad brushstrokes or terse outline form ... focusing on certain areas and working on their details ... moving to other parts of the composition, then returning to add additional nuances ... and so forth. Perhaps the complementary aspects of breadth-first and depth-first can apply to other situations in life?

Friday, June 11, 1999 at 18:41:06 (EDT) = 1999-06-11

TopicScience

(correlates: PoeticLines, BovineMind, LearningFromAdversity, ...)