Нахождение точки, которая наилучшим образом соответствует пересечению n сфер
У меня есть массив точек с расстояниями. Я хочу найти точку, которая наилучшим образом удовлетворяет условию
for (point_i, distance_i) in pointArray:
abs(point - point_i) = distance_i
Я думаю, что это можно решить с помощью некоторой регрессии или метода наименьших квадратов, но у меня проблемы с постановкой задачи.
Если кто-нибудь может помочь, это будет очень ценно
2 ответа
Вы должны определить "лучший", чтобы иметь ответ на вопрос.
То, что вы, вероятно, хотите сделать, это определить какую-то функцию ошибки для определения того, насколько важно отклонение от заданной точки, а затем попытаться минимизировать сумму ошибок. Используемая функция ошибок зависит от вашей реальной проблемы. Например, возможно, вы хотите использовать (длина (точка - точка_i) - расстояние)2. Это было бы наименьших квадратов. Но, возможно, вас не волнует абсолютная величина расстояния, просто соотношение между тем, как далеко они находятся, и как далеко вы их ожидаете. Таким образом, вы можете использовать (длина (точка - точка_i)/ расстояние - 1)2. Возможно, вы получаете точки и расстояния от группы датчиков. В этом случае соответствующая используемая функция ошибок отражает степень неопределенности при измерении расстояния.
Как только вы выбрали подходящую функцию ошибки, вам нужно найти способ ее оптимизации. Самый простой способ сделать это - вычислить градиент для вашей функции ошибки и использовать его, чтобы следовать алгоритму поиска пути до самой низкой точки. Если ваша функция ошибок хорошо себя ведет, это должно работать, хотя и не так быстро. Если вы амбициозны, вы можете использовать многомерный метод Ньютона-Рафсона, чтобы найти эту точку. Это делает больше предположений о вашей функции ошибок, и будет много работы, но будет сходиться гораздо быстрее.
Эта проблема обычно решается с помощью линейной алгебры путем решения "наименьших квадратов", что минимизирует квадрат ошибки.
Вот как GPS-приемники находят "наилучшее соответствие", чтобы дать ваши координаты. Они принимают набор "шумных" расстояний до всех разных спутников и находят новый набор расстояний, которые соответствуют одной точке, которая имеет наименьшую квадратичную ошибку от "шумных" расстояний.
Существует множество библиотек линейной алгебры (наиболее преобладающим из которых является linpack), которые должны иметь функции для решения проблем этих типов.