动态规划心得

时间:2022-12-27 16:45:06

一、找出最优解的性质,刻划其结构特征-最优子结构特征

        1.  矩阵连乘:将矩阵连乘积简记为A[i:j] ,这里i≤j,m[i][j]为计算矩阵A[i:j]所需的最少数乘次数

           2.  最长公共子序列中的X(m)={x1,x2,…,xm}和Y(n)={y1,y2,…,yn},z[i][j]记录字符串X[i]、Y[j]最长公共子串长度

           3.  最大子段和:子问题: {a1,a2, …, aj},b[j]计算区间a[1:j]上最大子区间长度

           4.  最优三角剖分:凸子多边形{vi-1,vi,…,vj},t[i][j]记录凸多边形{vi-1,vi..vj}的最优三角剖分所对应的权函数值

           5.  多边形游戏:从顶点i(1≤i≤n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j),即v[i], op[i+1], …, v[i+j-1],                   m[i][j][0]存放自顶点i开始(首次删除第i条边),长度为j的子链长度的最小值,m[i][j][1]存放自顶点i开始(首次删                 除第i条边),长度为j的子链长度的最大值

           6.  图像压缩:i个象素序列{p1,…,pi},s[i]存储为前i段灰度值所需最小存储空间,

               7.  背包问题中的子问题<i,j>,m[i][j]表示可选物品为i+1,i+2..n,背包容量为j时,所装物品的最大价值 

           8.  最优二叉搜索树:最优二叉搜索树Tij,m[i][j]为子树{xi..xj}最小平均路长

二、递归地定义最优值:刻画原问题解与子问题解间的(数值)关系:表达式中存在        寻优变量、最优目标值

          1.  矩阵连乘: 当i=j时,m[i][j]=0; 只有一个矩阵,相乘次数为0
        (m[1][n])当i<j时,m[i][j]=max{m[i][k]+m[k+1][j]+p[i-1]p[k]p[j]}
                   其中,k为区间[i,j)之间的断点,矩阵Ai的维数为p[i-1]*p[i]
                   

           2.  最长公共子序列:    当i=0或j=0时,z[i][j]=0;  其中一个序列为空

               (z[lenx][leny])    当i,j>0 && X[i]==Y[j],z[i][j]=z[i-1][j-1]+1

                                                            当i,j>0 && X[i]!=Y[j], z[i][j]=max{z[i-1][j],  z[i][j-1]}

           3.  最大子段和:  当j=0,b[j]=0;  序列为空

               (b[n])              当j>0,b[j]=max{b[j-1]+a[j], a[j]}

           4.  最优三角剖分:  当i=j,t[i][j]=0; 此时三角形中只有两个顶点,为退化三角形

              (t[1][n])             当i<j,t[i][j]=max{t[i][k]+t[k][j]+w(vi-1,vi,vj)}

                                           k为区间[i, j)上的断点,w(vi-1,vi,vj)为三角形的权值

           5.  多边形游戏:      当j=1,m[i][j][0]=v[i],m[i][j][1]=v[i]; 长度为的子链

              (max{m[i][n][1]})当j>1,m[i][j][0]=min{minf(i,j,s), 1<=s<j, 1<=i,j<=n}

                                                        m[i][j][1]=max{maxf(i,j,s), 1<=s<j, 1<=i,j<=n}

                                                        maxf(i,j, s)-----将p(i,j)在op[i+s]处断开后的最大值,minf(i,j,s)----最小值                  

           6.  图像压缩:当i=0,s[i]=0;   灰度序列长度为0

                (s[n])     当i>0,s[i]=min{s[i-k]+k*bmax(i-k+1,i)}+11

                                  bmax(i-k+1,i)为最后一段[i-k+1]像素所占位数

           7.  背包问题中的子问题<i,j>,当i=n,如果w[n]>j,m[i][j]=0;    此时物品重量>背包容量

                 (m[1][c])                                     如果w[n]<=j, m[i][j]=v[n];  此时物品重量<=背包容量

                                                                        此时背包容量为j,只有一个物品可选{n},  w[]为物品重量, v[]为物品价值

                                                           当i<n,如果w[n]>j,m[i][j]=m[i-1][j];    

                                                                        如果w[n]<=j, m[i][j]=max{m[i-1][j], m[i-1][j-w[i]]+v[i]};  

           8.  最优二叉搜索树:m[i][i-1]=0  1<=i<=n  i>j

                 (m[1][n])          m[i][j]=w[i][j]+min{m[i][k-1]+m[k+1][j]}  i<=j

                                             k为区间[i,j]上的断点

                                             a[]中存放在二叉树中的叶节点找到x的概率(成功)

                                             b[]中存放在内节点上找到x的概率(失败)

                                             T(i,j)为有序集{xi..xj}关于存取概率{a[i-1],b[i]...b[j],a[j]}的一棵最优二叉树

                                             w[i][j]表示查询落在区间(xi-1, xj+1)上的概率

                                             w[i][j] = a[i-1] + b[i] +…+ b[j] + a[j]


三、以自底向上的方式计算出各个子问题、原问题的最优值,  并避免子问题的重复            计算(记录已计算的子问题解)
              这是动态规划相对于递归与分治的好处,也可以采用备忘录方法,形式上更加简洁。

四、根据计算最优值时得到的信息,构造最优解
                主要是根据各个断点,进行回溯,构造解的过程


             我觉得,遇到一个求最优问题,首先要将问题抽象出数学模型,用符号语言描述问题,然后找出此问题是否具有最优子结构,如果具有,再以递归的定义构造子问题的最优解,这一步最为关键,这不仅关系到问题是否能求解出,也关系到求解效率。然后自底向上构造最优解,当所有子问题的最优解求出来时,整个问题的最优解也就求出来了。个人感觉,还是数学的作用比较重要一些吧,在这些动态规划的问题中,不乏一些优秀的优化案例,比如在最优二叉搜索树中,运用了动态规划加速原理,这便是数学知识的运用。