(0) 阅读 (1098)

分布式树搜索 编辑

词条创建者 匿名用户

分布式树搜索

编辑

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

分布式树搜索的概述

编辑

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

分布式树搜索

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

替代品

编辑

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

分布式树搜索的争议

编辑

围绕着Korf-Ferguson的DTS算法几乎没有争议,因为它被公认为是非常完整的,但也是简单的。它经常被用作学生发现分布式问题解决的基本原理和关键概念的踏脚石。对这一算法概念最重要的挑战是KröllB的一篇文章,"平衡的分布式搜索树不存在",这篇文章并没有攻击算法的真实性或当前的效率,而是指出DTS本身,无论对它做多少改进(例如事先平衡输入树),都无法达到最佳解决时间。这开启了一个新的观点:是否有太多的资源被用于完成DTS,从而阻碍了具有更高效率潜力的新算法的研究和开发?DTS的另一个限制是


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163439/

发表评论

登录后才能评论

词条目录
  1. 分布式树搜索
  2. 分布式树搜索的概述
  3. 替代品
  4. 分布式树搜索的争议

轻触这里

关闭目录

目录