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

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

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

  • A is at (0,0)
  • B is at (0,0)
  • C is at (0,12)

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

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

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


coordinates distance algorithm
person Kristian Glass    schedule 03.01.2012    source источник
comment
На каком языке вы бы предпочли реализовать свое решение?   -  person calebds    schedule 04.01.2012
comment
Python был бы идеальным, но я возьму практически все, что не APL / INTERCAL или подобное.   -  person Kristian Glass    schedule 04.01.2012

Ответы (3)


arrow_upward
12
arrow_downward

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

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

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

Минимальная сумма всего времени в пути

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

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

person hatchet - done with SOverflow    schedule 03.01.2012
comment
Этот вопрос и большинство ответов связаны с тем, что местоположение является одним из ограничений, которые мне не нужны; однако решение, на которое вы ссылаетесь, кажется жизнеспособным, спасибо - person Kristian Glass; 04.01.2012
comment
@KristianGlass - Прочтите статью в Википедии, она не учитывает это ограничение и упоминает подход первой ссылки как часто используемое решение. - person hatchet - done with SOverflow; 04.01.2012

arrow_upward
3
arrow_downward

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

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

person Chris    schedule 03.01.2012

arrow_upward
1
arrow_downward

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

person jrennie    schedule 03.01.2012