我有两组整数,A 和 B,大小不一定相同。根据我的需要,我将每 2 个元素 a 和 b(整数)之间的距离设为 abs(a-b)
。
我定义两组之间的距离如下:
- 如果集合的大小相同,则最小化所有对 [a,b](a 与 A 和 b 与 B)的距离之和,最小化所有可能的“对分区”(有 n!可能的分区) ).
- 如果集合的大小不同,假设 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
。
最佳答案
请注意,此问题有时称为滑雪板和滑雪者问题,其中您有 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。
关于algorithm - 两组可能不同大小之间的距离度量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4441733/