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

Question

我在为我的研究生算法课学习时遇到了这个问题:

假设您有 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)要考虑的子问题，这应该完全适用于动态规划，可以自上而下或自下而上地实现。