Я использую Spark для разработки решателя TSP. По сути, каждый элемент в RDD представляет собой тройку (id, x, y), где id — индекс точки, а x-y — координата этой точки. Учитывая RDD, хранящий последовательность из 3-х кортежей, как я могу оценить стоимость пути этой последовательности? Например, последовательность (1, 0, 0), (2, 0, 1), (3, 1, 1) даст стоимость 1 + 1 = 2 (из первой точки во вторую и затем в третью). Кажется, для этого мне нужно знать, как именно Spark разделяет последовательность (RDD). Кроме того, как я могу оценить стоимость между граничными точками двух разделов? Или есть какая-то простая операция для меня, чтобы сделать это?
Используйте Spark RDD для определения стоимости пути
Ответы (1)
При любой параллельной обработке необходимо серьезно подумать о том, что представляет собой отдельный элемент данных, чтобы вместе находились только те данные, которые должны быть объединены.
Таким образом, вместо того, чтобы каждая строка была точкой, вполне вероятно, что каждая строка должна быть массивом точек, определяющих путь, после чего вычисление общей длины пути с помощью Spark становится простым. Вы бы просто использовали то, что обычно используете для вычисления общей длины массива отрезков с заданными определяющими точками.
Но и тогда не ясно, нужна ли нам полная общность точек. Для TSP решение-кандидат — это путь, который включает все местоположения, а это означает, что нам не нужно хранить местоположения городов для каждого решения или каждый раз вычислять расстояния. Нам просто нужно рассчитать одну матрицу расстояний, которую мы затем можем транслировать, чтобы каждый работник Spark имел к ней доступ, а затем искать расстояния вместо их вычисления.
(На самом деле это перестановка идентификаторов местоположения, а не просто их список, что может еще больше упростить задачу.)
person
Matthew Graves
schedule
24.11.2015
