算法:计算塔位置以最小化预期距离

Question

我在学习研究生算法类(class)时遇到了这个问题:

假设您有 p 个塔楼，您希望将它们放置在由 n 个城市组成的线上，其中每个城市都是从 1 到 n 的整数。放置塔的成本是塔到其他城市的预期距离。问题是提供一种有效的算法来放置所有 p 塔，同时最大限度地降低成本。

这里给出了一种贪婪的方法:https://www.mssanz.org.au/modsim2015/J11/dzator.pdf ，但似乎效率不太高。

到目前为止，我已经尝试使用动态规划来解决这个问题。例如，如果有 1 座塔和 5 个城市，我会遍历每个城市作为塔的潜在候选者，并计算在那里放置塔的成本。然后，我选择成本最小的城市。

但是，当有 2 个或更多塔时，我很难跟进。我试图将城市划分为不同的、连续的子集，但我似乎无法从中取得进展 - 即我似乎无法识别子问题。

有什么指点吗？

编辑:

塔的成本正如问题中所描述的那样:它是从塔的位置到城市的距离。然而，放置一座塔会影响其他塔的放置方式，因为特定城市的人们会去他们最近的塔。

Answer 1

从您的链接来看，您想要做的是放置 p塔 n均匀分布的不同规模的城市，其规模为i例如，第一个城市是 s(i) 。您希望最小化每个人到最近塔的平均距离。或者，等效地，最小化人们到塔的距离总和。

我说得对吗？

如果是这样，子问题将放置 k两个标记之间的塔i ，和j (这些标记位于城市之间或末端)，使得从人到塔的距离总和最小。作为进一步的限制， k是 2 的幂，否则标记会超出 map 的右边缘并且 k是 n 的二进制表示的尾部.

对于每个子问题，如果1 < k，信息是分割成更小的子问题的最佳位置。否则就是塔的位置，如果 k = 1 。 (请记住，如果 k 是 2 的幂，则我们将均匀地拆分塔，或者如果我们的范围超出右边缘且 k 不是 2 的幂，则拆分为 2 的幂和其余表示形式2.)

将会有O(log(p) * n^2)要考虑的子问题，这应该完全适合动态规划，可以自上而下或自下而上实现。