|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Tsyplakov 2:5020/400 28 May 2001 16:06:43
To : All
Subject : Re: Weighted mediam
--------------------------------------------------------------------------------
Stanislav Shwartsman пишет в сообщении...
> Hello Alexei!
>
> 26 May 01 19:23, you wrote to me:
>
> SS>> Дано N точек на плоскости с координатами Pi(Xi, Yi) и
весом
> SS>> Wi каждая. Hайти сабж для этих точек - такую точку P(X,Y)
на
> SS>> плоскости, что для нее
>
> SS>> N
> SS>> Sum [ Wi*D(Pi, P) ] i=1
>
> SS>> будет минимальным. D - расстояние между точками,
вычисляется
> SS>> по формуле D(Pi, P) = abs(Xi-X) + abs(Yi-Y)
>
> AF> кажись эта задача называется "где построить школу" :)
>
> очень на то похоже ;)
Это другая задача.
> AF> есть три деревни, в каждой соотв. кол-во детей/потенциальных
> AF> учеников.
> AF> не математическое простое решение:
> AF> приклеиваешь карту района с этими деревнями к столу, сверлишь
дырки в
> AF> точках этих деревень, берёшь три нитки, связанные с одной
стороны
> AF> (типа жиденького пучка), просовываешь три свободных конца
сквозь дырки
> AF> в столе, к тому что под столом привязываешь грузики с массой
> AF> пропорциональной кол-ву учеников в соответствующей деревне.
вылазишь
> AF> из-под стола, смотришь где находится узелок пучка на карте -
там
> AF> строить школу.
>
> А математического решения у тебя нет ? Точнее алгоритмического - с
O(N)
> сложностью ?
Про нитки лучше забыть. Они подразумевают другое расстояние
> AF> только вот расстояние у тебя почему-то сумма модулей, а не по
> AF> Пифагору. ошибка?
>
> Hет, не ошибка. Эта формула расстояния называется метрика
Манхеттена и
> эквивалентна Эвклидовой. В очень многих задачах можно заменить
Эвклидову
> метрику на метрику Манхеттена без влияния на результат.
Вряд ли можно заменить для размерности 2. Это ошибка
Скажу во-первых, что задача распадается на две, т.к. по X и по Y можно
минимизировать отдельно. Во-вторых, известно, что задача на
минимизацию суммы модулей в одномерном случае есть задача на поиск
медианы (откуда и сабж).
Медиана считается просто. Hапример, нужно найти медиану Xi. Сначала
сортируем числа Xi по возрастанию, а затем берем что-то типа (N/2)-го
наблюдения. Если N нечетное, то берут ((N+1)/2)-е наблюдение, а если
четное - то любое число между (N/2)-м и ((N+2)/2)-м наблюдением. Суть
в том, чтобы слева и справо от медианы было одинаковое количество
наблюдений. Если же медиана взвешенная, то нужно ее выбирать так,
чтобы _сумма весов_ по наблюдениям слева и справа была одинакова
(насколько возможно). Можно идти слева направо и корректировать суммы
весов слева и справа. Если в какой-то точке разность этих сумм меняет
знак, то это и есть медиана.
Сортировка примерно O(N*logN). Hо можно быстрее. Идея такая же как в
QuickSort. Если надо, могу подробнее.
С уважением,
А.Цыплаков
-----------------------------
Alexander Tsyplakov
Novosibirsk State University
http://www.nsu.ru/ef/tsy/
--- ifmail v.2.15dev5
* Origin: Novosibirsk State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
