使用Spark查找路径成本

Question

我正在使用火花设计一个TSP解决方案。本质上，RDD中的每个元素都是一个三元组(id, x, y)，其中id是一个点的索引，x-y是那个点的坐标。如果一个RDD存储了一个三元组序列，我如何评估这个序列的路径开销？例如，序列(1，0，0)，(2，0，1)，(3，1，1)将给出成本1 + 1 = 2 (从第一点到第二点，然后到第三点)。为了做到这一点，我似乎必须知道火花如何准确地划分序列(RDD)。此外，如何评估两个分区的边界点之间的成本？还是有什么简单的手术让我这么做？

Answer 1

对于任何并行处理，您都希望认真考虑单个数据元素是什么，这样就只需要将需要在一起的数据放在一起。

因此，不是每一行都是点，很可能每一行都应该是定义路径的点数组，在这一点上，用Spark计算路径的总长度变得很容易。您只需使用通常使用的任何方法来计算给定定义点的线段数组的总长度。

但即便如此，我们还不清楚我们是否需要点的全局性。对于TSP，候选解决方案是一条包含所有位置的路径，这意味着我们不需要为每个解决方案存储城市的位置，也不需要每次计算距离。我们只需要计算一个距离矩阵，然后我们就可以广播它，这样每个星火工人都可以访问它，然后查找这些距离，而不是计算它们。

(它实际上是位置It的排列，而不仅仅是它们的列表，这可以简化更多的事情。)