algorithm - 了解 Cormen 邮局定位解决方案

Question

Cormen 的《Introduction to algorithms》一书第 9 章有一个问题post office location problem。

We are given n points p1,p2,...pn with weights w1,w2,....wn. Find a point p(not necessarily one of the input points) that minimizes the sum wi*d(pi,p) where d(a,b) = distance between points a,b.

查看相同的解决方案，我了解到加权中位数将是解决此问题的最佳解决方案。

但我对实际的编码部分和用法有一些基本的怀疑。

• 如果所有元素的权重都相等，那么为了找到加权中位数，我们找到所有权重之和 < 1/2 的点。这里怎么扩展？

• 给定一个真实的场景，将在不同房屋中投递的信件数量作为权重，我们希望通过找到邮局的位置来最小化行进距离，给定 x 坐标(假设所有房子是一维的)，我们实际上会怎么做？

有人可以帮助我消除疑虑并理解问题。

编辑:

我也在想一个很相似的问题:有一个长方形的网格(2d)，不同的地方有不同的人数，都想在1点见面(坐标肯定是整数)，那有什么区别从上面的问题中我们将如何解决它？

Answer 1

您仍然想要权重总和为 1/2 的点。选择任意一点并考虑从那里向左移动一个点还是向右移动一个点会更好。如果向左移动一点，则到左侧所有点的距离减少一，到右侧所有点的距离增加一。这样做的输赢取决于左边权重的总和和右边权重的总和。如果权重之和不等于 1/2，您可以通过朝权重 > 1/2 的方向移动来做得更好，因此唯一不能通过选择另一个权重做得更好的点是权重为 1/2 的点- 或者，更准确地说，两边的权重都 <= 1/2 的点。

要使 1/2 成为正确答案，权重总和必须为 1，因此如果您从字母数权重开始，那么您必须将它们除以字母总数才能得出它们的总和一。当然，除非您必须为每封要投递的信件进行一次单独的旅行，否则这种惩罚功能并没有真正意义，但我假设我们应该忽略它。

编辑

对于不止一个维度，您几乎可以直接解决最小化距离加权和的问题。维基百科在 http://en.wikipedia.org/wiki/Geometric_median 中对此进行了描述.您想考虑权重，但这并不会使问题复杂化。一种方法是 http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares .不幸的是，这并不能保证它找到的解决方案将在一个网格点上，或者离解决方案最近的网格点将是最佳网格点。它可能不会太糟糕，但在所有可能的情况下找到最好的网格点可能会更棘手。