|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 28 May 2001 11:46:51
To : Stanislav Shwartsman
Subject : Weighted mediam
--------------------------------------------------------------------------------
Sat May 26 2001 20:32, Stanislav Shwartsman wrote to Alexei Frounze:
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>> кажись эта задача называется "где построить школу" :)
SS> очень на то похоже ;)
AF>> есть три деревни, в каждой соотв. кол-во детей/потенциальных
AF>> учеников.
AF>> не математическое простое решение:
AF>> приклеиваешь карту района с этими деревнями к столу, сверлишь дырки в
AF>> точках этих деревень, берёшь три нитки, связанные с одной стороны
AF>> (типа жиденького пучка), просовываешь три свободных конца сквозь дырки
AF>> в столе, к тому что под столом привязываешь грузики с массой
AF>> пропорциональной кол-ву учеников в соответствующей деревне. вылазишь
AF>> из-под стола, смотришь где находится узелок пучка на карте - там
AF>> строить школу.
SS> А математического решения у тебя нет ? Точнее алгоритмического - с O(N)
SS> сложностью ?
AF>> только вот расстояние у тебя почему-то сумма модулей, а не по
AF>> Пифагору. ошибка?
SS> Hет, не ошибка. Эта формула расстояния называется метрика Манхеттена и
SS> эквивалентна Эвклидовой. В очень многих задачах можно заменить Эвклидову
SS> метрику на метрику Манхеттена без влияния на результат.
Приведенное решение относится только к Евклидовой метрике, в Манхеттенской
задача сильно упрощается за счет разделимости (т.е. можно искать отдельно по
координатам)
А вот О(N) у меня не получается, разве что точки уже упорядочены. Hаходим
общую сумму весов, и идем от точек с минимальной координатой к максимальной.
Суммируем по дороге веса. Когда насчитаем половину - ответ готов (точнее,
ответ - любое значение между точкой, сумма весов для которой меньше половины,
и точкой, для которой больше). Аналогично по второй координате.
С уважением
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
