交叉匹配.pptVIP

  1. 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
  2. 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  3. 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  4. 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  5. 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  6. 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  7. 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
交叉匹配

交叉匹配 问题描述 现有两行正整数。如果第一行中有一个数和第二行中的一个数相同,都为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[

文档评论(0)

rovend + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档