Dovetailing (computer science)

From Wikipedia, the free encyclopedia

Dovetailing is a technique in algorithm design (such an algorithm is sometimes referred to as a dovetailer). It refers to interleaving different computations, performing them, in a sense, simultaneously.

To illustrate, consider performing a search in a tree in a breadth-first, rather than depth-first manner. This preference is useful when the tree potentially contains a path of infinite length - if a depth-first search (DFS) was used, part of the tree would potentially never be explored. Accordingly a breadth-first search (BFS) is used, which visits nodes according to their distance from the root. This avoids the problem caused by a depth-first search moving down an infinite path.

Now the BFS approach of visiting each child on the same level of the tree is like performing a single step for a particular program. The DFS approach is like running one program at a time, moving to the next only when it is fininished running (which may take an infinite amount of time).

Etymology: 1. The term might have come from card shuffling. 2. This technique is known as dovetailing in analogy with the interleaving ends of a dovetail joint in woodworking.