Алгоритм нахождения точки минимального общего расстояния от локаций

Question

Я создаю приложение, основанное на поиске «удобного места встречи» с учетом набора местоположений.

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

• А находится при (0,0)
• B составляет (0,0)
• С находится при (0,12)

Местоположение минимальной общей поездки для этих точек находится в точке (0,0) с общим расстоянием поездки 12; центр тяжести находится в точке (0,4) с общим расстоянием перемещения 16 (4 + 4 + 8).

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

Что я не могу сделать, так это придумать какой-либо алгоритм для решения этой проблемы - предложения приветствуются, пожалуйста!

Answer 1

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

http://www.geomidpoint.com/calculation.html

Этот вопрос также очень похож на

Минимальная сумма всех времен прохождения

Вот статья в Википедии об общей проблеме, которую вы пытаетесь решить:

http://en.wikipedia.org/wiki/Geometric_median

Answer 2

В некотором смысле вы ищете центр масс треугольника с равными весами в вершинах.Это указывало бы на барицентрические координаты.

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

Answer 3

Один из вариантов - определить целевую (и градиентную) функцию и использовать универсальную библиотеку оптимизации, например scipy.optimize .fmin_cg будет хорошим алгоритмом для решения вашей проблемы.Ваша цель - сумма расстояний, как определено в разделе «Определение» страницы Геометрическая медиана Википедии , на которую ссылается топор.Аргументом для вашей целевой функции является y .