交叉匹配.pptVIP

交叉匹配 问题描述 现有两行正整数。如果第一行中有一个数和第二行中的一个数相同，都为r，则我们可以将这两个数用线段连起来。称这条线段为r－匹配线段。例如下图就显示了一条3 匹配线段和一条2匹配线段。 我们想要对于给定的输入，找到画出最多的匹配线段的方式，使得： 1. 每条 a 匹配线段恰好和一条 b匹配线段相交，且 a≠b，a, b指代任何值，并非特定值。 2. 不存在两条线段都从一个数出发。 写一个程序，对于给定的输入数据，计算出匹配线段的最多个数。 * 分析 这是一个多次动态规划问题。 设这两行数分别保存在 a[n]和b[m]中。用 f(i, j)表示如下图所示的两行数据，可以画出的最多的匹配线段数。 a[1] a[2] … A[i] b[1] b[2] … B[j] 对于这个状态的求解，可以分如下几种情况讨论： 1. 没有从a[i]出发的匹配线段。如下图，这种情况的解即为f(i – 1, j) 2. 没有从b[j]出发的匹配线段。如下图，这种情况的即为f(i, j – 1) 3. a[i]和 b[j]处，各引出一条匹配线段，这时必须a[i]≠b[j]。设 a[i] = b[v]，b[j] = a[u]。从a[i]向 b[v]，b[j]向a[u]各引一条匹配线段，这两条线段必然相交。这种情况的解即为 f(u – 1, v – 1) + 2 * 显然，f(i, j)就是上面三种情况中的最优值。因此，我们可以列出状态转移方程： 其中 a[i]=b[v]且1≤v＜j b[j]=a[u]且1≤u＜i 该算法的复杂度看上去是 O((nm)2)，因为一共有i, j, u, v这四个变量需要循环。这个复 杂度的算法在时间上是无法承受的。 从下图可以看出，如果存在 a[u’] = b[j]， 且 u u’ i，则用b[j]向 a[u’]的匹配线段，代替 b[j]向 a[u]的匹配线段，所得到的解不会变差。因此，u 的选择是越靠后越好。同理，v 的选择也是越靠后越好。 * 由此，可以得到状态转移方程： 其中 a[i]=b[v]，且不存在v’，使得v ＜v’ ＜j，a[i]=b[v’] b[j]=a[u]，且不存在u’，使得v ＜u’ ＜i，b[j]=a[u’] 我们可以看到，对于确定的 i 和 j，相应的 u 和 v 的值也是确定的，这些值可以预先求出。而求法也是利用动态规划。设相应 u和 v的值分别为u[i, j]和 v[i, j]。易知， * 这样，原动态转移方程可变为： 该算法需要保存f，u，v等数组，空间复杂度是O(nm)。由规划方程可知，计算f，u，v的时间复杂度是 O(nm)，因此总的时间复杂度也还是 O(nm)。 在这个例子中，我们很顺利地得到了一个动态转移方程，但这个算法的时间复杂度却无法让人接受。进一步的分析表明，决策变量的取值有很强的约束条件，于是通过第二次动态规划独立的求出决策变量的取值，从而提高了算法的效率。 * 参考程序： const max = 100; var k, p, q, n, m: integer; u, v, f: array[- 1 .. max, - 1 .. max] of integer; a, b: array[0 .. max] of integer; begin readln(n, m); for k := 1 to n do read(a[k]); for k := 1 to m do read(b[k]); for p := 1 to n do for q := 1 to m do begin if a[p - 1] = b[q] then u[p, q] := p - 1 else u[p, q] := u[p - 1, q]; if a[p] = b[q - 1] then v[p, q] := q - 1 else v[p, q] := v[p, q - 1]; end; for p := 1 to n do for q := 1 to m do begin if a[p] = b[q] then k := 0 else k := f[u[p, q] - 1, v[p, q] - 1] + 2; if f[p - 1, q] k then k := f[p - 1, q]; if f[p, q - 1] k then k := f[p, q - 1]; f[