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

18

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

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

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

В чем ваша проблема тогда? Это не настоящий вопрос, я думаю. moooeeeep
означает, что у вас есть сетка и какая-то точка на ней помечена, и вы хотите найти точку в сетке, которая имеет минимальное среднее расстояние Манхэттена с отмеченной точкой? Saeed Amiri
Это домашнее задание? Если это так, мы должны добавить этот тег. Кроме того, вам дан список пунктов, из которых можно выбрать ответ? Jonathan M
Вы спрашиваете: у меня есть сетка с определенными пересечениями помечены. Я хотел бы найти пересечение в сетке, которое является ближайшим ко всем отмеченным пересечениям. ?? Jonathan M
Не домашнее задание, я наткнулся на статьюspringerlink.com/content/2yrp1u5gkdf05pgx , но я не мог понять ни одного слова, думал, что кто-то может объяснить здесь простым английским языком. user1045047

Ваш Ответ

1   ответ
34

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

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

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

Если точки на линии такие:

-4 | | | 0 | 2 3 4
             ^

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

Если точки на линии такие:

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

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

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

EXAMPLE

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

Представьте, что вы хотите найти точки, которые находятся на минимальном расстоянии от Манхэттена до набора(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 
COMPLEXITY

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

Давайте поговорим о сложности.

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

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

Время работы не O (n), а O (n) в среднем;)
Спасибо за пример. Очень помогло. user1045047
Не могли бы вы объяснить с помощью этого примера, скажем, набор равен {(1,1) (2,2)}, таким образом, точки с минимальной суммой манхэттенского расстояния будут {(1,1), (2,2), (1 , 2), (2,1)}, для каждого из них сумма равна 2. user1045047
Почему медиана является решением проблемы?
@ user1045047 Я все еще улучшаю свой пост. Теперь я добавил полный пример того, как вы находите решения оригинальной задачи тоже.

Похожие вопросы