7

您有一组n 个对象，其中给出了整数位置。一组对象是同一位置的一组对象（不一定是该位置的所有对象：单个位置可能有多个组）。对象可以向左或向右移动，目标是移动这些对象以形成k个组，并以移动的最小距离进行。

例如：

  • 初始位置为 [4,4,7]，k = 3：最小成本为 0。
  • [4,4,7] 和k = 2：最小成本为 0
  • [1,2,5,7] 和k = 2：最小成本为 1 + 2 = 3

我一直在尝试使用贪婪的方法（通过计算哪个动作最短），但这不起作用，因为每一步都涉及两个可以以任一方式移动的元素。我还不能制定动态编程方法，但我正在努力。

4

4 回答 4

4

这个问题是k-medians 问题的一维实例，可以表述如下。给定一组点 x_1...x_n，将这些点划分为 k 个集合 S_1...S_k 并选择 k 个位置 y_1...y_k，以使 |x_i - y_f(i)| 的所有 x_i 的总和最小化。 ，其中 y_f(i) 是 x_i 被分配到的集合对应的位置。

由于中位数是绝对距离的总体最小值（即 L_1 范数），因此每个位置 y_j 将是相应集合 S_j 中元素 x 的中位数（因此称为 k-medians）。由于您正在查看整数值，因此如果 S_j 包含偶数个元素，则中位数可能不是整数，但在这种情况下，选择高于或低于中位数的下一个整数将给出相同的总和绝对距离。

解决 k 中位数（以及相关且更常见的 k 均值问题）的标准启发式方法是迭代的，但这并不能保证产生最佳或什至好的解决方案。解决一般度量空间的 k-median 问题是 NP-hard，找到 k-median 的有效近似是一个开放的研究问题。例如，谷歌搜索“k-medians approximation”会导致一堆给出近似方案的论文。 http://www.cis.upenn.edu/~sudipto/mypapers/kmedian_jcss.pdf http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arr-clustering.pdf

在一维中，事情变得更容易，您可以使用动态编程方法。本文描述了相关一维 k-means 问题的 DP 解决方案，R 中的源代码可在此处获得。有关详细信息，请参阅论文，但该想法与@SajalJain 提出的想法基本相同，并且可以很容易地适应解决 k-medians 问题而不是 k-means。对于 j<=k 和 m<=n，令 D(j,m) 表示 x_1...x_m 的最优 j 中位数解的成本，其中假设 x_i 是有序的。我们有复发

D(j,m) = min (D(j-1,q) + Cost(x_{q+1},...,x_m)

其中 q 的范围从 j-1 到 m-1 并且Cost等于距中位数的绝对距离之和。对于 的天真 O(n) 实现Cost，这将产生整个问题的 O(n^3k) DP 解决方案。但是，这可以改进为 O(n^2k)，因为 Cost 可以在恒定时间内更新，而不是每次都从头开始计算，使用以下事实：对于排序序列：

Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_1...x_h)-x_1   if h is odd
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_2...x_h)-x_1   if h is even

有关更多详细信息，请参阅文章。除了 Cost 函数的更新不同之外，k-median 的实现与 k-means 的实现相同。 http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf

于 2013-11-05T21:30:55.457 回答
1

据我了解，问题是：

我们在一条线上有 n 个点。我们想在线上放置 k 个位置。我称它们为目的地。将n个点中的每一个移动到k个目的地之一，使距离之和最小。我把这个总和称为总成本。目的地可以重叠。

一个明显的事实是，对于每个点，我们应该在左侧寻找最近的目的地，在右侧寻找最近的目的地并选择最近的目的地。

另一个重要的事实是所有目的地都应该在点上。因为我们可以在不增加总距离的情况下将它们在线上向右或向左移动以到达一个点。

通过这些事实考虑以下 DP 解决方案：

DP[i][j] 表示第一个 i 点所需的最小总成本，此时我们只能使用 j 个目的地，并且必须在第 i 个点上放置一个目的地。

计算 DP[i][j] 将目的地固定在第 i 个点之前（我们有 i 个选择），并为每个选择（例如第 k 个点）计算第 i 个点和点之间的点所需的距离添加的新点（第 k 个点）。将其与 DP[k][j - 1] 相加并找到所有 k 的最小值。

初始状态（例如 j = 1）和最终答案的计算留作练习！

于 2012-09-12T14:00:06.330 回答
0

让我们看看k=1。

对于 k=1 和 n 奇数，所有点都应该移动到中心点。对于 k=1 和 n 偶数，所有点都应移动到中心点或它们之间的任何点。我所说的“中心”是指两侧的点数，即中位数。

您可以看到这一点，因为如果您选择一个目标点 x，其右侧的点多于左侧的点，那么 x 右侧的新目标 1 将导致成本降低（除非恰好多一个点）右比左，目标点是一个点，在这种情况下，n 是偶数，目标在两个中心点上/之间）。

如果您的点已经排序，这是一个 O(1) 操作。如果不是，我相信它是 O(n) （通过顺序统计算法）。

一旦你找到了所有点都移动到的位置，找到成本是 O(n)。

因此，无论这些点是否已排序，这都是 O(n)。

于 2013-11-05T21:27:45.710 回答
0

任务 0 - 以非递减顺序对对象的位置进行排序

让我们定义'center'它所在的对象的位置shifted to.

现在我们有两个观察结果；

  1. For N positions the 'center' would be the position which is nearest to the mean of these N positions.例如，让 1,3,6,10 为位置。然后均值 = 5。最近的位置是 6。因此这些元素的中心是 6。这为我们提供了当所有元素需要分组为 1 组时移动成本最低的位置。

  2. 让 N 个位置“最优地”分成 K 个组。When N+1 th object is added, 那么它只会干扰第 K 组，即first K-1 groups will remain unchanged.

根据这些观察，我们构建了一种动态规划方法。

Let Cost[i][k] and Center[i][k] be two 2D arrays. 
Cost[i][k] = minimum cost when first 'i' objects are partitioned into 'k' groups
Center[i][k] stores the center of the 'i-th' object when Cost[i][k] is computed.

Let {L} be the elements from i-L,i-L+1,..i-1 which have the same center.
(Center[i-L][k] = Center[i-L+1][k] = ... = Center[i-1][k])
这些是在计算第 i 个元素时需要考虑的唯一对象（来自观察 2）

现在

Cost[i][k] will be 
min(Cost[i-1][k-1] , Cost[i-L-1][k-1] + computecost(i-L, i-L+1, ... ,i))
Update Center[i-L ... i][k]

通过找到中心（来自观察 1）可以很容易地找到 computecost()

时间复杂度：

Sorting O(NlogN)
Total Cost Computation Matrix = Total elements * Computecost = O(NK * N)
Total = O(NlogN + N*NK) = O(N*NK)
于 2012-09-13T09:05:04.510 回答