算法设计技巧：dovetailing
在读Elements of the Theory of Computation一书时看到了一个词叫做“dovetailing”，查资料后发现这是一个设计算法的技巧。
Dovetailing, in algorithm design, is a technique that interweaves different computations, performing them essentially simultaneously. Algorithms that use dovetailing are sometimes referred to as dovetailers.
Consider a tree that potentially contains a path of infinite length: if a depth-first search is performed in this environment, the search may move down an infinite path and never return, potentially leaving part of the tree unexplored. However, if a breadth-first search is used, the existence of an infinite path is no longer a problem: each node is visited in a branching manner according to its distance from the root, so an infinite path will only impact the part of the search travelling down that path.
We can regard this tree as analogous to a collection of programs; in this case, the depth-first approach corresponds to running one program at a time, moving to the next only when the current program has finished running. In the case where one of the programs runs for an infinite amount of time, this transition will never happen. The breadth-first approach of visiting each child on the same level of the tree corresponds to dovetailing, where a single step is performed for every program before moving to the next. Thus, progress is made in each program, regardless of the potential existence of a program of infinite runtime.
In the case of an infinite number of programs, all potentially infinitely long, neither the breadth-first nor depth-first would be sufficient to ensure progress on all programs. Instead, the following technique can be used: perform the first step of the first program; next, perform the first step of the second program and the second step of the first program; next, perform the first step of the third program, the second step of the second program, and the third step of the first program; and so on.
- Note: We could dovetail the depth-first (no dovetailing) and breadth-first (full dovetailing) mechanism of combining algorithms. This recursive application of the dovetailing algorithm to itself leads to an infinite number of new algorithms, each involving slightly less total dovetailing.
这也是证明集合是不是无限可数的一种技巧。如果一个无限集的序列能够用dovetailing来遍历，那么它就是无限可数的。
Elements of the Theory of Computation一书给出了两个结论：
1）有限个可数无限的集合的并集是可数的
2）无限个可数无限的集合的并集是可数的
对于1），我们可以把这个并集想象成一棵树：
然后进行广度优先搜索。dovetailing的形状就像一把锯子（这里就不放图了）
而2）就是材料中说的无限个程序有无限个步骤的情况。（其实1）也是材料中说的情况）