Кратчайшее расстояние - общее место встречи

Question

Я столкнулся с этой проблемой, когда на двумерной сетке есть несколько домов (их координаты указаны), и нам необходимо найти, какой дом можно использовать в качестве места встречи, чтобы расстояние, пройденное каждым, было минимальным,Предположим, что расстояние по оси x или y занимает 1 единицу, а расстояние до диагональных соседей составляет, скажем, 1,2 единицы.

Я не могу придумать хороший алгоритм оптимизации для этого.

PS: не домашнее задание.И я только ищу алгоритм (не код) и, если возможно, его доказательство.

PS # 2: Я не ищу исчерпывающее решение.Хотите верьте, хотите нет, но это меня поразило:)

Answer 1

Как уже указывалось, в случае манхэттенского расстояния медиана дает решение.Это очевидный вывод из общеизвестного факта, что медиана минимизирует среднее абсолютного отклонения:

E|X-c| >= E|X-median(X)| для любой постоянной c.

И здесь вы можете найти примердоказательство для дискретного случая:https://stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315

Answer 2

У меня была та же проблема в течение некоторого времени. Решением является очевидный консенсус, данный в предыдущих постах: найти медиану (mx, my) независимо, а затем найти точку, ближайшую в данных N точках, и это место встречи. Чтобы понять, почему на самом деле это решение, сначала нужно рассмотреть расстояние.

d = сумма (| xi-x |) + сумма (| yi-y |) по всем 1 <= i <= N, </p>

, который не зависит от х и у. Следовательно, мы можем решить одномерный случай для x и y. Я пропущу объяснение, данное ^^, и, следовательно, заключу, что (mx, my) является лучшим решением , если , мы рассмотрим все возможные моменты. Более сложная задача - доказать, что мы можем перейти от (mx, my ) к ближайшему (xi, yi), так что (xi, yi) является одной из заданных точек без изменения (увеличения) расстояния. Доказательство идет:

Учтите, что мы отсортировали x-координаты (для доказательства) и это X1<X2<...<Xn. Также Xj<mx<X(j+1), где j = N/2, теперь давайте перейдем mx один шаг влево, то есть mx' <- mx-1. Отсюда d' = |X1-mx+1| + .. + |Xj-mx+1| + |X(j+1)-mx+1| + .. + |Xn-mx+1| Мы знаем, что mx-1 увеличит значения N / 2 (для k> = j + 1 и уменьшит для <= j), следовательно, эффект тот же. Таким образом (mx-1, my) дает то же самое решение. Это означает, что есть пробел от <code>Xj<mx<X(j+1) и Yj<my<Y(j+1) где расстояние не меняется. Таким образом, мы можем найти ближайший такой пункт, на который есть ответ.

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

Это мой первый пост, помогите мне улучшить свои навыки письма.

Answer 3

Ваша метрика расстояния странная. Вы ожидаете, что путешествие по диагонали должно занимать как минимум sqrt (2) ~ = 1,41 расстояние, превышающее расстояние перемещения в направлении компонента, потому что это намного дальше, если путешествовать по прямой вдоль диагонали по теореме Пифагора. .

Если вы настаивали на расстоянии до Манхэттена (диагонали не разрешены), то вам нужно выбрать дом, ближайший к медиане (x) + медиане (y) домов.

Рассмотрим случай 1D, у вас есть несколько точек на линии, и вы хотите выбрать место встречи. Для конкретности / простоты, скажем, есть 5 домов, ни одного дубликата.

Подумайте, что происходит, когда место встречи смещается от медианы вправо. За каждый отряд, пока вы не пройдете 4-й дом слева направо, 3 человека должны сделать дополнительный шаг вправо, и 2 человека должны сделать еще один шаг влево, поэтому стоимость возрастает на 1. Как только вы Пройдите 4-й дом, затем 4 человека должны сделать дополнительный шаг вправо, а один человек должен сделать еще один шаг влево, поэтому стоимость увеличивается на 3. При перемещении места встречи в слева от медианы. Отход от медианы всегда увеличивает стоимость.

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

Answer 4

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

Answer 5

Ваша проблема называется Оптимальным определением точки встречи. Следующая статья дает эффективный приближенный алгоритм http://www.cse.ust.hk/~wilfred/paper/vldb11.pdf

Answer 6

Ну, вы могли бы перебор.Возьмите каждый дом и рассчитайте расстояние до каждого другого дома.Суммируйте расстояния для каждого отдельного дома.Тогда просто возьмите дом с самой низкой суммой.