请输入您要查询的百科知识:

 

词条 带权中位数
释义

带权中位数,就是给定的N个数都有一个权值,或者说相当于个数。此时的中位数就不再是第N/2个数了,而是第∑DI/2个数。

定义

我们都学过中位数问题,即给定了N个数后,位于第[N/2]的数就是中位数。

带权中位数问题:

而在信息学竞赛中,有这样一类题,给出了若干个排列在一条直线上的点,每个点有一个权值,比如说货物量、人数什么的,然后让我们找出使所有点的货物、人集合到一个点的总代价最小的位置。我们将会发现,这一类问题实际上就是带权中位数问题。

例如:

我国蒙古大草原上有 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 即为带权中位数。

证明(简):

若最优点在T

则有:

{D[I]*DIST(IT)}(I<>T)<={D[I]*DIST(I,T+1)}(I<>T+1)

将此式化为:

{D[L]}*DIST(L,T)}+{D[R]*DIST(R,T)}+D[T+1]*DIST(T+1,T)

<=∑{D[L]}*DIST(L,T+1)}+∑{D[R]*DIST(R,T+1)}+D[T]*DIST(T,T+1) (L<T&R>T+1)

即:

{D[L]*DIST(L,T+1)}-{D[L]*DIST(L,T)}(L<T)+D[T]*(DIST(T,T+1))>={D[R]*DIST(R,T)}-(D[R]*DIST(R,T+1))(R>T+1)+D[T+1]*(DIST(T,T+1))进一步化简为:

{D[L]*(DIST(L,T)-DIST[L,T+1])}(L<=T)<={D[R]*(DIST(R,T+1)-DIST(R,T))}(R>=T+1)DIST(L,T)-DIST(L,T+1)=DIST(T,T+1)

DIST(R,T+1)-DIST(R,T)=DIST(T+1,T)

OBVIOUSLY : DIST(T,T+1)=DIST(T+1,T)

因此:

D[L](L<=T)>=(D[R])(R>=T+1)

即:∑D[L](L<T)+D[T]>=(D[R])(R>T)

因此我们发现,若T是最优点,则必有其左边的权值和加上D[T]后大于右边的权值和

而类似的,我们可以证明其右边的权值和加上D[T]后大于左边的权值和

因此我们要找的点也就是满足以上条件的点。注意到此时我们的选择已经和具体的位置(坐标)没有关系了,而成为主要考虑因素的仅仅是各点上的权值。

因为左边的权值和数+D[T]>=右边的权值和,那么:

LEFTSUM+D[T]>=RIGHTSUM=SUMALL-(LEFTSUM+D[T])

=>2*(LEFTSUM+D[T])>=SUMALL

=>2*RIGHTSUM<=SUMALL

同理可得:

RIGHTSUM+D[T]>=LEFTSUM=SUMALL-(RIGHTSUM+D[T])

=>2*(RIGHTSUM+D[T])>=SUMALL

=>2*LEFTSUM<=SUMALL

此时我们发现:

2*LEFTSUM<=SUMALL 2*(LEFTSUM+D[T])>=SUMALL

也即是说当前的位置T上的数包含了第[(SUMALL)/2]个数,由开篇的简述可知,这第[(SUMALL)/2]个数,就是这个序列中的带权中位数。所以这一类问题,实质上就是带权中位数问题。

证明的简单说明:

我们可以简单地把上面的证明过程看作是左边的人都集合到了M点,而右边的人都集合到了M+1点。此时形成了两军对垒的形式,如果左边的总人数比右边的多,那么从左边走到右边去就没有从右边走到左边来优,反之亦然。那么既然在当前点我们左边的总人数已经比右边多了,那么再往右边移动,左边的人数会进一步增多,而右边的人会减少,那么只会导致更差的结果,所以此时我们可以判断最优点一定在当前点的左边,或者至少在当前这个点。那么范围就从当前的[L,R]缩小到了[L,M],通过不断地缩小范围(而每一次缩小我们都砍掉了一半的范围),最后我们得到的将是一个点——那就是我们要求的集合位置。

一些符号的意思:

D[I]—第I个点的权值

DIST(I,J)—I到J点的距离,即DIST(I,J)=|NUM[I]-NUM[J]|

由定义式易知:DIST(I,J)=DIST(J,I)

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/15 20:45:33