Хорошо, как и было обещано простое решение:
Обозначения: Пусть d_{i,j}=d_{j,i} обозначает квадрат расстояние между точками i и j.Пусть N будет количеством очков.Пусть p_i обозначает точку i и p_{i,k} k -ю координату точки.
Будем надеяться, что теперь я выведу алгоритм корректно.После этого будут некоторые объяснения, чтобы вы могли проверить вывод (я ненавижу, когда появляется много индексов).
Алгоритм использует динамическое программирование для достижения правильного решения
Initialization:
p_{i,k} := 0 for all i and k
Calculation:
for i = 2 to N do
sum = 0
for j = 2 to i - 1 do
accu = d_{i,j} - d_{i,1} - p_{j,j-1}^2
for k = 1 to j-1 do
accu = accu + 2 p_{i,k}*p_{j,k} - p_{j,k}^2
done
p_{i,j} = accu / ( 2 p_{j,j-1} )
sum = sum + p_{i,j}^2
done
p_{i,i-1} = sqrt( d_{i,0} - sum )
done
Если яЯ не совершил серьезных ошибок в указателях (я обычно это делаю). Это должно сработать.
Идея, стоящая за этим:
Мы устанавливаем первую точку произвольно в начале координат, чтобы облегчить нашу жизнь.Не то чтобы для точки p_i мы никогда не устанавливали координату k, когда k > i-1.То есть для второй точки мы устанавливаем только первую координату, а для третьей - только первую и вторую координату и т. Д.
Теперь давайте предположим, что у нас есть координаты для всех точек p_ {k '}, где k'<i имы хотим вычислить координаты для p_{i}, чтобы все d_{i,k'} были выполнены (нас пока не волнуют какие-либо ограничения для точек с k>k').Если мы запишем систему уравнений, мы получим
d_{i,j} = \sum_{k=1}^N (p_{i,k} - p_{j,k} )^2
Поскольку p_{i,k} и p_{j,k} равны нулю для k>k', мы можем уменьшить это до:
d_{i,j} = \sum_{k=1}^k' (p_{i,k} - p_{j,k} )^2
Также обратите внимание, что по инварианту цикла все p_{j,k} будут равны нулю при k>j-1.Итак, мы разделим это уравнение:
d_{i,j} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k} )^2 + \sum_{k=j}^{k'} p_{i,j}^2
Для первого уравнения мы просто получим:
d_{i,1} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k} )^2 + \sum_{k=j}^{k'} p_i{i,1}^2
Для этого потребуется специальноеобработка позже.
Теперь, если мы решим все биномы в нормальном уравнении, мы получим:
d_{i,j} = \sum_{k=1}^{j-1} p_{i,k}^2 - 2 p_{i,k} p_{j,k} + p_{j,k}^2 + \sum_{k=j}^{k'} p_{i,j}^2
вычтем первое уравнение из этого и у вас останется:
d_{i,j} - d_{i,1} = \sum_{k=1}^{j-1} p_{j,k}^2 - 2 p_{i,k} p_{j,k}
для всех j> 1.
Если вы посмотрите на это, вы заметите, что все квадраты координат p_i пропали и единственные квадраты нам нужныуже известны.Это набор линейных уравнений, которые могут быть легко решены с использованием методов из линейной алгебры.На самом деле есть еще одна особенность этого набора уравнений: уравнения уже имеют треугольную форму, поэтому вам нужен только последний шаг распространения решений.На последнем этапе нам остается одно квадратное уравнение, которое мы можем просто решить, взяв один квадратный корень.
Я надеюсь, что вы можете следовать моим рассуждениям.Уже немного поздно, и моя голова немного кружится от этих индексов.
EDIT : Да, были ошибки индексации.Исправлена.Я попытаюсь реализовать это в python, когда у меня будет время, чтобы проверить это.