经常会遇到复杂问题不能简单地分解成几个子问题综述

发布时间：2023-03-25 07:16:12 来源：文档文库

小中大

字号：

手机查看

经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。
【问题】求两字符序列的最长公共字符子序列问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字
符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列
x=“x0,x1,…，xm-1”，序列Y“yO,y1,…，yk-1”是X的子序列，存在X的一个严格递增下标序列，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
给定两个序列A和B,称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列
A和B的最长公共子序列。
如采用列举A的所有子序列，并一一检查其是否又是B的子序列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。考虑最长公共子序列问题如何分解成子问题，设质：（1）“aOa1
A=“aO,al,…，am-1”,
B=“bO,bl,…，bm-1”，并Z=“zO,z1,…，zk-1”为它们的最长公共子序列。不难证
明有以下性如果
am-1=bn-1…am-2”和“bOb1…
如果am-1!=bn-1…am-2”和“bOb1…
如果
am-1!=bn-1则
zk-1=am-1=bn-1则若
zk-1!=am-1且“zOz1
…zk-2”是

bn-2”的一个最长公共子序列；
（2）“aa1
蕴涵“zOz1
…

zk-1”是

Obn-1”的一个最长公共子序列；
（
3）a“O则若
zk-1!=bn-1蕴涵“zOz1
…
zk-1”…am-1”和“bOb1…bn-2”的一个最长公共子序列。
这样在找A和B的公共子序列时如有am-1=bn-1则进一步解决一个子问题找
a1a1O1!=bn-1是

“a
…am-2”和“bOb1…则要解决两个子问题找出
bm-2”的一个最长公共子序列；如果
am-“aOa1…am-2”和“bOb1…bn-1”的
一个最长公共子序列和找出“aQa1，…,am-1”和“bQb1,…,bn-2”的一个最长公共
子序列再取两者中较长者作为A和B的最长公共子序列。
定义c[i][j]为序列“aO,a1,…,ai-2”和“bO,b1,…,bj-1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下：（1）c[i][j]=O（2）
c[i][j]=c[i-1][j-1]+1如果i=O或j=O；
如果Ij>O且
a[i-1]=b[j-1]c[i-1][j]）如果Ij>O且
a[i-1]!=b[j-1]；
。
c[i][j]的产生仅依赖于
（3）c[i][j]=max（c[i][j-1]按此算式可写出计算两个序列的最长公共子序列的长度函数。由于
c[i-1][j-1]、c[i-1][j]和c[i][j-1]故可以从c[m][n]开始跟踪c[i][j]的产生过程
逆向构造出最长公共子序列。细节见程序。
#include#include#defineN1OOchara[N],b[N],str[N];
{intm=strlen(a,n=strlen(b,i,j;for(i=0;i<=m;i++c[i][0]=0;for(i=0;i<=n;i++for(i=1;i<=m;i++for(j=1;j<=m;j++if(a[i-1]==b[j-1]c[i][j]=c[i-1][j-1]+1;elseif(c[i-1][j]>=c[i][j-1]c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];returnc[m][n];}c[0][i]=0;
char*buile_lcs(char{intk,i=strlen(a,s[],char*a,char*bj=strlen(b;k=lcs_len(a,b,c;s[k]='0';while(k>0if(c[i][j]==c[i-1][j]elseif(c[i][j]==c[i][j-1]else{s[--k]=a[i-1];i--;j--;}i--;
returns;}
voidmain({printf(“Entertwostring(<%dn”,N;scanf(“%s%s”,a,b;printf(“LCS=%ns”,build_lcs(str,a,b;}
1、动态规划的适用条件
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
(1最优化原理(最优子结构性质最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
图2例如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径
J'是B到C的最优路径，则A到
C的路线取I和J比I和J更优，矛盾。从而证明J必是B到C的最优路径。
最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。
（2）无后向性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
（3）子问题的重叠性动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承
受，而搜索算法在时间上却无法承

本文来源：https://www.2haoxitong.net/k/doc/8387edd77a3e0912a21614791711cc7930b77830.html