algorithm - 两组可能不同大小之间的距离度量

Question

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

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

1. 如果集合的大小相同，则最小化所有对 [a,b](a 与 A 和 b 与 B)的距离之和，最小化所有可能的“对分区”(有 n!可能的分区) ).
2. 如果集合的大小不同，假设 A 的大小为 m，B 的大小为 n，其中 m < n，则在 B 的所有大小为 m 的子集上最小化与 (1) 的距离。

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

• 构造一个矩阵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) 的时间。

最佳情况下，如果已使用此 paper 中描述的算法对点进行排序，则可以在线性时间内解决问题。 .

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];

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

该算法的正确性依赖于这样一个事实:在任何最优匹配中，如果a1与b1匹配，a2与b2匹配，且a1 < a2，则b1 <= b2。