|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 27 May 2001 00:01:21
To : All
Subject : Re: Weighted mediam
--------------------------------------------------------------------------------
"Stanislav Shwartsman" <Stanislav.Shwartsman@f520.n400.z2.fidonet.org> wrote
in message news:990889057@f520.n400.z2.ftn...
> Hello All!
>
> Задача попалась такая нехорошая:
>
> Дано N точек на плоскости с координатами Pi(Xi, Yi) и весом Wi каждая.
> Hайти сабж для этих точек - такую точку P(X,Y) на плоскости, что для
нее
>
> N
> Sum [ Wi*D(Pi, P) ] i=1
>
> будет минимальным. D - расстояние между точками, вычисляется по
формуле
> D(Pi, P) = abs(Xi-X) + abs(Yi-Y)
>
> Сложность алгоритма должна быть O(N), запрещается пользоваться
> итеративными математическими выражениями, которые накапливают ошибку
> в точности.
Hу во-первых задача разделяется по направлениям, т.е. для X и Y
решается независимо, т.е отдельно минимизируем
D(X_i, X) = Sum [ W_i*abs(X_i-X)]
и отдельно
D(Y_i, Y) = Sum [ W_i*abs(Y_i-Y)]
Теперь как решить такую задачу для Х. Допустим, что X_i
отсортированы по возрастанию (знаю, что сортировка больше O(N)
но допустим. Также допустим, что X попадент между X_j и X_(j+1).
Cледовательно, можем убрать abs(), заменив их знаками
Sum [ W_i*abs(X_i-X)] = Sum_1^j [ W_i*(X-X_i)] + Sum_(j+1)^N [ W_i*(X_i-X)]
и задача минимизации этой суммы сводится к сравнению
Sum_1^j [ W_i*(X_j-X_i)] + Sum_(j+1)^N [ W_i*(X_i-X_j)]
и
Sum_1^j [ W_i*(X_(j+1)-X_i)] + Sum_(j+1)^N [ W_i*(X_i-X_(j+1))]
т.е. попадаем либо в X_j, либо в X_(j+1).
Главное, что показал данный шаг - то, что решение совпадает
с одним из X_i.
В принципе можно было бы расчитать все возможные такие суммы,
и выбрать минимум, что может быть сделанно за O(N) операций.
Hо, сортировка :( как минимум O(NlnN).
Тогда, несколько другой подход - выберем начальное приближение
для X, решив задачу минимизиции с квадратами вместо модулей.
Sum [ W_i*(X_i-X)^2]
что дает
X = Sum [W_i*X_i]/Sum [W_i];
и найдем несколько (думаю, что три-четыре - достаточно)
ближайших к X точек X_j и посчитать для них суммы D(X_i,X_j)
и выбрать минимальную. Все это требует O(N) операций.
Все.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
