4

Cormen 的《算法简介》一书在第 9 章中有一个问题邮局位置问题。

我们有 n 个点 p1,p2,...pn，权重为 w1,w2,....wn。找到使总和 wi*d(pi,p) 最小化的点 p（不一定是输入点之一），其中 d(a,b) = 点 a,b 之间的距离。

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

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

  • 如果所有元素的权重相等，那么要找到加权中位数，我们会找到所有权重的总和 < 1/2 的点。如何在这里扩展它？

  • 给定一个真实场景，将要在各个房屋中递送的信件数量作为权重，并且我们希望通过找到邮局的位置来最小化要行驶的距离，给定 x 坐标（假设所有房屋都在 1 个单一维度中），我们将如何实际去做呢？

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

编辑 ：

我也在考虑一个非常相似的问题：有一个矩形网格（2d）和不同数量的人在不同的地方都想在1点见面（肯定有整数坐标），那么与上述问题，我们将如何解决？

4

2 回答 2

4

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

要使 1/2 成为正确答案，权重的总和必须为 1，因此，如果您从作为字母数量的权重开始，则必须将它们除以字母总数才能使它们总和为 1。当然，除非您必须为要交付的每封信进行单独的旅行，否则此惩罚功能实际上没有意义，但我假设我们应该忽略这一点。

编辑

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

于 2012-07-21T19:26:45.313 回答
-1

编辑：这个答案是错误的，见评论

您正在寻找的东西称为质心（TMHO 加权中位数是一维的质心）。

我没有得到你的第一个问题，你能详细说明一下吗？

对于您的示例，我们将计算与该职位相关的每个办公室的信件数量加权的平均职位。这将给我们：x_center = sum(x_i * w_i) / sum(w_i) 和 y_center = sum(y_i * w_i) / sum(w_i)。

它是否正确回答了您的问题？

于 2012-07-21T15:19:38.550 回答