Алгоритм оптимизации расстояния между точками в N-мерном пространстве
Здраствуйте.
Мне нужно оптимизировать расстояние между точками, но нельзя изменять некоторые точки.
Пример(3D):
X : входные данные
X[1] = 0.25, 0.8, 0.4 - const
X[2] = 0.11, 0.5, 0.3 - const
X[3] = 0.43, 0.3, 0.1 - mutable(генерируем рандомно 0...1)
X[4] = 0.11, 0.4, 0.2 - mutable(генерируем рандомно 0...1)
X[5] = 0.23, 0.3, 0.3 - mutable(генерируем рандомно 0...1)
dm : Матрица расстояний
0 0.345832 0.393372 0.172916 0.393775
0.345832 0 0.393775 0.172916 0.393372
0.393372 0.393775 0 0.353553 0.707107
0.172916 0.172916 0.353553 0 0.353553
0.393775 0.393372 0.707107 0.353553 0
X : результат
X[1] = 0.25, 0.8, 0.4 - const
X[2] = 0.11, 0.5, 0.3 - const
X[3] = 0.??, 0.?, 0.? - mutable
X[4] = 0.??, 0.?, 0.? - mutable
X[5] = 0.??, 0.?, 0.? - mutable
Получается точки X[1] и X[2] уже на своем месте, расстояние между ними равно значению в матрице расстояний, их нельзя изменять. Нужно только изменить {x, y, z} в X[3], X[4], X[5]. Возможно существует алгоритм с помощью которого можно решить данную проблему?
Количество точек ~200
Размерность пространства >= 3D
Ответы (2 шт):
Другими словами, ваша задача формулируется так:
В пространстве размерности D заданы точки X_1, X_2, ..., X_m, задана симметричная матрица L размером NxN, где N > m. Нужно подобрать точки X_{m+1}, ..., X_N так, чтобы соответствующая им матрица расстояний M минимально отличалась от L: |M - L| = min.
Я не буду спрашивать, какую меру в пространстве матриц вы собираетесь использовать для определения расстояния между матрицами, это для решения непринципиально.
Принципиальна размерность задачи. 200 точек - это 200D параметров. Даже если зафиксированы 100 точек, нахождение остальных равноценно решению оптимизационной задачи в пространстве размерностью 100N.
Подозреваю, что никакой из прикладных пакетов не сможет решить задачу такой размерности, так как в процессе будут возникать якобианы размером (100N)x(100N). Поэтому я бы решал так:
- Уменьшаем размерность задачи со 100 неизвестных точек до 1. Т.е. берём 100 точек и ищем одну точку, которая даст оптимальную матрицу размером 101 на 101. В качестве метода решения можно взять Монте-Карло, или же решать численно задачу поиска экстремума для функции с D переменными.
- Зафиксировав 101 точку, ищем 102-ю точку.
- Зафиксировав 102 точки, ищем 103-ю точку. ...
- Зафиксировав 199 точек, ищем 200 точку.
Стопудов это будет неоптимальное решение. Можно взять его за начальное значение и попробовать уточнить градиентным спуском. В результате вы получите какой-то минимум.
Чутье мне подсказывает, что у этой задачи будет море локальных минимумов, и с практической точки зрения задача поиска глобального минимума будет неразрешима.
Если зафиксированы хотя бы четыре точки (пример для 3D) не в одной плоскости, то координаты остальных восстанавливаются с помощью триангуляции (точно).
Если четырёх точек нет, то однозначного ответа быть не может. К фиксированным точкам надо добавить недостающие до четырёх (несложная задача, координаты дополнительных точек придумываются точно). Если четвёрка оказалась примерно в одной плоскости, то надо выбрать другие дополнительные точки. Отныне считаем всю четверку зафиксированной. Затем триангуляция выше.
После триангуляции запускаем оптимизацию попарных расстояний с помощью МНК. Так как у нас хорошая стартовая точка, МНК должен сойтись быстро.