Используйте Spark RDD, чтобы найти стоимость пути

Question

Я использую Spark для разработки решения TSP. По существу, каждый элемент в RDD представляет собой 3-кортеж (id, x, y), где id является индексом точки, а x-y является координатой этой точки. Если RDD хранит последовательность из 3-х кортежей, как я могу оценить стоимость пути этой последовательности? Например, последовательность (1, 0, 0), (2, 0, 1), (3, 1, 1) даст стоимость 1 + 1 = 2 (от первой точки ко второй точке, а затем до третьей точки). Кажется, для этого я должен знать, как именно Spark разделяет последовательность (RDD). Кроме того, как я могу оценить стоимость между граничными точками двух разделов? Или для меня есть простая операция?

Answer 1

С любой параллельной обработкой вы хотите серьезно подумать о том, что представляет собой один элемент данных, так что только данные, которые должны быть вместе, вместе.

Таким образом, вместо того, чтобы каждая строка была точкой, вполне вероятно, что каждая строка должна быть массивом точек, определяющих путь, при котором точка, вычисляющая полную длину пути с помощью Spark, становится легкой. Вы просто используете то, что обычно используете для вычисления общей длины массива сегментов линии с учетом определяющих точек.

Но даже тогда не ясно, что нам нужна полная общность точек. Для TSP решение кандидата - это путь, который включает все местоположения, что означает, что нам не нужно хранить местоположения городов для каждого решения или каждый раз рассчитывать расстояния. Нам просто нужно вычислить одну матрицу расстояний, которую мы можем транслировать так, чтобы каждый рабочий из Spark имел к ней доступ, а затем просматривал расстояния, а не вычислял их.

(На самом деле это перестановка идентификаторов местоположения, а не просто список из них, что может упростить еще больше.)