动态规划法的若干问题

《动态规划法的若干问题》由会员分享，可在线阅读，更多相关《动态规划法的若干问题（6页珍藏版）》请在金锄头文库上搜索。

1、八、动态规划法八、动态规划法经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单 地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时 会按问题规模呈幂级数增加。会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所 有子问题的解存于该数组中，这就是动态规划法所采用的基本

2、方法。以下先用实例说明动有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先用实例说明动 态规划方法的使用。态规划方法的使用。 【问题问题】 求两字符序列的最长公共字符子序列求两字符序列的最长公共字符子序列 问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字 符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列 X=“x0，x1，xm- 1”，序列，序列 Y=“y0，y1，yk-1”是是 X 的子序列，存在的子序

3、列，存在 X 的一个严格递增下标序列的一个严格递增下标序列 ，使得对所有的，使得对所有的 j=0，1，k-1，有，有 xij=yj。例如，。例如，X=“ABCBDAB”， Y=“BCDB”是是 X 的一个子序列。的一个子序列。 给定两个序列给定两个序列 A 和和 B，称序列，称序列 Z 是是 A 和和 B 的公共子序列，是指的公共子序列，是指 Z 同是同是 A 和和 B 的子序列。的子序列。 问题要求已知两序列问题要求已知两序列 A 和和 B 的最长公共子序列。的最长公共子序列。 如采用列举如采用列举 A 的所有子序列，并一一检查其是否又是的所有子序列，并一一检查其是否又是 B 的子序列，并随

4、时记录所发现的子的子序列，并随时记录所发现的子 序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。 考虑最长公共子序列问题如何分解成子问题，设考虑最长公共子序列问题如何分解成子问题，设 A=“a0，a1，am-1”， B=“b0，b1，bm-1”，并，并 Z=“z0，z1，zk-1”为它们的最长公共子序列。不难证明为它们的最长公共子序列。不难证明 有以下性质：有以下性质： （1） 如果如果 am-1=bn-1，则，则 zk-1=am-1=bn-1，且，且“z0，z1，zk-2”是是 “a0，a1，am-2”和和“b0，b1，bn

5、-2”的一个最长公共子序列；的一个最长公共子序列； （2） 如果如果 am-1!=bn-1，则若，则若 zk-1!=am-1，蕴涵，蕴涵“z0，z1，zk-1”是是 “a0，a1，am-2”和和“b0，b1，bn-1”的一个最长公共子序列；的一个最长公共子序列； （3） 如果如果 am-1!=bn-1，则若，则若 zk-1!=bn-1，蕴涵，蕴涵“z0，z1，zk-1”是是 “a0，a1，am-1”和和“b0，b1，bn-2”的一个最长公共子序列。的一个最长公共子序列。 这样，在找这样，在找 A 和和 B 的公共子序列时，如有的公共子序列时，如有 am-1=bn-1，则进一步解决一个子问题，找

6、，则进一步解决一个子问题，找 “a0，a1，am-2”和和“b0，b1，bm-2”的一个最长公共子序列；如果的一个最长公共子序列；如果 am-1!=bn-1， 则要解决两个子问题，找出则要解决两个子问题，找出“a0，a1，am-2”和和“b0，b1，bn-1”的一个最长公共子的一个最长公共子 序列和找出序列和找出“a0，a1，am-1”和和“b0，b1，bn-2”的一个最长公共子序列，再取两者的一个最长公共子序列，再取两者 中较长者作为中较长者作为 A 和和 B 的最长公共子序列。的最长公共子序列。 定义定义 cj为序列为序列“a0，a1，ai-2”和和“b0，b1，bj-1”的最长公共子序列

7、的长度，计的最长公共子序列的长度，计 算算 cj可递归地表述如下：可递归地表述如下： （1）cj=0 如果如果 i=0 或或 j=0；（2）cj= ci-1j-1+1 如果如果 I，j0，且，且 ai-1=bj-1； （3）cj=max（cj-1，ci-1j） 如果如果 I，j0，且，且 ai-1!=bj-1。 按此算式可写出计算两个序列的最长公共子序列的长度函数。由于按此算式可写出计算两个序列的最长公共子序列的长度函数。由于 cj的产生仅依赖于的产生仅依赖于 ci- 1j-1、ci-1j和和 cj-1，故可以从，故可以从 cmn开始，跟踪开始，跟踪 cj的产生过程，逆向构造出最长的产生过程，

8、逆向构造出最长 公共子序列。细节见程序。公共子序列。细节见程序。# include # include # define N 100char aN,bN,strN;int lcs_len(char *a, char *b, int c N) int m=strlen(a), n=strlen(b), i,j;for (i=0;i=cj-1)cj=ci-1j;elsecj=cj-1;return cmn; char *buile_lcs(char s ,char *a, char *b) int k, i=strlen(a), j=strlen(b);k=lcs_len(a,b,c);sk=0;

9、while (k0)if (cj=ci-1j) i-;else if (cj=cj-1) j-;else s-k=ai-1;i-; j-;return s;void main() printf (“Enter two string（表示表示 具有具有 n 条边条边 v0v1，v1v2，vn-1vn 的一个凸多边形，其中，约定的一个凸多边形，其中，约定 v0=vn 。若若 vi 与与 vj 是多边形上不相邻的两个顶点，则线段是多边形上不相邻的两个顶点，则线段 vivj 称为多边形的一条弦。弦将多边形称为多边形的一条弦。弦将多边形 分割成凸的两个子多边形分割成凸的两个子多边形和和。多边形的三角剖分

10、。多边形的三角剖分 是一个将多边形分割成互不重迭的三角形的弦的集合是一个将多边形分割成互不重迭的三角形的弦的集合 T。图。图 1 是一个凸多边形的两个不同是一个凸多边形的两个不同 的三角剖分。的三角剖分。(a) (b)图图 1 一个凸多边形的一个凸多边形的 2 个不同的三角剖分个不同的三角剖分在凸多边形在凸多边形 P 的一个三角剖分的一个三角剖分 T 中，各弦互不相交且弦数已达到最大，即中，各弦互不相交且弦数已达到最大，即 P 的任一不在的任一不在 T 中的弦必与中的弦必与 T 中某一弦相交。在一个有中某一弦相交。在一个有 n 个顶点的凸多边形的三角刮分中，恰好有个顶点的凸多边形的三角刮分中，

11、恰好有 n-3 条弦和条弦和 n-2 个三角形。个三角形。凸多边形最优三角剖分的问题是：给定一个凸多边形凸多边形最优三角剖分的问题是：给定一个凸多边形 P=以及定义在以及定义在 由多边形的边和弦组成的三角形上的权函数由多边形的边和弦组成的三角形上的权函数 。要求确定该凸多边形的一个三角剖分，使。要求确定该凸多边形的一个三角剖分，使 得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。可以定义三角形上各种各样的权函数可以定义三角形上各种各样的权函数 。例如：定义。例如：定义 ( vivjvk)=| vivj |+| vivk |+| vkv

12、j |，其中，其中，| vivj |是点是点 vi 到到 vj 的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长 三角剖分。三角剖分。（1）最优子结构性质）最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸（凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸（n+1）边形）边形 P=的一个最优三角剖分的一个最优三角剖分 T 包含三角形包含三角形 v0vkvn，1kn-1，则，则 T 的权的权 为为 3 个部分权的和，即三角形个部分权的和，即三角形 v0vkvn 的权，子多边形的权，子多边形的权和的权和 的权之和。

13、可以断言由的权之和。可以断言由 T 所确定的这两个子多边形的三角剖分也是所确定的这两个子多边形的三角剖分也是 最优的，因为若有最优的，因为若有或或的更小权的三角剖分，将会的更小权的三角剖分，将会 导致导致 T 不是最优三角剖分的矛盾。不是最优三角剖分的矛盾。（2）最优三角剖分对应的权的递归结构）最优三角剖分对应的权的递归结构首先，定义首先，定义 ti，j（1i的最优三角剖分所对应的的最优三角剖分所对应的 权值，即最优值。为方便起见，设退化的多边形权值，即最优值。为方便起见，设退化的多边形具有权值具有权值 0。据此定义，要计算。据此定义，要计算 的凸（的凸（n+1）边多边形）边多边形 P 对应的

14、权的最优值为对应的权的最优值为 t1，n。ti，j的值可以利用最优子结构性质递归地计算。由于退化的的值可以利用最优子结构性质递归地计算。由于退化的 2 顶点多边形的权值为顶点多边形的权值为 0， 所以所以 ti，i=0，i=1，2，n 。当。当 j 一一 i1 时，子多边形时，子多边形至少有至少有 3 个个 顶点。由最优于结构性质，顶点。由最优于结构性质，ti，j的值应为的值应为 ti，k的值加上的值加上 tk+1，j的值，再加上的值，再加上 vi- 1vkvj 的权值，并在的权值，并在 ikj-1 的范围内取最小。由此，的范围内取最小。由此，ti，j可递归地定义为：可递归地定义为：（3）计算

15、最优值）计算最优值下面描述的计算凸（下面描述的计算凸（n+1）边形）边形 P=的三角剖分最优权值的动态规划算的三角剖分最优权值的动态规划算 法法 MINIMUM_WEIGHT，输入是凸多边形，输入是凸多边形 P=的权函数的权函数 ，输出是最优，输出是最优值值 ti，j和使得和使得 ti，k+tk+1，j+（ vi-1vkvj）达到最优的位置（）达到最优的位置（k=）si，j，1ijn 。Procedure MINIMUM_WEIGHT(P，w)；Beginn=lengthp-1;for i=1 to n do ti,i:=0;for ll=2 to n dofor i=1 to n-ll+1 dobeginj=i+ll-1;ti,j=;for k=i to j-1 dobeginq=ti,k+tk+1,j+( vi-1vkvj);if q的最优三角剖分所对应的权值的最