最小化距离之和：优化问题

Question

实际问题如下：

麦当劳计划沿着一条直路开设多个连锁店（假设有n个）。这些店需要仓库来存储食物。一个仓库可以为任意数量的店提供存储，但必须只能位于其中一个店中。 麦当劳只有有限数量的仓库（假设为k），并希望将它们放置在使店到最近仓库的平均距离最小的位置。

给定一个长度为n的坐标点数组和整数“k”，返回一个长度为'k'的数组，其中包含最佳仓库位置的坐标。

抱歉，我没有可用的示例，因为我是凭记忆写下这些内容的。无论如何，可以使用以下样本：

数组={1,3,4,5,7,7,8,10,11} (n=9) k=1

答案：{7}

我一直在想：对于k=1，我们可以简单地找出集合的中位数，这将给出仓库的最佳位置。但是，对于k>1，应将给定集合分成'k'个子集（不相交，并且由超集的连续元素组成），并且每个子集的中位数将给出仓库位置。但是，我不明白应根据什么基础形成'k'个子集。提前感谢。

编辑：此问题还有一个变体：不是最小化总和/平均值，而是最小化店铺与其最近仓库之间的最大距离。我也不明白这个问题。

- Arpit Tarang

---

这是一份作业吗？如果是，请标记为作业。 - Karel Petranek

这是在一次比赛中获得的。 - Arpit Tarang

@ArpitTarang 我也遇到同样的问题了，你解决了吗？ - user3634974

Answer 1

这不是一个聚类问题，而是设施选址问题的特殊情况。您可以使用通用整数/线性规划软件来解决它，但由于问题在一条线上，可能会有更有效率（且成本更低）的算法可行。您可以考虑动态规划，因为可能有一些设施组合可以很快被消除。请查看P-Median problem以获取更多信息。

- Grembo

---

我从p-中位数问题的文章中没有得到太多信息。其中大部分都有一个额外的“运输成本”参数，这使得问题更加复杂。请帮忙。 - Arpit Tarang

我发现这是“设施选址问题”。但是，他们针对2D问题有复杂的算法...而我的只有1D。能帮忙吗？ - Arpit Tarang

无所谓。你仍然有距离，只是在一个维度上。 - Grembo

Answer 2

这条笔直的公路使得这成为一项动态规划的练习，从公路左侧向右侧工作。部分解决方案可以通过最右边仓库的位置和放置的仓库数量来描述。部分解决方案的成本将是到最近仓库的总距离（对于固定的k最小化，这与最小化平均值相同），或者到目前为止最接近仓库的最大距离。

在每个阶段，您已经计算出了左侧N个节点的答案，并按使用的仓库数量和最右侧仓库的位置进行索引 - 您只需要保存最佳成本。现在考虑下一个节点，并使用您为N个节点存储的答案以加快速度，计算N+1个节点和所有可能的k和最右侧仓库的最佳解决方案。一旦您计算出覆盖所有节点的最佳成本解决方案，您就知道其最右侧仓库的位置，这给您一个仓库的位置。返回具有该仓库作为最右侧节点的解决方案，并找出该解决方案基于哪个解决方案。这给您更多的最右侧仓库 - 因此，您可以回溯到最佳解决方案的所有仓库的位置。

我往往会算错解决这个问题的成本，但是对于N个关节和k个仓库的放置，您需要走N步，每一步都基于考虑不超过Nk个先前的解决方案，因此我认为成本是kN^2。

- mcdowella

---

现在考虑下一个关节，并计算出N+1个关节和所有可能的k值和最右侧仓库的最佳解决方案，使用您已经存储的N个关节的答案来加快速度。 请问您能否给出（至少）一个提示如何完成这个任务？ - Arpit Tarang

基本想法是，对于一个给定的点，最好的答案可以描述为“在这个点放置一个仓库，然后使用左侧第4个点的答案来确定其他仓库的位置”——但通常会有一些细节问题需要解决，这些问题会因具体问题而异。如果你不熟悉动态规划，请查看 http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html 上的前两个例子——或搜索其他教程。 - mcdowella