Учитывая n точек на двумерной плоскости, какая точка такая, что расстояние от всех точек минимизировано? Эта точка не обязательно должна быть из множества заданных точек. Это центроид или что-то еще?
Как найти все такие точки (если более одного) с алгоритмом?
Это называется "Центр расстояния" и отличается от центра тяжести.
Во-первых, вы должны определить, какую меру расстояния вы используете. Если предположить, что вы используете стандартную метрику d = sqrt ((x1-x2) ^ 2 + (y1-y2) ^ 2), то она не является единственной, и задача минимизирует эту сумму.
Самый простой пример, чтобы показать этот ответ, не является уникальным примером прямой линии. Любая точка между двумя точками имеет равное полное расстояние от всех точек.
В 1D правильным ответом будет любой ответ, который имеет одинаковое количество точек справа и слева. Пока это верно, тогда любое перемещение влево и вправо будет увеличиваться и уменьшать левую и правую стороны на одну и ту же величину и, таким образом, оставлять расстояние одинаковым. Это также доказывает, что центроид не обязательно правильный ответ.
Если мы переходим к 2D, это уже не так, поскольку sqrt делает проблему взвешенной. Удивительно, но, похоже, не стандартный алгоритм! На странице здесь используется метод грубой силы. Я этого никогда не знал!
Если бы я хотел использовать алгоритм, я бы нашел медианную точку в X и Y в качестве начальной точки, а затем использовал алгоритм спуска градиента - это получило бы ответ довольно быстро. Все уравнение заканчивается квадратичным, поэтому кажется, что должно быть точное решение.
Может быть более одной точки. Рассмотрим плоскость с двумя точками на ней. Эти точки описывают линейный сегмент. Любая точка на этом сегменте будет иметь такое же полное расстояние от двух конечных точек.
Алгоритм грубой силы. может дать вам наилучшие результаты. Во-первых, найдите прямоугольник/любой четырехугольник, ограничивающий входные точки. Наконец, для каждой точки внутри прямоугольника вычислите расстояние от других точек. Суммируйте расстояния точки от входного набора. Скажите, что это "стоимость" точки. Повторите для каждой точки и выберите точку с мин. стоимость.
Интеллект также может быть добавлен в алгоритм. он может устранить области, основанные на средней стоимости и т.д.
Вот как я, по крайней мере, подойду к проблеме... надеюсь, что это поможет.
Это подробно обсуждается здесь http://www.ddj.com/architect/184405252?pgno=1