algorithm - 最小化直线上的距离平方和

Question

A total of n apartment buildings is coming up on a new street. The postal service wants to place a single mailbox on the street. Their objective is to minimize the total square of distances that residents have to walk to collect their mail each day.

Building i has r[i] residents, and is at distance d[i] from the beginning of the street. Devise an algorithm that computes a distance m from the beginning of the street for the mailbox that minimizes the total square of distance, that residents travel to get to the mailbox.

我的计划是根据距街道起点的距离对建筑物进行排序。然后，找到居民总数并计算中位数。然后将邮箱放置在与居民中位数相对应的建筑物中。这是正确的解决方法吗？

Answer 1

你想最小化:

sum(r[i](m-d[i])^2)

为了解决这个问题，对 m 进行微分:

sum( 2.r[i].(m-d[i]) )

要找到最小值，将导数设置为 0:

0 = sum( 2.r[i].(m-d[i]) )
m.sum(r[i]) = sum(r[i].d[i])
m = sum(r[i].d[i]) / sum(r[i])

即m 是距离的加权平均值。

(如果你想最小化绝对距离之和，那么答案将由中位数给出。)