Breadth-first and depth-first searches are two similar methods for brute-force solving problems of combinatorial enumeration.
A depth-first search starts at a node, and traverses from child to grandchild downward until either a solution is found, or can be shown not to exist. It will then backtrack up one level, taking the next child at that level and again proceeding downward. Whenever a given level is exhausted of possibilities it goes up a level and over to the next child.
Breadth-first searches in contrast proceed horizontally, visiting all children before going to grandchildren.
may be used effectively when only one valid solution is needed; otherwise, a breadth-first search using something like NestWhile
can often get the desired results in less time. The reason is that depth-first search incurs an extra cost when backtracking, whereas breadth-first search does not need to backtrack.
includes a usage that operates on directed graphs. This particular usage compares well with the System
, and can be used to obtain similar outputs (see "Properties and Relations" section below).
When traversing an input graph, the algorithm simply follows directed edges immediately to terminal nodes, backtracks to branch points, and continues to take new paths until a solution is found. In practice, this can be done by keeping a path history as a memory stack.
The two primary methods generate partial search graphs, rather than requiring a complete search graph as input. Generation of a search space is done using a state update function, either stateUpdate or iterator.
takes an input state
as a first argument and draws a second argument from levelData
. The list levelData
is partitioned into sub-lists containing state differentials as items. An input state at level t
is then combined with a differential from the (t+1)th
sub-list of levelData
to obtain the next state. If the input state
is inconsistent with the next differential state from levelData
will return Nothing
. This is a failure signal, which causes the algorithm to keep searching for a valid solution. Valid solutions are obtained by combining one differential from each level of levelData
, and they must also satisfy the test solutionQ
Similarly, when a state is input to an iterator, the return is a list of candidate states or an empty list. The empty list is a termination condition, which passes the candidate solution to solutionQ. If the state satisfies solutionQ it will be returned as a positive result. If the state does not satisfy solutionQ, it is ignored and the search continues. As opposed to the method using levelData, enumerating the search space via an iterator allows solutions to be found at any depth.
The test solutionQ should be a function of one variable. Either it takes the name of a terminal vertex on an input graph, or it takes a terminal state created via stateUpdate or iterator. In fact, states generated by stateUpdate or iterator can be thought of as nodes on a search graph.
No two backtracking problems are exactly alike, and results can vary based on ordering of candidate states. Optimizations can often be found by including heuristic-based state selection in either stateUpdate or iterator.