5

这是一个学术问题而不是实际问题。在旅行推销员问题中，或任何其他涉及找到最小优化的问题中……如果有人使用 map/reduce 方法，似乎有一些方法可以将当前最小结果广播给所有人计算节点以某种方式允许它们放弃超过该值的计算。

换句话说，如果我们将问题映射出来，我们希望每个节点在完成之前知道何时放弃给定的部分结果，但何时已经超过了其他解决方案。

立即想到的一种方法是，reducer 是否有办法向映射器提供反馈。考虑一下我们是否有 100 个节点，并且映射器向它们提供数百万条路径。如果 reducer 将最好的结果提供给 mapper，则该值可以作为参数包含在每个新路径（问题子集）中。在这种方法中，粒度相当粗略……这 100 个节点将每个节点都在他们的问题分区上不断打磨以完成，并且只有在映射器的下一个请求时才获得新的最小值。（对于少量节点和大量问题分区/子集在此粒度上工作将是无关紧要的；而且它

想到的另一种方法是让节点主动订阅某种频道，或多播甚至广播，它们可以从它们的计算循环中收集新的最小值。在这种情况下，他们可以在收到更好的解决方案（由他们的同行之一）通知时立即放弃错误的计算。

所以，我的问题是：

  • 与现有 map/reduce 讨论相关的任何艺术术语是否涵盖此概念
  • 当前的 map/reduce 框架是否提供了支持这种动态反馈的功能？
  • 这个想法有什么缺陷……为什么它很愚蠢？
4

2 回答 2

3

这是一个很酷的主题，没有那么多文献，之前已经完成了。所以这几乎是一个头脑风暴的帖子，而不是你所有问题的答案；）

所以每个 TSP 都可以表示为一个图表，看起来可能像这样：（取自德语维基百科）

TSP 图

现在您可以在其上运行图形算法。MapReduce 可以很好地用于图形处理，尽管它有很多开销。
您需要一个称为“消息传递”的范例。本文在此处进行了描述：Paper。
我在博客中谈到了图形探索，它非常简单地讲述了它是如何工作的。我的博文

这是您告诉映射器当前最小结果是什么的方式（可能仅针对顶点本身）。

有了脑海中的所有知识，考虑使用分支定界算法（您所描述的）来达到目标​​应该是非常标准的。就像有一个随机的起始顶点并分支到每个相邻的顶点。这会导致向每个相邻节点发送一条消息，其代价是可以从起始顶点（映射步骤）到达。顶点本身仅在低于当前存储的成本时才更新其成本（减少步骤）。最初，这应该设置为无穷大。
你一遍又一遍地这样做，直到你再次到达起始顶点（显然在你访问了其他每个顶点之后）。因此，您必须以某种方式跟踪当前到达顶点的最佳方式，这也可以存储在顶点本身中。并且时不时地你必须绑定这个分支并切断成本太高的分支，这可以在阅读消息后在 reduce 步骤中完成。基本上，这只是 MapReduce 中的图形算法和一种最短路径的混合。
请注意，这不会屈服于节点之间的最佳方式，它仍然是一个启发式的事情。而且您只是在使 NP-hard 问题并行化。

但是再做一点自我广告，也许你已经在我链接的博客文章中读过它，MapReduce 存在一个抽象，在这种图形处理中开销更少。它被称为BSP（批量同步并行）。它在通信和计算模型上更加自由。所以我确信这可以用 BSP 比 MapReduce 更好地实现。您可以通过它更好地了解您所说的这些渠道。

我目前参与了一个 Summer of Code 项目，该项目针对 BSP 的这些 SSSP 问题。如果你有兴趣，也许你想去看看。这可能是部分解决方案，在我的博客中也有很好的描述。SSSP 在我的博客中

我很高兴听到一些反馈；）

于 2011-05-24T17:59:23.950 回答
1

似乎Storm实现了我的想法。它本质上是一种计算拓扑（想想每个计算节点可能如何基于键/散列函数将结果路由到特定的减速器）。

这并不完全是我所描述的，但如果一个人有足够低的延迟方式来传播拓扑中的每个节点可以更新/接收的当前边界（即局部最优信息），以便知道要丢弃哪些结果，这可能会很有用。

于 2012-06-05T21:44:44.997 回答