为什么求解“最长公共子序列”(LCS)需要递归函数?——从“公共子串”的角度来分析问题(附程序和VB源文件)

作者在 2022-12-09 16:57:15 发布以下内容
    我们知道:公共子序列是由一个个公共子串顺序连接而成的。为了求“最长公共子序列”,可以把字符串中的字分成2类:一类是要留下的(组成公共子串),另一类是要出列的。我们可以编程,把字符串(我取下面一行,txt2)从头到尾逐字鉴定该留还是该出列。
别看字符串五花八门、长长短短,鉴定起来却只有4种情况。而且并不是每一种都需要调用递归函数的。
我在【图一】中的每个公共子串的右面画一根蓝色竖线,表示原公共子串结束,新公共子串开始。
(下面所说的“情况一、情况二”,都可以用我们熟悉的、简单的编程语句来完成的。)
情况一:看第1个字“他”,上下2个字一样,“他”就留下,这情况我称为①。后面的字,只要还是在这个公共子串里,都可以这样来判断。
情况二:看第2根蓝色竖线后面的“啦”,它跟“了”不同,第1段公共子串结束。我们可以说,★所有的问题都是由公共子串结束引起的;所有的问题也只有1个:“谁是下一个公共子串的最优首字”。(引号里的14个字要多次用到,下文中用“F”来代替)“最优”什么意思?“最优”就是保证标题中的“最长”。
因为在“了”的右面再也找不到“啦”(我在程序里用Do 循环找),“啦”就出列。这情况我称为②。也不需要函数。
情况三:重点看下行第2条蓝线后面字“罗”,它与上面的“英”不同,却又能在“英白”的后面找到“罗”字,关键是“罗”左边的“英”能在下面“罗”的右面找到相同的“英”。这是“唯一问题”中的“唯一难点”。
★问:“罗”是不是“F”呢?或许“英”是的呢?★“是”还是“不是”的依据,就是能不能(在第2条蓝线后面全部的2个字符串)形成“最长公共子序列”。如果不是的话,“罗”就必须“出列”了。
这时必须要请“专家”(函数)了。这个专家有什么本事呢?它的工作就是★“求2个(首字一样的)字符串(字符串的末端就是整个字符串的末端)的最长公共子序列的字数”。我后面用(罗罗)、(英英)等来表示函数求出的值。
假定已经请到了“专家”。那么,解题的逻辑就很简单了。接下来的步骤和逻辑推理如下:
第一步,请“专家”(调用函数),计算(罗罗),(【图二】中是用2根粗红横线标出,我改用“(红红)”表示,更有代表性)。
第二步,用For循环顺序找到一对“英”、(一对“白”,假定可以找到),再请“专家”(调用函数)计算(英英)、(白白)……。我仿【图二】用(蓝蓝)来表示(英英)、(白白)……中的一个。
推理:  ★如果始终没有 “(蓝蓝)>(红红)”,那么“罗”就是“F”,“罗”留下,★这样的情况我称为③1。
        ★如果一旦有(蓝蓝),就是(英英)或(白白)>(罗罗),那么“罗”就不是“F”了,这个推理是显而易见的。这时,“罗”必须“出列”;★这样的情况我称为③2。
  (★想一想,这样的逻辑推理正确吗?关键是有了“最长”这个要求)
  下行字符串txt2里的每一个字,都可以根据这4种情况(①、②、③1、③2)从左到右,逐字来判断“去”还是“留”的。我在【图一】里每个字的下面都标出来了。
  关于“情况(①、②、③1、③2) ”。在我以前的博文中有比较详细的讲述。是很容易看懂的。
    回过头来说“专家”,“专家”的解题思路就是我上文所叙述的思路。那么问题来了:既然“专家”也是这样的解题思路,那么,它在遇到情况③的时候,也要请个“助手”了。这个“助手”的名字及构造与“专家”(它的“上级”)是一模一样的,也要请新“助手”……★这在很多地方称为“自己调用自己”,(其实说“调用它的拷贝”更恰当)。这就是“递归”的“递”了。如果这样无穷“递”下去,问题还能解决吗?
  仔细分析后发现,各个“助手”的工作内容会有很大的差别,关键是:最后总会迎来★“无需调用助手”、可以直接上交数据的那一刻(请读者试试分析最后一根蓝色竖线后面的2个字符串)。递归函数终归是可以开始“归”的。这样“上级”得到了“下级”传回的★数值(归),就可以继续工作而得到具体★数值,再交给自己的“上级”……,最后,邀请“专家”的那个程序(我们叫它“主程序”),就可以算出“最长公共子序列”的长度(字数)和“内容”了。
思考:前面的7个字(尤其是第5个字“,”),需要调用递归函数吗?为什么?下行字符串共19个字,只有“罗”字调用了递归函数,是吗?
几点说明:
1.程序主要由1个主程序和1个递归函数 LCS(a&,b&) 组成。这2部分的代码非常相似(★先看主过程的代码,后看函数的代码),因为它们的“任务”都是要“求出2个字符串的最长公共子序列”。主程序是对整个字符串(txt1、txt2、从头到尾,从左到右)进行求解。而递归函数是对“由主程序交代下来的两个部分的字符串”进行求解,且只求长度。交代下来的(参数)是:2个字符串的“首字”在整字符串txt1、txt2 中的位置(数值型数据)。而2个字符串的末端,分别都是 txt1 、txt2 的末端。(正因为如此,对太长的 txt1、txt2 求解会造成“(无响应)”)
2.两部分都有一个局部变量(名字一样,但是互不相干)Liu (留的音),它是因“情况③”引起的。当得到Liu=1时,表示判断结果是:这个字该“留”( ③1 ),它总是(下一个)公共子串的首字。当得到 Liu=0 时,表示判断结果是:这个字该“出列”( ③2 )。
3.为了减少读者的眼光在“文字”和“图片”之间反复跳转, 我在图片里加了文字说明,也有一些“推论”。其逻辑是否严密,敬请读者甄别。
4.★优化问题。如果每当需要计算“2个字符串的最长公共子序列的长度”时,就呼叫“助手”,“助手”还会呼叫“助手”……那工作量会“巨大”,因为这里有很多重复的计算。所以,这时应该先查一查★:“之前算过吗?有记录吗?”如果有的话,就不要呼叫“助手”了,直接拿来用就是了。(我用了一个“二维数组”---Zong()来记录),当元素的值不为零(大于零或者-1)时,表示这个元素已经算过了。反之,等于零时,要请“助手”(调用函数)。
5.大概是我的程序对“优化”做得不好,所以对于“长字符串”运算比较慢。我希望能得到帮助。
    实验结果:    (上传2组共4个文件。用其他编程语言编写的程序,也可以用它们来验证程序)
第一组:科学txt1.txt (約350字) ,科学txt2.txt (約350字),公共子序列长度是 327字(标准答案),时间 約5秒。
第二组:法txt1.txt  (約1400字),法txt2.txt (約700字),公共子序列长度是 661字(标准答案),时间 約7分钟。
  读者如果发现我这篇博文里有错误或者不妥,或者代码有错误和不妥,敬请指出,真诚感谢!如果有什么疑问,也请提出来,我会尽量解答。欢迎商榷和交流。
图一.png (上传于2022-12-09 16:57:15)
图一.png

图二.png (上传于2022-12-09 16:57:15)
图二.png


作者在 2022-12-09 18:07:44 补充以下内容
补充图片.png (上传于2022-12-09 18:07:44)
补充图片.png
作者在 2022-12-10 16:05:56 补充以下内容
在《情况三》这一段有一个错字,我在下面用红色背景标出。这个字应该是“英”字。
关键是“罗”左边的“英”能在下面“罗”的右面找到相同的。这是“唯一问题”中的“唯一难点”。】
改正的字,我在下面用绿色背景标出。
关键是“罗”左边的“英”能在下面“罗”的右面找到相同的。这是“唯一问题”中的“唯一难点”。】
作者在 2023-01-08 13:53:20 补充以下内容
2022-12-09 16:57:15 上传的 “OUT.rar” 有部分改动。现在重新上传文件:“LCS.rar”
默认分类 | 阅读 708 次
文章评论,共0条
游客请输入验证码
浏览77387次
文章分类