Р: Как наиболее эффективно сделать расчет длины границы ячейки между разными "владельцами"?
Я занимаюсь пространственной оптимизацией. У меня ~20 000 ячеек, у "хозяев" которых есть шанс на оптимальную ситуацию Клетки различаются по размеру и форме. Задача, которую мне нужно сделать, - это рассчитать длину линии между владельцами в местном районе. (Это единственный вариант определения нового владельца ячейки.)
У меня есть три матрицы. Номер один имеет столбцы, которые представляют: Line_id, Left_cell_neighbour, right_cell_neighbour, length_of_line. Линия является одной из пограничных линий ячейки. Между двумя ячейками может быть больше, чем просто одна строка.
Line_ID LEFT_ID RIGHT_ID Lenght
[1,] 1 5 1 31.648135
[2,] 2 15 2 38.229177
[3,] 3 9 65 2.707813
[4,] 4 5 4 2.139000
[5,] 5 1 1279 1.660400
[6,] 6 6 1 25.000000
Номер два имеет столбцы, которые представляют: Cell_id, Neightbour_cell_1_id, Neighbour_cell_2_id.. и так далее. Количество соседей варьируется между ячейками, но все они имеют менее 10 соседних ячеек. -1 только для заполнения пустого пространства. Я могу дать шанс NA, если это поможет.
Cell_Id N_1_Id N_2_Id N_3_Id N_4_Id N_5_Id N_6_Id N_7_Id N_8_Id
[1,] 1 31 6 2 -1 -1 -1 -1 -1
[2,] 2 1 67 7 3 -1 -1 -1 -1
[3,] 3 2 43 8 4 7 6 -1 -1
[4,] 4 3 9 75 -1 -1 -1 -1 -1
[5,] 5 44 11 6 -1 -1 -1 -1 -1
Номер три имеет столбцы, которые представляют: Cell_id, Владелец и переменные.
Cell_Id Owner Variable_1 Variable_2 Variable_3
[1,] 1 22 1.77579 565 399
[2,] 2 22 284.08909 427 228
[3,] 3 22 367.90390 464 269
[4,] 4 22 0.01670 231 67
[5,] 5 22 33.89463 241 73
[6,] 6 22 422.15516 620 481
Мне нужно рассчитать длину линии между соседями разных владельцев примерно в половине итераций. Количество итераций, вероятно, будет огромным, поэтому вычисления должны быть быстрыми.
Один пример показан на картинке в этом сообщении. Владельцем ячейки, помеченной вопросительным знаком, будет тот, у которого уже есть большая часть общей границы с ячейкой. Разные владельцы показаны в разных цветах. Вы можете видеть, что владелец этой ячейки будет таким же, как владелец ячеек 3 и 5.
Линии, длина которых должна быть рассчитана, отмечены красным. У соседа (в этой ситуации) есть 4 разных владельца, один для ячейки 1, один для ячейки 4, один для ячейки 2 и один для ячеек 3 и 5.
Тогда я смогу получить матрицу с длинами в столбцах: Owner, lenght_of_borderline. Затем я выбираю владельца, соответствующего max(lenght_of_borderline), чтобы быть новым владельцем.
Но как рассчитать это эффективно? Другие предложения для эффективных структур или так далее для этой задачи приветствуются.
Спасибо за вашу помощь!
Ссылка на изображение (надеюсь, это работает) http://imageshack.us/photo/my-images/641/situationn.png/
Обновление: примеры матриц.
1 ответ
Вы должны быть в состоянии использовать моделируемый отжиг для эффективного решения этой проблемы.
http://en.wikipedia.org/wiki/Simulated_annealing
Вот видео другого примера.
http://www.youtube.com/watch?v=-cr6wbZOqOU
Научная библиотека GNU имеет набор инструментов для этого.
http://www.gnu.org/software/gsl/manual/html_node/Traveling-Salesman-Problem.html
Есть привязки для R доступны.