Как создать цепочку из пар в R - PullRequest
Новая
       16

Как создать цепочку из пар в R

0 голосов
/ 23 апреля 2019

редактировать: добавлено текущее решение

Я балуюсь проблемой коммивояжера и использую решатель для расчета наиболее оптимального тура. Выходные данные моего линейного решателя дают мне таблицу с арками в маршруте, однако для построения маршрута мне нужен вектор со всеми расположениями, расположенными в правильном порядке. Есть ли элегантный способ объединить эти арки в один тур?

Одним из решений будет серия (вложенных) соединений / совпадений, однако, на мой взгляд, это не элегантное решение. 

# output of solver (where i = 'from' and j = 'to')
solution = data.frame(i = c(6, 4, 10, 7, 1, 9, 3, 2, 8, 5),
                j = c(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))

# transformation
??

# required output
tour = c(6, 1, 5, 10, 3, 7, 4, 2, 8, 9)

Таким образом, выходной файл, который я ищу, представляет собой одну цепочку связанных арок (от i до j) в туре.

Мое текущее решение использует циклы и совпадения и выглядит следующим образом: 

# number of cities to visit
nCities = length(solution)

# empty matrix
tour = matrix(0, nCities, 2)

#first location to visit picked manually
tour[1, ] = solution[1, ]

# for loop to find index of next arch in tour
for(k in 2:nCities){
  ind = match(tour[k - 1, 2], solution[, 1])         
  tour[k, ] = solution[ind, ]
}
# output 'tour' is the solution but then sorted.

# I then take only the first column which is the tour
tour = tour[1, ]

Однако, это выглядит неуклюже, и, поскольку я стараюсь избегать циклов как можно больше, я не доволен этим. Кроме того, я подозреваю, что существуют более элегантные решения, предпочтительно с использованием базовых функций R.

...