分布式树搜索

创建分布式树搜索算法（也称为Korf-Ferguson算法）是为了解决以下问题：给定一个具有非均匀分支节点和深度的树，用任意数量的处理器尽可能快地进行并行搜索。

此算法的最高级别是通用的，不使用特定的现有树搜索类型，但是这一算法很容易专门化，以适应任何类型的非分布式树搜索。

DTS由多个进程组成，每个进程都有一个节点和一组附加的处理器，其目标是搜索所述节点下的子树。然后，每个进程将自己划分为多个协调的子进程，这些子进程再次对自己递归划分，直到基于每个进程可用的处理器的数量找到搜索树的最佳方式。一旦进程完成，DTS就会动态地将处理器重新分配给其他进程，以便通过良好的负载平衡保证效率最大化，尤其是在不规则树中。

一旦一个进程完成搜索，它就会递归地向其父进程发送并合并一个结果信号，直到所有不同的子答案都被合并并且整个问题都得到解决。^[1]

DTS只适用于以下两种主要情况:一、要搜索的数据结构是树，二、算法可以使用至少一个计算单元(如果只有一个计算单元，则不能认为是分布式的)。

网络路由是DTS在日常运用中的典型例子。互联网可以看作是一个IP（网络协议）地址树，路由协议的工作方式与现实中邮局的工作方式相似。由于目前有超过43亿个IP地址，社会运作在很大程度上取决于数据到达目的地的时间。因此，IP路由将工作划分为多个子单元，每个子单元具有不同规模的计算能力，且各单元通过使用彼此的结果以高效的方式找到路由。这是DTS日常运用的一个例子，影响了全世界43％以上的人口，影响范围从娱乐到国家安全。^[2]

虽然DTS是目前使用最广泛的算法之一，但它的许多应用程序都有替代算法，如果对这些算法进行更多的研究，它们可能会发展成效率更高、资源需求更低的解决方案。

其中一个比较有争议的例子是大数据处理。在谷歌搜索引擎（Google）、脸书(Facebook)、优兔(YouTube)等应用程序中，搜索需要进行优化，使等待时间保持在一个合理的窗口内。这可以通过使用DTS来实现，但也可以使用其他算法（例如SQL数据库中的数据散列），或者结合使用不同算法（脸书的Haystack算法组并行树搜索，数据散列和内存排序/排序）。^[3]

DTS的一个更重要的限制是，它需要一个树作为输入。树是称为图的数据结构的子实例，这意味着每个图都可以转换成树。尽管目前没有比Korf-Ferguson算法更好的树搜索方法，但每个任务自身情况不同，在大多数情况下，存在比树搜索更有效的数据结构来表示和解决问题。因此存在具有循环的树结构的实例，但在相同处理能力的相同结构上的图搜索更快。

关于Korf-Ferguson's的DTS算法几乎没有争议，因为这一算法体系完整但操作简单。它经常被用作学生发现分布式问题解决的基本原理和关键概念的入门工具。

对这一算法概念提出的最大质疑的是Kröll B一篇名为《平衡的分布式搜索树并不存在》的文章，它没有攻击算法的准确性或当前效率，而是针对DTS这一算法本身，即无论对它进行了多少改进（例如预先平衡输入树），也永远无法达到最佳分辨率时间。^[4]这就提出了一个新的观点:完成DTS时是否占用了太多的资源，从而阻碍了更高效率和更有潜力的新算法的研究和开发?DTS的另一个限制是，无论解决方案的划分、协调和合并多么有效，它总是受到材料数量或处理器及其处理能力的限制。几乎所有算法都会受到这一限制，这种观点最近才被认可。但是，像欧几里得（Euclideon）这样的新一代算法可能有一天能够通过独立于处理能力的问题解决方案来降低深度优先搜索（DFS）的效率。