алгоритм выбора весов таким образом, чтобы средние позиции приближались к целевым позициям

У меня есть система с небольшим количеством частиц (4-10) в фиксированных местах в пространстве. Затем у меня есть одно целевое местоположение. Я хотел бы присвоить веса каждой частице, чтобы средневзвешенное расположение частиц было как можно ближе к цели. Веса должны быть назначены последовательно в тех случаях, когда возможны несколько решений. Например, если у меня есть 3 частицы в точках [1,0,0], а также в точках [-1,0,0] и [0,0,0], а моя цель — [0,0,0], возможны три решения, которые будут весами 0,333,0,333,0,333 или 0,0,1 или 0,5,0,5,0. Второй вариант кажется наиболее интуитивным, но на самом деле не имеет значения, какое решение будет выбрано, главное, чтобы оно выбиралось последовательно. Также меня в основном интересуют случаи, когда точное решение невозможно, но выбранные веса минимизируют ошибку. Каков наиболее эффективный алгоритм для вычисления этих весов?

РЕДАКТИРОВАТЬ: чтобы сделать это более понятным, я создал визуализацию 2-го случая. В этом примере имеется 5 фиксированных положений и 1 целевое положение. В настоящее время я использую неуклюжий наивный подход, начиная со среднего значения всех 5 (веса = 0,2,0,2,0,2,0,2,0,2), а затем итеративно корректируя эти веса и наблюдая, помогает ли это решению, постепенно приближаясь к цели. Это может занять сотни шагов. Мне нужно обработать это на миллионах или даже миллиардах целевых позиций, поэтому я ищу более прямой аналитический подход к решению. введите здесь описание изображения


person billTavis    schedule 25.04.2020    source источник
comment
Может быть, я не совсем понял задачу, но мне кажется, что это набор линейных уравнений, которые нужно решить.   -  person Henry    schedule 25.07.2020
comment
@ Генри, да, это цель - получить решение с точки зрения уравнений, чтобы я мог быстро и точно найти ответ. Но я не знаю, как сформулировать это в терминах разрешимых уравнений. Любые поисковые идеи будут высоко оценены. Я искал наименьшие квадраты, но все, что я могу найти, это линейная регрессия, которая, кажется, не одно и то же, потому что для этого каждый член имеет свою собственную ошибку, но в этом случае есть только одно значение ошибки для общего среднего.   -  person billTavis    schedule 27.07.2020


Ответы (1)


Для задачи можно составить простые линейные уравнения (показывая трехмерный случай):

sum(xi * wi) = xt
sum(yi * wi) = yt
sum(zi * wi) = zt

Вы не упомянули об этом, но, похоже, есть также ограничение, что сумма весов равна 1. В этом случае просто добавьте еще одно уравнение:

sum(wi) = 1

Если есть N точек, теперь у нас есть система из 3 (или 4) уравнений с N неизвестными (wi). Как решить такую ​​систему, хорошо известно из линейной алгебры. Решений может быть 0, 1 или бесконечно много.

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

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

person Henry    schedule 27.07.2020
comment
спасибо за подробный ответ. После некоторых исследований кажется, что я могу выразить это в терминах Ax = b, где A — матрица 3xN с позициями точек, b — целевая позиция, а x — веса, для которых нужно решить. Поскольку A не квадрат, я могу решить его с помощью x = (A.TA)^-1 * A.Tb правильно? Для N = 10 потребуются сотни вычислений для каждой целевой позиции, поэтому, хотя это дало бы мне прямое аналитическое решение, я не уверен, насколько эффективно это было бы на практике... может быть, вы на что-то с выпуклой оболочкой , и геометрический подход был бы лучше - person billTavis; 27.07.2020
comment
Вместо вычисления инверсий просто выполните исключение Гаусса, чтобы привести матрицу к ступенчатой ​​форме. Также обратите внимание, что вам нужно сделать это только один раз, когда вы решаете одну и ту же систему для разных правых частей. Однородный раствор также один и тот же и должен быть рассчитан только один раз. Так что не думаю, что расчеты затянутся надолго. - person Henry; 28.07.2020
comment
еще раз спасибо. Я не знаком с этим методом, но, глядя на Википедию, кажется, что правая сторона меняется с каждым шагом, поэтому я не уверен, что вы имеете в виду, говоря, что мне нужно сделать это только один раз. en.wikipedia.org/wiki/Gaussian_elimination Вы предлагаете мне отслеживать операции, которые происходят на значения правой руки? А затем, чтобы решить с новым набором правых значений, я применяю эти сохраненные операции, а затем использую обратную замену с уже измененной матрицей? Как проявляется однородный раствор? - person billTavis; 29.07.2020
comment
Да первой части. Шаги исключения необходимо повторить для новой правой стороны. Однородное решение полезно в случае, когда существует бесконечно много решений. Вы получаете их все, добавляя один специальный раствор ко всем гомогенным растворам. - person Henry; 29.07.2020