这是一个学术问题，而不是实际问题。在旅行推销员问题中，或任何其他涉及找到最小优化的问题中……如果有人使用 map/reduce 方法，似乎有一些方法可以将当前最小结果广播给所有人计算节点以某种方式允许它们放弃超过该值的计算。
换句话说，如果我们将问题映射出来，我们希望每个节点在完成之前知道何时放弃给定的部分结果，但何时已经超过了其他解决方案。
立即想到的一种方法是，reducer 是否有办法向映射器提供反馈。考虑一下如果我们有 100 个节点，并且映射器向它们提供数百万条路径。如果 reducer 将最好的结果提供给 mapper，则该值可以作为参数与每个新路径(问题子集)一起包含在内。在这种方法中，粒度是相当粗糙的……这 100 个节点将每个节点都在他们的问题分区上不断打磨以完成，并且只有在映射器的下一个请求时才获得新的最小值。 (对于少量节点和大量问题分区/子集在此粒度上工作将是无关紧要的；也可能将启发式应用于将可能的路由或问题子集馈送到节点的序列以快速收敛到最优值，从而最大限度地减少节点执行的“浪费”计算量)。
想到的另一种方法是让节点主动订阅某种 channel ，或多播甚至广播，它们可以从中从计算循环中收集新的最小值。在这种情况下，他们可以在收到更好的解决方案(由他们的同行之一)通知时立即放弃错误的计算。
所以，我的问题是:
最佳答案
这是一个很酷的主题，没有那么多文献，之前已经完成了。所以这几乎是一个头脑 Storm 的帖子，而不是你所有问题的答案；)
所以每个 TSP 都可以表示为一个图表，看起来可能像这样:(取自德语维基百科)
现在您可以在其上运行图形算法。 MapReduce 可以很好地用于图形处理，尽管它有很多开销。
您需要一个称为“消息传递”的范例。本文在此处进行了描述:Paper .
我在博客中谈到了图形探索，它非常简单地讲述了它是如何工作的。 My Blogpost
这是告诉映射器当前最小结果是什么的方式(可能只针对顶点本身)。
考虑到所有知识，想到 branch and bound 应该是相当标准的。算法(你描述的)来达到目标。就像有一个随机的起始顶点并分支到每个相邻的顶点。这会导致向每个相邻节点发送一条消息，其代价是可以从起始顶点(映射步骤)到达。顶点本身仅在低于当前存储的成本时才更新其成本(减少步骤)。最初，这应该设置为无穷大。
您一遍又一遍地这样做，直到您再次到达起始顶点(显然在您访问了其他每个顶点之后)。因此，您必须以某种方式跟踪当前到达顶点的最佳方式，这也可以存储在顶点本身中。并且时不时地你必须绑定(bind)这个分支并切断成本太高的分支，这可以在阅读消息后在 reduce 步骤中完成。
基本上，这只是 MapReduce 中的图形算法和一种最短路径的混合。
请注意，这不会屈服于节点之间的最佳方式，它仍然是一个启发式的事情。而且您只是在使 NP-hard 问题并行化。
但是再做一点自我广告，也许你已经在我链接的博客文章中读过它，MapReduce 存在一个抽象，在这种图形处理中具有更少的开销。它被称为 BSP (Bulk synchonous parallel) .它在通信和计算模型上更加自由。所以我确信这可以用 BSP 比 MapReduce 更好地实现。您可以通过它更好地了解您所说的这些 channel 。
我目前参与了一个 Summer of Code 项目，该项目针对 BSP 的这些 SSSP 问题。也许你想visit if you're interested .这可能是部分解决方案，在我的博客中也有很好的描述。 SSSP's in my blog
我很高兴听到一些反馈；)
关于optimization - 旅行推销员和 map /减少 : Abandon Channel，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6114120/