Вопрос по algorithm – Алгоритм минимального манхэттенского расстояния
Я хочу найти точку с минимальной суммой манхэттенского расстояния / прямолинейного расстояния от набора точек (т.е. сумма прямолинейного расстояния между этой точкой и каждой точкой в наборе должна быть минимальной). Результирующая точка может быть одной из точек из данного набора (не обязательно). Если существует несколько точек с одинаковым минимальным расстоянием, я хочу получить их все.
ДРУГИМИ СЛОВАМИ:
У меня есть сетка с отмеченными определенными пересечениями. Я хотел бы найти пересечение, которое является ближайшим ко всем отмеченным пересечениям. То есть мне нужно найти такую точку, чтобы сумма расстояний от всех точек была минимальной.
что само расстояние состоит из двух независимых компонентов: расстояния по координатам 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)
Вы формируете две более простые задачи:
Для х:
0 1 2 3 3 4
^-^
И здесь решением является сегмент[2, 3] (обратите внимание, что здесь мы дублировали точку3что я представлял, наверное, не самым интуитивно понятным способом).
Для тебя:
3 3 4 5 6 7
^-^
Здесь решением является сегмент[4, 5].
В итоге мы получаем, что решением исходной задачи является прямоугольник с формулой:
2 <= x <= 3; 4 <= y <= 5
Поскольку многие люди проявляют интерес к этому посту, я решил немного улучшить его.
Давайте поговорим о сложности.
Сложность задачи фактически такая же, как сложность решения более простой задачи (потому что, как уже обсуждалось, решение фактически состоит из решения двух более простых задач). Многие люди решат эту проблему путем сортировки, а затем выбрав медианы. Однако это приведет кO(nlog n) сложность, гдеn количество точек во входном наборе.
Это можно улучшить, если использовать лучший алгоритм для нахождения k-го элемента (пример реализации в C ++ STL). Этот алгоритм в основном следует тому же подходу, что и qsort. Время работыO(n), Даже в случае двух срединных точек это все равно останется линейным (требуется два прогона одного и того же алгоритма), и, таким образом, общая сложность алгоритма становитсяO(n), Очевидно, что задача не может быть решена быстрее, если сам ввод имеет указанную сложность.