Използвам 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). Освен това как мога да оценя цената между граничните точки на два дяла? Или има някаква проста операция, за да направя това?
Използвайте Spark RDD, за да намерите цената на пътя
Отговори (1)
При всяка паралелна обработка искате да обмислите сериозно какво представлява един елемент от данни, така че само данните, които трябва да бъдат заедно, да бъдат заедно.
Така че вместо всеки ред да е точка, вероятно всеки ред трябва да бъде масив от точки, които определят път, в който момент изчисляването на общата дължина на пътя със Spark става лесно. Просто бихте използвали всичко, което обикновено използвате, за да изчислите общата дължина на масив от линейни сегменти, дадени на определящите точки.
Но дори и тогава не е ясно дали се нуждаем от пълната общност на точките. За TSP кандидат решение е път, който включва всички местоположения, което означава, че не е необходимо да съхраняваме местоположенията на градовете за всяко решение или да изчисляваме разстоянията всеки път. Просто трябва да изчислим една матрица от разстояния, която след това можем да излъчим, така че всеки работник на Spark да има достъп до нея, и след това да търсим разстоянията, вместо да ги изчисляваме.
(Това всъщност е пермутация на идентификатори на местоположение, а не просто списък от тях, което може да опрости нещата още повече.)
person
Matthew Graves
schedule
24.11.2015
