【Rosalind】Longest Increasing Subsequence – 动态规划算法(Dynamic Programming)初探

Rosalind习题:Longest Increasing Subsequence(题目ID:LGIS)

今天突然发现自己的Rosalind的生物信息学的习题已经做到一个瓶颈了,感觉从今天的这道题开始难度开始大了,这种难度不是体现在需要多么高的代码水平,而是开始更加强调算法了。我自己看了一下,也很真实,习题列表里从这一题开始的“成功解题次数”开始出现了一个很大的减少:

感觉很多刷题的人是不是做到这里就做不下去了……

之间其实除了做题之外,对于自己的数据处理里也是用了很多自己写的代码,做的过程中发现一个事情,之前写的很多代码因为只是为了实现功能来对题目给的测试数据有效,实际上测试数据都是比较小的,很多我跑测试数据觉得没问题的代码,一旦面临真实的数据,会出现非常慢的问题。于是我开始思考关于代码速度的问题,拿生物信息学里必须会用到FASTA和FASTQ数据来说,这些数据动不动就是成百万上千行的,很多时候我写的单纯的递归、遍历的方法会导致大量的重复计算,占用大量内存和计算资源的情况下还消耗了很多不必要的时候。这时候就需要很多算法的支持。

这两天做的这道题是关于一个编程中的经典问题——最长递增子序列(Longest Increasing Subsequence,LIS)的。先上题目:

Problem

A subsequence of a permutation is a collection of elements of the permutation in the order that they appear. For example, (5, 3, 4) is a subsequence of (5, 1, 3, 4, 2).

A subsequence is increasing if the elements of the subsequence increase, and decreasing if the elements decrease. For example, given the permutation (8, 2, 1, 6, 5, 7, 4, 3, 9), an increasing subsequence is (2, 6, 7, 9), and a decreasing subsequence is (8, 6, 5, 4, 3). You may verify that these two subsequences are as long as possible.

Given: A positive integer n≤10000 followed by a permutation π of length n.

Return: A longest increasing subsequence of π, followed by a longest decreasing subsequence of π.

Sample Dataset

Sample Output

思路

这道题目意思非常明确,就是给定一个有顺序的数组,返回其最长的递增和递减子序列,这里的子序列指的是序列的元素先后关系必须和原数组一致,但是可以不是相连的。

我先想清楚递增的情况吧,拿题目给的这个数组来举例子吧:(8 2 1 6 5 7 4 3 9)。我可以使用遍历的方法:

1) 拿到第一个元素8作为开头,找到后面比他大的元素9,组成(8,9),然后9后面没有比它还大的数了,结束;

2) 拿到第二个元素2作为开头,找到后面比他大的元素,有很多个(6 5 7 4 3 9),分别把这些数字和2组成新数组,再找这些数字后面比这些数字还大的组成长度为3的新数组……直到最后一个数后面没有比它还大的数。因为这里出现了分支,所以会得到很多个待选数组,我们再选一个长度最长的就结束;

3) 拿到第三个元素1作为开头,重复上述的步骤;

4) 最终把所有的待选数组都放在一块比长度。

很容易发现这种方法是严重浪费了计算资源的。为什么呢,举个例子,我们用1作为开头,很容易看出有这样一个子序列:(1,6,7,9),但是在下一步在用6作为开头的时候,也会得到(6,7,9)这个数组,但是这个数组明显不可能是我们最终要得到的LIS,因为它在长度上已经输给了前面那个。

怎么改进这个问题呢,就是说我需要在每出现一个在前面已经出现结果的基础上更好的结果的时候将前面的结果覆盖。动态规划(Dynamic Programming)方法就能很好的解决这个问题。

我刚还在想咋写这个引入,DP算法对我来说也是新鲜事物,我还是直接引用一下前人写好的:

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。

——维基百科

在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策问题。在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化的过程为动态规划方法。

——百度百科

我不太清楚该怎么介绍动态规划整个过程,接下来结合这道题来讲一下它的过程。

获得子序列的动态规划数组

我还是以这个数组作为例子:perm = [8, 2, 1, 6, 5, 7, 4, 3, 9]

我从第一个元素开始数,它和它前面的元素能组成的最长的递增子序列(的长度)。下面是步骤:

1) 对于第一个元素8,它前面没有元素了,它能组成的LIS就是它本身[8],长度为1,所以我们设置8对应的动态规划数组元素为1;

2) 对于第二个元素2,它前面的元素没有比它小的,它能组成的LIS也是它本身,长度为1,所以2对应的动态规划数组元素也是1;

3) 第三个元素1面临的情况和2)中的2是一样的,其动态规划数组元素也是1;

4) 对于第四个元素6,前面终于有比它小的元素2和1了,它分别可以组成[2,6]和[1,6]两个LIS,长度都为2,所以对应的动态规划数组元素为2;

5) 对于第五个元素5,它的情况和4)中的6是一样的,它的动态规划数组元素也是2;

6) 对于第六个元素7,要开始注意,它前面比它小的数有2,1,6和5,那么7肯定是和已经能组成更长LIS的数(6和5)来组合出新的长度的LIS,也就是说它的动态规划数组元素应该是6和5对应的元素(2)加上自己本身这个元素的长度(1)也就等于3;

7) 对于第七个元素4,前面比它小的元素2和1对应的动态规划数组元素都是1,所以第七个元素的动态规划数组元素是2;

8) 对于第八个元素3,它的情况和7)中的4是一样的,动态规划数组元素是2;

9) 对于第九个元素9,它比前面的数都要大,它可以放在前面所有数能组成的LIS后面组成新的LIS,为了追求更长的LIS,我们把它放在已有LIS最长的后面,也就是第6)步中得到的后面,它的动态规划数组元素应该是7对应的元素(3)和自己本身元素长度(1)的加和4。

至此,这一次动态规划过程结束了。实际上,动态规划数组中的元素指的是什么——是截止到当前元素,能够组成的最长递增子序列的最大长度

为了方便进一步说清楚和写代码时方便想清楚这件事,我画了这样一个图:

列表permutation是给定的序列,dp是动态规划数组。

至于最长递减子序列的dp数组我也写在下面了,感兴趣的读者可以自己试着推一下。

那么怎么找到最长递增子序列本身呢,我们首先要肯定一个事实,这个最长递增子序列很可能并不唯一,所以我想了个办法输出了一条:按顺序观察permutationdp数组,每次dp数组首次出现新高(除了dp[0])的时候就是新加入了一个可能组成最终LIS的元素。按这个规律输出序列就可以了。

到这里,我觉得我对这个问题的理解就讲完了,读者如果还想对动态规划算法有更多了解也可以自行上网搜索相关的材料阅读。

代码

总结

随着熟悉编程语法后,发现对于算法的理解的重要性要大于编程语法本身,只有对一个实际问题有了思路才能更好地用代码来实现,就好比学会了很多英语单词语法,也得给定具体的一个描述对象和描述方法才能言之有物。

其实LIS的长度只是动态规划算法的一个应用而已,它的更多内容以后如果有机会还是会继续探索的,现在还是以练习代码为主要目的,在这个过程中熟悉接触算法,以后遇到相关问题知道有一个算法可以试试看就行了。网上有很多对于这些算法的专业大佬讲的内容,读者感兴趣不妨自行搜索。

Share this page if you like this post:)