两组可能不同尺寸之间的距离测量

Question

我有2组整数,A和B,不一定大小相同.根据我的需要,我将每个2个元素a和b(整数)之间的距离变为公正abs(a-b).

我定义了两组之间的距离如下:

1. 如果集合具有相同的大小,则最小化所有对[a,b](a中的a和b中的a和b)的距离之和,最小化所有可能的"对分区"(有n个可能的分区).
2. 如果这些集合的大小不同,那么假设大小为m的A和大小为n的B,其中m <n,则最小化距离(1)在大小为m的B的所有子集上的距离.

我的问题是,根据上面的定义,以下算法(只是一个直观的猜测)给出了正确的答案.

• 构造一个D大小矩阵m X n,用D(i,j) = abs(A(i)-B(j))
• 找到最小元素D,累积它,并删除该元素的行和列.累计下一个最小的条目,并继续累积,直到删除所有行和列.

例如,如果A={0,1,4}和B={3,4},那么D(使用上面和左边的元素):

3 4

0 3 4

1 2 3

4 1 0

而距离是0 + 2 = 2,从配对来4用4,并3用1.

Answer 1

请注意,此问题有时被称为滑雪板和滑雪者问题,其中您有n个滑雪板和m个不同长度和高度的滑雪者.目标是将滑雪板与滑雪者相匹配,以便最大限度地减少高度和滑雪板长度之间的差异总和.

要解决这个问题,你可以使用最小权重的二分匹配,这需要O(n ^ 3)的时间.

更好的是,使用下面的简单动态编程算法,您可以使用O(n)额外内存实现O(n ^ 2)时间.

最理想的是,如果已经使用本文中描述的算法对点进行了排序,则可以在线性时间内解决问题.

O(n ^ 2)动态规划算法:

if (size(B) > size(A))
  swap(A, B);
sort(A);
sort(B);
opt = array(size(B));
nopt = array(size(B));
for (i = 0; i < size(B); i++)
  opt[i] = abs(A[0] - B[i]);
for (i = 1; i < size(A); i++) {
  fill(nopt, infinity);
  for (j = 1; j < size(B); j++) {
    nopt[j] = min(nopt[j - 1], opt[j - 1] + abs(A[i] - B[j]));
  swap(opt, nopt);
}
return opt[size(B) - 1];

在上面i的外for循环的每次迭代之后,opt[j]包含{A[0],..., A[i]}使用元素的最佳解匹配{B[0],..., B[j]}.

该算法的正确性依赖于以下事实:在任何最佳匹配中,如果a1与b1匹配,则a2与b2匹配,a1 <a2,则b1 <= b2.