C++动态规划
2010-11-16 13:05:18 来源:WEB开发网核心提示:给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,C++动态规划(3),称Z是序列X和Y的公共子序列,问题表述:给定2个序列X={x1,x2,…,xm}和Y = {y1,y2,…,yn},用2行的数组空间就可以计算出最长公共子序列的长度,进一步的分析还可将空间需求减至O(min
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
问题表述:给定2个序列X={x1,x2,…,xm}和Y = {y1,y2,…,yn},找出X和Y的最长公共子序列。
最长公共子序列的结构
设序列X = {x1,x2,…,xm}和Y = {y1,y2,…,yn}的最长公共子序列为Z = {z1,z2,…,zk} ,则
(1)若xm = yn,则zk = xm = yn,且z(k-1)是x(m-1)和y(n-1)的最长公共子序列。
(2)若xm != yn且zk != xm,则Z是x(m-1)和Y的最长公共子序列。
(3)若xm != yn且zk != yn,则Z是X和y(n-1)的最长公共子序列。
由此可见,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此,最长公共子序列问题具有最优子结构性质。
子问题的递归结构
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yi的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}。当i = 0或j = 0时,空序列是Xi和Yj的最长公共子序列。故此时C[i][j] = 0。其它情况下,由最优子结构性质可建立递归关系如下:
由于在所考虑的子问题空间中,总共有θ(mn)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率
计算最优值和构造最长公共子序列(见源码)
实现:
/* 主题:最长公共子序列* 作者:chinazhangjie* 邮箱:chinajiezhang@gmail.com* 开发语言:C++* 开发环境:Microsoft Visual Studio 2008* 时间: 2010.11.14*/#include <iostream>#include <vector>using namespace std ;// longest common sequenceclass LonComSequence{public: typedef vector<vector<int> > LCS_Type ; typedef vector<vector<int> > MarkType ;public: LonComSequence (const vector<char>& vSeq1, const vector<char>& vSeq2) : mc_nEqual (1), mc_nSq1move(2), mc_nSq2move(3) { m_vSeq1 = vSeq1 ; m_vSeq2 = vSeq2 ; m_nLen1 = vSeq1.size() ; m_nLen2 = vSeq2.size() ; // 初始化最长公共子序列的长度 m_lcsLen.resize (m_nLen1 + 1) ; m_mtMark.resize (m_nLen1 + 1) ; for (int i = 0; i < m_nLen1 + 1; ++ i) { m_lcsLen[i].resize (m_nLen2 + 1) ; m_mtMark[i].resize (m_nLen2 + 1) ; } } // 计算最长公共子序列的长度 int calLcsLength () { for (int i = 1; i <= m_nLen1; ++ i) { m_lcsLen[i][0] = 0 ; // 序列二的长度为0,公共子序列的长度为0 } for (int i = 1; i <= m_nLen2; ++ i) { m_lcsLen[0][i] = 0 ; // 序列一的长度为0,公共子序列的长度为0 } for (int i = 0; i < m_nLen1; ++ i) { for (int j = 0; j < m_nLen2; ++ j) { if (m_vSeq1[i] == m_vSeq2[j]) { m_lcsLen[i+1][j+1] = m_lcsLen[i][j] + 1 ; m_mtMark[i+1][j+1] = mc_nEqual ; } else if (m_lcsLen[i][j+1] >= m_lcsLen[i+1][j]) { m_lcsLen[i+1][j+1] = m_lcsLen[i][j+1] ; m_mtMark[i+1][j+1] = mc_nSq1move ; } else { m_lcsLen[i+1][j+1] = m_lcsLen[i+1][j] ; m_mtMark[i+1][j+1] = mc_nSq2move ; } } } return m_lcsLen[m_nLen1][m_nLen2] ; } // 构造最长公共子序列 void LCS() { cout << "LCS is : " ; __LCS(m_nLen1, m_nLen2); cout << endl ; }private: void __LCS (int i, int j) { if (i == 0 || j == 0) { return ; } if (m_mtMark[i][j] == mc_nEqual) { __LCS (i - 1, j - 1) ; cout << m_vSeq1[i - 1] << " " ; } else if (m_mtMark[i][j] == mc_nSq1move) { __LCS (i - 1, j) ; } else { __LCS (i, j - 1) ; } }private: vector<char> m_vSeq1 ; // 序列一 vector<char> m_vSeq2 ; // 序列二 int m_nLen1 ; // 序列一的长度 int m_nLen2 ; // 序列二的长度 LCS_Type m_lcsLen ; // 最长公共子序列的长度 MarkType m_mtMark ; // 记录m_lcsLen const int mc_nEqual ; // 相等的标志 const int mc_nSq1move ; // 序列一左移的标志 const int mc_nSq2move ; // 序列二左移的标志} ;int main(){ vector<char> s1 ; s1.push_back ('A') ; s1.push_back ('B') ; s1.push_back ('C') ; s1.push_back ('D') ; s1.push_back ('E') ; s1.push_back ('F') ; vector<char> s2 ; s2.push_back ('B') ; s2.push_back ('D') ; s2.push_back ('F') ; s2.push_back ('G') ; s2.push_back ('H') ; LonComSequence lcs(s1, s2) ; cout << lcs.calLcsLength () << endl ; lcs.LCS(); return 0 ;}
算法的改进
在算法lcsLength和lcs中,可进一步将数组b省去。事实上,数组元素c[i][j]的值仅由c[i-1][j-1],c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j],可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1],c[i-1][j]和c[i][j-1]中哪一个值所确定的。
如果只需要计算最长公共子序列的长度,则算法的空间需求可大大减少。事实上,在计算c[i][j]时,只用到数组c的第i行和第i-1行。因此,用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。
实例三、最大子段和
问题表述
n个数(可能是负数)组成的序列a1,a2,…an.求该序列
例如: 序列(-2,11,-4,13,-5,-2) ,最大子段和:
[]
更多精彩
赞助商链接