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

Question

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

假设您有想要沿着n城市线放置的p塔，其中每个城市是从1到n的整数。放置塔的成本是从塔到其他城市的预期距离。问题是提供一个有效的算法来布置所有的p塔，同时最小化成本。

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

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

然而，当有2个或更多的塔时，我遇到了问题。我试图将城市划分为不同的、连续的子集，但我似乎无法取得进展--即我似乎无法识别子问题。

有什么建议吗？

编辑：

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

Answer 1

从你的链接判断，你要做的是将p塔放置在不同大小的均匀分布的城市中，i城市的大小是，比方说，s(i)。您希望最小化从每个人到最近的塔的平均距离。或者，等效地，最小化从人到塔的距离的总和。

我说的对吗？

如果是这样的话，子问题是将k塔放置在两个标记i和j (其中这些标记位于城市之间或末端之外)之间，以使人到塔的距离之和最小。作为进一步的限制，要么k是2的幂，要么标记偏离地图的右边缘，并且k是n的二进制表示的尾端。

对于每个子问题，如果是1 < k，则信息是拆分为更小的子问题的最佳位置；否则，如果是k = 1，则是塔的位置。(请记住，如果k是2的幂，我们将均匀地拆分塔楼，否则，如果我们的范围偏离右边缘，并且k不是2的幂，则拆分为2的幂和表示的其余部分。)

将有O(log(p) * n^2)子问题需要考虑，这应该完全服从动态编程，动态编程可以自上而下或自下而上地实现。

Answer 2

一次递增一座塔，遍历所有城市。假设g(i)是在ith位置放置一座塔的成本-根据你的帖子，此函数仅取决于塔和城市的位置，后者已经固定。我将把计算的细节留给读者。

假设m(t,i)是将t塔放置到索引i的成本。那么一般的情况是：

m(t, i) = min(
  // Place a tower at i
  g(i) + m(t - 1, i - 1),

  // Do not place a tower at i
  m(t, i - 1)
)

正如我们所看到的，在自下而上的方法中，我们在m中的两次查找都已经被记录下来，因为我们正在迭代递增数量的塔，每次都是从第一个城市位置到最后一个城市位置。

更新：

由于问题现在增加了信息，“放置一座塔将影响其他塔的放置方式，因为特定城市的人们将前往离他们最近的塔”，这里是一个O(t * n^2)公式。让f(t, i)表示放置在i的第t个塔，c[i]表示第i个城市，d(c, t)表示从城市c到t的塔的距离/成本函数。然后，从左向右迭代：

f(t, i) =
  if t is the leftmost tower:
    // cities left of t
    sum d(c[0..i], i)

  otherwise:
    min(
      // cities right of and closer to (t - 1)
      sum d(c[l..m], l) +

      // cities left of and closer to t
      sum d(c[m+1..i], i)

      if t is the rightmost tower, also add:
        // cities right of t
        sum d(c[i..last c], i) +

      where l is the location of the neighbouring tower
      to the left and m is the middle city, closer to l
    )

    for all l

  for all i