旅行推销员和地图/减少：放弃渠道

那是一个很酷的主题，没有那么多文献，之前已经做过。因此，这几乎是一个集思广益的帖子，而不是您所有问题的答案;） 因此，每个TSP都可以表示为一张图，看起来可能像这样：（取自德国维基百科） 现在，您可以在其上运行图算法。尽管MapReduce有很多开销，但可以很好地用于图形处理。 您需要一个称为“消息传递”的范例。本文对此进行了描述：纸。 我在图探索方面就此发表了博客，它非常简单地讲述了它的工作原理。我的网志文章 这样可以告诉映射器当前的最小结果是什么（也许只是针对顶点本身）。 有了所有知识后，想到达到目标的分支定界算法（您所描述的）应该是相当标准的。就像拥有一个随机的起始顶点并分支到每个相邻的顶点一样。这导致一条消息被发送到每个相邻节点，其代价是可以从起始顶点到达（映射步骤）。顶点本身仅在其成本低于当前存储的成本时才更新其成本（“减少步骤”）。最初，应将其设置为无穷大。 您需要一遍又一遍地执行此操作，直到再次到达起始顶点为止（很明显，在您访问其他所有顶点之后）。因此，您必须以某种方式跟踪到达顶点的当前最佳方法，该方法也可以存储在顶点本身中。而且，您不时需要绑定此分支，并切断过于昂贵的分支，可以在阅读消息后的reduce步骤中完成此操作。 基本上，这只是MapReduce中的图形算法和最短路径的混合。 请注意，这不会达到节点之间的最佳方式，这仍然是一个启发式的事情。而且，您只是使NP难题成为现实。 但是又要进行一点自我广告，也许您已经在我链接的博客文章中阅读了它，对MapReduce有了一个抽象，在这种图形处理中开销较小。它称为BSP（批量同步并行）。它在通信和计算模型中更加自由。因此，我敢肯定，使用BSP可以比MapReduce更好地实现这一点。您可以用它更好地实现这些渠道。 我目前正在参与“代码之夏”项目，该项目针对BSP的这些SSSP问题。如果您有兴趣，也许想参观。这可能是部分解决方案，我的博客也对此进行了很好的描述。 SSSP在我的博客中 我很高兴听到一些反馈;）     

看来Storm实现了我的想法。它本质上是一种计算拓扑（考虑每个计算节点如何基于键/哈希函数将结果路由到特定的reducer）。 这并不是我所描述的确切内容，但是如果它具有足够低的延迟方式来传播当前边界（即局部最优信息），拓扑中的每个节点都可以更新/接收该边界以得知要丢弃的结果，则可能有用。