分布式树搜索

分布式树搜索（DTS）算法是一类以高效和分布式方式搜索数值的算法。它们的目的是通过沿多个分支并行工作来迭代一棵树，并将每个分支的结果合并成一个共同的解决方案，以尽量减少在树状数据结构中搜索一个值所花费的时间。最初的论文是由加利福尼亚大学计算机科学系的克里斯-弗格森和理查德-E-科夫在1988年写的。他们使用了其他多个国际象棋人工智能来开发这种范围更广的算法。

分布式树搜索算法（也称为Korf-Ferguson算法）是为了解决以下问题而创建的：给定一棵具有非统一分支因子和深度的树，用任意数量的处理器尽可能快地并行搜索它。该算法的顶层部分是通用的，并不使用特定的现有类型的树搜索，但它可以很容易地被专门化以适应任何类型的非分布式树搜索。DTS包括使用多个进程，每个进程有一个节点和一组附加的处理器，目标是搜索所述节点下面的子树。然后每个进程将自己分成多个协调的子进程，这些子进程再次递归划分，直到根据每个进程可用的处理器数量找到搜索树的最佳方式。一旦一个进程完成，DTS动态地将处理器重新分配给其他进程，以便通过良好的负载平衡保持xxx的效率，特别是在不规则的树上。一旦一个进程完成了搜索，它就会递归地向其父进程发送和合并一个结果信号，直到所有不同的子答案都被合并，整个问题都被解决。DTS的应用只有在两个主要条件下才适用：要搜索的数据结构是一棵树，而且算法可以利用至少一个计算单元（尽管如果只有一个计算单元，就不能被认为是分布式）。日常使用DTS的一个主要例子是网络路由。

互联网可以被看作是一棵由IP地址组成的树，对路由协议的比喻可以是现实世界中邮局的工作方式。由于目前有超过43亿个IP地址，社会在很大程度上取决于数据找到其目的地的时间。因此，IP路由将工作分为多个子单元，每个子单元都有不同规模的计算能力，并利用彼此的结果，以非常有效的方式找到路线。

虽然DTS是目前使用最广泛的算法之一，但它的许多应用都有替代品，如果对它们进行更多的研究，就有可能发展成更有效、对资源需求更少的解决方案。其中一个比较有争议的例子是大数据处理。在像谷歌搜索引擎、Facebook、YouTube这样的应用中，需要对搜索进行优化，以使等待时间保持在一个合理的窗口内。这可以通过单纯使用DTS来实现，但其他算法也被用来代替（例如SQL数据库中的数据哈希），或者结合使用（Facebook的Haystack算法将平行树形搜索、数据哈希和内存排序/排序分组）。DTS的一个更重要的限制是，它需要一棵树作为输入。树是被称为图的数据结构的一个子实例，这意味着每一个图都可以被转换为树。尽管目前不存在比Korf-Ferguson算法更好的搜索树的方法，但每个任务都有不同的特殊性，在大多数情况下，存在比通过树搜索更有效的数据结构来表示和解决这个问题。因此，存在着有周期的树状结构的实例，不可能比具有相同处理能力的相同结构上的图搜索快。

这开启了一个新的观点：是否有太多的资源被用于完成DTS，从而阻碍了具有更高效率潜力的新算法的研究和开发？