Вопрос по algorithm – Все точки с минимальным Манхэттенским расстоянием от всех других заданных точек [Оптимизировано]

8

Проблема здесь состоит в том, чтобы найти множество всех целочисленных точек, которые дают минимальную сумму на всех расстояниях Манхэттена от данного набора точек!

Например:

давайте иметь заданный набор точек {P1, P2, P3 ... Pn}

Основная проблема состоит в том, чтобы найти точку, скажем, X, которая имела бы минимальную сумму на всех расстояниях от точек {P1, P2, P3 ... Pn}.

т.е. | P1-X | + | P2-X | + .... + | Pn-X | = D, где D будет минимальным по всем X.

Если продвинуться дальше, может быть более одного значения X, удовлетворяющего указанному выше условию. то есть возможно более одного X, что давало бы одно и то же значение D. Итак, нам нужно найти все такие X.

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

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

Итак, есть ли другой подход, который дал бы результат, даже когда точки очень далеко друг от друга (где медиана дает диапазон, который составляет порядка 10 ^ 9).

@soulcheck: Ах, вы правы, использование среднего значения фактически минимизирует сумму квадратов. BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft floor (mean) не дает вам минимального расстояния. возьмите [0,99,100,101]. пол (среднее) = потолок (среднее) = 75, но самые близкие точки - 99 и 100. soulcheck

Ваш Ответ

4   ответа
3

то каждая точка в этом интервале так же хороша, как и любая другая.

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

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

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

Твой ответ убедителен. Это означает, что в случае нечетного количества точек всегда будет одна точка на минимальном расстоянии. Если я просто хочу посчитать количество точек на минимальном расстоянии, то в случае нечетного количества точек его всегда 1, а в четном случае это произведение интервала, заданного медианой. Правильно Login Test
@ LoginTest просто чтобы было понятно. В случае нечетного количества точек вы получите одну медиану в каждом измерении. Таким образом, есть только одна «ближайшая» точка, если количество точек нечетное. soulcheck
@ LoginTest право! soulcheck
Понял!! Это очень ясно. :) Login Test
9

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

Proof: Если у нас будет четное количество очков, будет два медианы. Точка между двумя медианами будет иметь n / 2 точки слева и n / 2 точки справа и общую сумму расстояний до этих точек S.

Если мы переместим его на одну точку влево, S увеличится на n / 2 (поскольку мы удаляемся от крайних правых точек) и вниз на n / 2 (поскольку мы движемся к крайним левым точкам), так что в целом S остается прежним. Это верно до тех пор, пока мы не достигнем самой левой средней точки. Когда мы двигаемся на одну левую часть от крайней левой средней точки, у нас теперь есть (n / 2 + 1) точек вправо и (n / 2 - 1) точек влево, поэтому S повышается на два. Продолжение влево только увеличит S.
По той же логике все точки справа от самой правой медианы также имеют более высокое значение S.

Если у нас нечетное количество баллов, то есть только одна медиана. Используя ту же логику, что и выше, мы можем показать, что она имеет наименьшее значение S.

Хорошее объяснение, сэр. Это помогло мне понять решение. Спасибо!! :) Login Test
1

вы можете рассмотреть их также отдельно. Оптимальный ответ (медиана (х), медиана (у)). Вам нужно осмотреть эту точку для целочисленных решений.

НОТ: Я не прочитал ваш вопрос правильно, отвечая. Мой ответ остается в силе, но, возможно, вы уже знали об этом решении.

0

я также думаю, что для нечетного числа N точек на сетке будет только одна точка (т. Е. МЕДИАНА), которая будет находиться на минимальной сумме расстояния Манхэттена от всех других точек.

Для четного значения N сценарий будет немного другим.

По мне, если два комплектаX = {1,2} and Y= {3,4} их декартово произведение всегда будет 4.

т.е.X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}. Это то, что я понял до сих пор.

В качестве ДАЖЕ количества значений мы всегда принимаем значения «СРЕДНЕЕ ДВА» в качестве СРЕДНЕГО. Взятие 2 из X и 2 из Y всегда вернет декартово произведение 4 баллов.

Поправь меня, если я ошибаюсь.

Спасибо Логин! Иди. Mayank Kataria
Вы правы насчет медианы, но не правы насчет декартовых произведений. На самом деле может быть большой диапазон X и Y, и, следовательно, большее количество точек будет удовлетворять условию не только 4 во всех случаях. Число точек будет (| x1-x2 + 1 | * | y1-y2 + 1 |), где {x1, x2} - медианы для координат по оси X, а {y1, y2} - медианы по оси Y -ordinates. Login Test

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