求问算法导论9-2题如何解

wxstorm
企鹅 2011-01-10 字数 107

就是N个点p1,p2....pN,对应weight w1, w2....

求个点到这些点的距离和最小

一维: d=|x-pi|

二维:  d=|x-pxi|+|y-pyi|

Algorithm 算法
9 个回复
wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2011-01-10

没这个题号。。。

【 在 wxstorm (企鹅) 的大作中提到: 】

: 就是N个点p1,p2....pN,对应weight w1, w2....

: 求个点到这些点的距离和最小

: 一维: d=|x-pi|

: ...................

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2011-01-10

一维的情况是中位数吧?

没用到weight?

【 在 wxstorm (企鹅) 的大作中提到: 】

: 就是N个点p1,p2....pN,对应weight w1, w2....

: 求个点到这些点的距离和最小

: 一维: d=|x-pi|

: ...................

wxstorm
企鹅 2011-01-10

Page 194 第二版的英文版

post-office location problem问题

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 没这个题号。。。

wxstorm
企鹅 2011-01-10

题目说是weighted median。

为啥呢

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 一维的情况是中位数吧?

: 没用到weight?

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2011-01-11

你的原帖对题目描述有问题。。。

话说,9-2的c)你怎么做的?利用线性时间的中位数算法找出带权中位数。

【 在 wxstorm (企鹅) 的大作中提到: 】

: 题目说是weighted median。

: 为啥呢

wxstorm
企鹅 2011-01-11

9-2 c)只要对9.3节的算法修改下就行了吧?

每次寻找到中间一个以后,分成两半的时候,计算前后的weight和(这个和移动一样的开销),1/2应该分到哪边就去哪边继续找。

那个post office是咋做的?

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 你的原帖对题目描述有问题。。。

: 话说,9-2的c)你怎么做的?利用线性时间的中位数算法找出带权中位数。

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2011-01-11

c)的证明大概是,设我们找到了点p,然后给他一个位移极小量o。那么对那个和式的影响就是w(d(p,pi)+o),就是w*d(p,pi)+w*o,恩,因为是移动,所以一边是加,一边是减。于是会发现w*o项应该是正数(保证最小),正好就满足了权重中位数的性质。

d)的解法还没想出来。

【 在 wxstorm (企鹅) 的大作中提到: 】

: 9-2 c)只要对9.3节的算法修改下就行了吧?

: 每次寻找到中间一个以后,分成两半的时候,计算前后的weight和(这个和移动一样的开销),1/2应该分到哪边就去哪边继续找。

: 那个post office是咋做的?

: ...................

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2011-01-11

d)两个维度分别求权重中位数,证明同c)

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: c)的证明大概是,设我们找到了点p,然后给他一个位移极小量o。那么对那个和式的影响就是w(d(p,pi)+o),就是w*d(p,pi)+w*o,恩,因为是移动,所以一边是加,一边是减。于是会发现w*o项应该是正数(保证最小),正好就满足了权重中位数的性质。

: d)的解法还没想出来。

wxstorm
企鹅 2011-01-11

牛~~~之前一直没想清楚那个位移变化和咋弄。。。。我傻了。。。

嗯,是到wo项不管往哪边移都为正的时候,p点就是最小了。

刚好是权重中位数

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: c)的证明大概是,设我们找到了点p,然后给他一个位移极小量o。那么对那个和式的影响就是w(d(p,pi)+o),就是w*d(p,pi)+w*o,恩,因为是移动,所以一边是加,一边是减。于是会发现w*o项应该是正数(保证最小),正好就满足了权重中位数的性质。

: d)的解法还没想出来。