算法分析与设计——最长公共子序列(LCS)问题
对于算法中关于,最长公共子序列(LCS)可能大家在学习的过程中刚刚接触的时候会出现这样的问题,查了很多资料之后发现还是不会,在那之后,老师在黑板上随便给了一个例题如下所示:
然后告诉你有这么个公式:
C【i】【j】 = (C【i-1】,【j-1】)+1
= 当 i=0 时或者 j = 0 时 有 C【i】【j】=0
= Max(C【i】【j-1】,C【i-1】【j】)中的最大值问题
可是看了半天还是不会,怎么也看不懂左右箭头表示什么,怎么进行操作
所以接下来是我自己整理的解决问题如下:
首先:对应 的其实Max(C【i】【j-1】,C【i-1】【j】)公式中的 这句话等价于比较一个类似“三角形”的数据,
去比较你所要填充的左面数据和正对应的上面的数据的大小, 不过!!!!这个前提条件是 C【i】!=C【j】
举个很简单的例子:我现在假设要填充C【2】【2】这个数值的大小 首先要看 i=2 和 j=2这两个是否是一样的,如果不是继续执行下面的操作,比较左面和上面正对着的数值的大小,发现左面是1,右面是0, 又因为1>0 所以Max=1 所以C【2】【2】=1,在这之后箭头的指向则根据你所选择的那个较大的数值方向一致,故指向1,箭头指向为向左
第二个例子:假设我要填C【4】【5】的数值,发现 C【i】与C【j】字母相同,这时候箭头指向,只要指向斜对角线即可,至于数字= “斜对角线的数值+1” !!!!!!!注意的是该条件成立的条件是必须C【i】= C【j】
当然对于同学可能认为箭头的指向对于左箭头和上箭头什么时候我用哪个,这个不必纠结,由于一个最长子序列的问题,可能最好的路径不只是一条,所以会有分叉的现象产生,也就有了多个解的结果,这是正常现象, 对于大家在查阅资料的时候编程的时候才用得到,即:
(1)把斜对角线箭头=0,左箭头=1,上箭头=2;
(2)把斜对角线箭头=0,左箭头=2,上箭头=1;
这个不用纠结,在考试中只要画对一种即可。
下面大家尝试一下另一个例题:
Yj | B | C | D | E | A | B | C | |
Xi | ||||||||
C | ||||||||
B | ||||||||
D | ||||||||
A | ||||||||
B |
可以用这个习题进行一下练习(答案我会在最后给出,也是我自己做的,不对的话麻烦大家记得指出来)
当然,最后呢,这也是我自己在查了很多资料加上自己对该问题的理解写出来的文章,欢迎大家的交流和评价,喜欢的话记得点个关注哦,我也会定时的更新软件相关的内容的,谢谢您的理解。
拓展练习,例题答案: