旅行推销员和地图/减少:放弃频道

Question

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

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

如果减速器具有向映射器提供反馈的方法,那么立即想到的一种方法是.考虑一下我们是否有100个节点,映射器为它们提供了数百万条路径.如果reducer将最佳结果提供给mapper,那么该值可以作为参数与每个新路径(问题子集)一起包含.在这种方法中,粒度相当粗糙...... 100个节点将在问题的分区上逐渐磨损完成,并且只有来自映射器的下一个请求才能获得新的最小值.(对于少量节点和大量问题分区/子集来说,这种粒度是无关紧要的;也可能是人们可以将启发式方法应用于可能的路由或问题子集被馈送到节点的序列中获得朝向最优的快速收敛,从而最小化节点执行的"浪费"计算量.

想到的另一种方法是节点主动订阅某种频道,或多播甚至广播,从中可以从计算循环中收集新的最小值.在这种情况下,当被通知更好的解决方案时(他们的同行之一),他们可以立即放弃糟糕的计算.

所以,我的问题是:

• 这个概念是否涵盖了与现有地图/减少讨论相关的任何艺术术语
• 当前的map/reduce框架是否提供支持此类动态反馈的功能？
• 这个想法有一些缺陷......为什么它是愚蠢的一些原因？

Answer 1

这是一个很酷的主题，没有那么多文献，以前就已经完成了。所以这几乎是一个集思广益的帖子，而不是所有问题的答案；）

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

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

通过这种方式，您可以告诉映射器当前的最小结果是什么（可能仅适用于顶点本身）。

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

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

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

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