带权中位数的带权中位数问题

发布网友发布时间：2022-05-03 03:17

共1个回答

热心网友时间：2022-07-01 19:07

而在信息学竞赛中，有这样一类题，给出了若干个排列在一条直线上的点，每个点有一个权值，比如说货物量、人数什么的，然后让我们找出使所有点的货物、人集合到一个点的总代价最小的位置。我们将会发现，这一类问题实际上就是带权中位数问题。
例如：
我国蒙古大草原上有 N（N 是不大于 100 的自然数）个牧民定居点 P1（X1，Y1）、P2
（X2，Y2）、 …Pn（Xn，Yn），相应地有关权重为 Wi，现在要求你在大草原上找一点 P（Xp，
Yp），使 P点到任一点 Pi的距离 Di 与Wi 之积之和为最小。
即求 D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值
结论：对 x与 y两个方向分别求解带权中位数，转化为一维。
设最佳点 p为点 k，则点 k 满足：
令 W 为点 k到其余各点的带权距离之和，则
sigma( i=1 to k-1) Wi <= W/2
sigma( i=k+1 to n) Wi <= W/2
同时满足上述两式的点 k 即为带权中位数。