Алгоритм минимального расстояния в манхэттенском пространстве

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

В ДРУГИХ СЛОВАХ:

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

Ответ 1

Прохладная вещь о расстоянии Манхатана заключается в том, что само расстояние состоит из двух независимых компонентов: расстояния по координатам x и y. Таким образом, вы можете решить две более простые задачи и объединить полученные результаты для получения желаемых результатов.

Задача, о которой я говорю, такова: заданы точки на линии. Найдите точку на линии, которая минимизирует сумму абсолютных расстояний до всех точек. Если их найти много (кстати, они всегда превращаются в один сегмент, который легко доказать). Сегмент определяется (потенциально двумя) точками медианы множества. Посредством я имею в виду точку, которая имеет равное количество точек слева и справа от нее. В случае, если число точек нечетное, такой точки нет, и вы выбираете точки с разностью 1 в обоих направлениях для формирования сегмента.

Здесь я добавляю примеры решений этой более простой задачи:

В случае, если точки на линии выглядят так:

-4 | | | 0 | 2 3 4
             ^

Решение - это просто точка и 2.

В случае, если точки на линии выглядят так:

-4 | | | 0 | 2 3
         ^---^

Весь отрезок [0, 2] является решением задачи.

Вы решаете эту задачу отдельно для координат x и y, а затем объединяете результаты, чтобы получить прямоугольник минимальных дистанционных точек.

ПРИМЕР

И вот теперь пример решения для начальной задачи.

Представьте, что вы хотите найти точки с минимальным расстоянием Манхатана до набора (0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4)

Вы создаете две более простые задачи:

Для x:

0 1 2 3 3 4
    ^-^

И здесь решение - это сегмент [2, 3] (обратите внимание, что здесь мы дублируем точку 3, которую я представлял, возможно, не самым интуитивным образом).

Для y:

3 3 4 5 6 7
    ^-^

Здесь решение является отрезком [4, 5].

Наконец, мы получим, что решение начальной задачи - это прямоугольник с формулой:

 2 <= x <= 3; 4 <= y <= 5

КОМПЛЕКСНОСТЬ

Как многие люди проявляют интерес к этому сообщению, я решил улучшить его немного больше.

Расскажите о сложности.

Сложность задачи на самом деле такая же, как сложность решения более простой задачи (поскольку, как уже говорилось, решение фактически состоит из решения двух более простых задач). Многие люди пойдут и решают его, сортируя, а затем выбирая медиан. Однако это вызовет сложность O(nlog n), где n - количество точек в наборе входных данных.

Это может быть улучшено, если используется лучший алгоритм для нахождения k-го элемента (Пример реализации в С++ STL). Этот алгоритм в основном следует тому же подходу, что и qsort. Время работы O(n). Даже в случае двух медианных точек это будет оставаться линейным (требуется два прогона одного и того же алгоритма), и, таким образом, общая сложность алгоритма становится O(n). Очевидно, что задача не может быть решена быстрее, если сам вход имеет указанную сложность.