一文看懂动态规划
目录
1.动态规划的概念
2.动态规划的基本要素
1.最优子结构性质（最优化原理）
2.重叠子结构性质
3.动态规划基本思想
4.设计动态规划算法的步骤
4.动态规划算法实例
1.矩阵连乘问题
1.穷举法
2.动态规划法
1.动态规划的概念
在现实中存在一类特殊的活动过程，在其每一个子过程中都需要做出相应的策略选择以实现最佳的整体效果。由于每个子过程的选择都受到前一状态的影响，并且会对未来的发展产生影响。因此，在每一个子过程中选择合适的策略不仅取决于当前所处的状态而且也会影响到未来的进程．一旦所有各子过程中的策略都被合理选择并实施完毕，则整个系统就能得到最优的整体效果．
将一个问题视为前后相联、呈链式结构的多变量系统或多环节系统，则可称之为多变量或多环节动态系统或系统工程学中的多项级优化模型。此类系统/模型则被称作多项级优化系统/模型/动态系统等术语视上下文而定。在多项级优化系统中，在各个时间段内所采取的各项措施（即策略），通常与其时间参数相关，并且每项措施均取决于前一时期的状态信息，在执行后又会随之导致状态转移（即状态更新）。各期所采取的各项措施形成的策略序列即是从变化的状态中演化出来的某种程序或流程序列，在此过程中体现出一定的动态特性（即时序性）。因此被用来解决多项级优化任务的方法则可统称为动态规划法/逐步优化法/串行最优化法等不同领域术语下的名称
2.动态规划的基本要素
1.最优子结构性质（最优化原理）
最优化原理可用如下方式表述：对于一个最优化策略来说，在任何时刻之前的历史状态与后续行动无关的前提下，在当前状态下做出的最佳选择必然是最佳选项。简单地说，则是说该最优化策略的所有子策略都必须是最优的。当且仅当一个问题满足最优化原理时才称其具有最优子结构特性。
2.重叠子结构性质
该类算法的核心目标是消除重复计算以提高效率，并以此为基础实现了优化效果。这种技术本质上是一种通过内存换取计算效率的方法，在运行过程中必须记录各个阶段的状态信息。其特点表现为较高的内存占用水平。选择这种方案的原因在于，在面对内存限制的情况下仍能有效运行，并与那些仅关注速度而不考虑资源消耗的策略形成对比。
3.动态规划基本思想
动态规划算法一般用于解决包含特定优化特征的问题，在这一类问题中可能会出现多个候选方案。每个候选方案都有一个对应的评估数值，在这些数值中我们希望找到最高的那个候选方案。
动态规划作为一种解决优化性问题的有效方法，在其本质与分治法存在诸多相似之处。该算法的核心理念也包括将复杂的问题拆分为多个较易解决的小规模子问题，并通过逐步求解这些小规模的子任务最终实现对整体目标的完成。在实现这一目标的过程中，动态规划算法特别强调通过系统地整理各个分步解决方案并进行综合分析来确保最终结果的质量。
与分治法不同的是，在能够通过动态规划方法高效解决的问题中（即那些能被分解为若干相似但不独立子问题的问题），其分解出的子问题通常存在相互重叠的情况。当采用分治法解决这类问题时（即那些无法有效避免重复计算的问题），会产生过多的子问题；其中许多子问题是被反复计算的
为了便于管理所有已解决的子问题的答案, 我们可以考虑建立一个表格来进行记录和查询, 以便快速查找所需的结果. 即使未来不再使用该子问题本身, 在其已经被解决的情况下, 我们仍然将结果存储在表格中. 这正是动态规划法的核心理念. 尽管不同的动态规划算法各有特色, 但它们在填表这一操作上却有着共同的基础和方法.
4.设计动态规划算法的步骤
- 第一步. 首先识别出问题的优化特性, 并对其实质结构进行详细描述
- 第二步. 通过递归的方式设定问题的最佳解决方案参数
- 第三步. 从下往上逐步计算各个层级的最佳解决方案数值
- 第四步. 参考计算过程中获取到的相关信息构建出优化方案的具体实现形式
前三个阶段构成了动态规划算法的基础环节；当仅需计算最优值时，则无需实施第四个阶段。
为获得问题的最优解而必须采取行动时，则需执行步骤4。在此时，在完成步骤3中的计算过程时，则通常会记录下更为详细的信息；以便于在后续步骤4中迅速构建出一个有效的最优解
4.动态规划算法实例
1.矩阵连乘问题
问题描述：
设有由n个矩阵构成的序列{A₁, A₂, A₃, …, Aₙ}，其中任意两个相邻矩阵A_i与A_{i+1}均满足相乘条件（i=1, 2, …, n−1）。我们关注该序列中各矩阵的连乘积结果为：Π_{i=1}^{n} A_i。
因为矩阵乘法符合结合律，在计算多个矩阵相乘时存在不同的执行顺序。这些不同的执行顺序可以通过适当添加括号的方式来决定。
我们来引出计算代价的概念
计算成本：乘法数量
当矩阵A具有维度p×q时，在考虑与另一矩阵B相乘的情况下（其中B具有维度q×r），其乘积所需的操作数为pqr次。
这里假设所有元素都是标量，并且在标准数值精度下完成操作。
该算法的时间复杂度直接由这三个参数决定。
举例：A1、A2、A3连乘积
假设这三个矩阵的维数分别为：
A1:20×50
A2:50×5
A3:5×30
(A1A2)A3:计算代价：20×50×5 + 20×5×30 = 8000
A1(A2A3):计算代价：50×5×30 + 20×50×30 = 37500
通过对比分析可知, 第二类加括号方法所需运算时间约为第一类方法的五倍. 由此可得, 在矩阵连乘运算中选择不同的加括号方式（即确定运算次序）会对总运算量产生显著影响.
针对当前课题而言，我们需要规划如何排列矩阵相乘顺序以最小化总运算量。
1.穷举法
应对上述问题时,最有可能会考虑的方法是穷举策略.具体表现为:首先列举所有可能的运算顺序,并针对每种运算顺序计算相应的乘法操作数量,然后从中筛选出所需乘法操作数量最少的一种最优运算顺序.然而这种方法带来的总运算量非常庞大.
将n个矩阵相乘的过程中，在第k个(k=1,2,…,n−1)和第k+1个矩阵之间将原矩阵序列划分为两个子序列，并对这两个子序列分别进行完全加括号处理；之后将这两个处理后的结果进行组合运算即可形成一种完全加括号的方式。这样就得到了关于P(n)的递归关系式如下：
我们对这个递归方程进行了深入研究，并在此过程中识别出P(n)本质上属于Catalan数。具体来说，在进一步分析后得出结论：P(n)=C(n-1)，其中
关于Catalan数的知识，可以自行百度，这里不多赘述
经过分析我们发现P(n)呈现为随n的增长呈指数增长。因此无法作为有效的解决方案用于穷举法
下面我们考虑用动态规划法来解决这个问题
2.动态规划法
1.分析最优解的结构
构建解决特定问题的动态规划算法的第一步通常是分析其整体最优结构特性。为了简化表示，在处理连续矩阵乘积时通常采用符号A[i:j]来表示从第i个到第j个矩阵相乘的结果。
考察计算A[1:n]的最优计算次序。
若将矩阵链中的一个点k作为分割点，在矩阵Ak与Ak+1之间将其分开，则该分割点对应的完全加括号方法即为((A₁至A_k)(A_{k+1}至A_n}))。
按照这种顺序进行操作时，默认是依次先计算前一部分[A₁到A_k]以及后一部分[A_{k+1}到A_n}]的结果，并随后将这两部分的乘积组合起来以获得最终结果。
按照给定的运算顺序，在该算法中总的运算量由三个部分构成：首先是A[1:k]区间的单独运算总量、其次是A[k+1:n]区间的单独运算总量、最后是这两个区间的乘积项运算总量。
该问题的核心属性在于：为了实现最优化，在计算整个矩阵链A_{\text{}}^{m \times n}时所采用的所有子链计算（如C_{\text{}}^{p \times q}与D_{\text{}}^{q \times r}）均需达到局部最优；由此可见，在优化全局的过程中局部的选择同样无法逃脱优化的要求：若单独优化某一部分（如C_{\text{}}^{p \times q}）所需的时间比原计划减少，则整体的时间将因此而被缩短至比预想方案更低的时间水平——这与全局最优化的目标相悖；由此可知，在全局最优策略下所有构成部分（如子链矩阵链中的每个部分）都必须满足各自局部最优化的要求
基于此，矩阵连乘积计算次序问题的最优解确实包含了其子问题的最优解。这一特性即为该问题能够采用动态规划算法求解的基础。该问题可用动态规划算法求解的主要特点即在于这一优化子结构。
2.建立递归关系
针对矩阵链乘积的最佳计算顺序问题, 考虑A[i:j] (1≤i≤j≤n)；所需的最小乘法次数为
对于任意给定的i和j满足m[i][j]存在，则原问题的最优值即为 m[1][n]。
当i等于j时，在这种情况下"A矩阵分割点"位于区间内（仅包含一个元素），其乘法次数为零（即单位矩阵）。因此有：
m[i,i]=0 \quad (i=1,2,3,\dots,n)
对于情况i
m[i,j]= m[i,k]+ m[k+1,j]+ p_{(i-1)} p_k p_j
然而，在实际求解过程中并不知道具体的分割点k的位置。因此需要遍历所有可能的k值（共有j-i种可能性），并选择使得总运算量达到最小的那个分割点Ak的位置：
m^{(ij)}=\min_{k=i}^{j-1} \{ m^{(ik)} + m^{(k+1,j)} + p_{(i-1)}p_kp_j \}
3.计算最优值
根据计算m[i][j]的递归式，容易写一个递归算法计算m[1][n]。
接下来我们借助填表过程理解递归的过程，现在给出下列矩阵：
填表过程是按对角线填写的，只利用到了二维数组的右上角一部分。
按照地推公式可知，在当i等于j时m值为零的情况下随后构建最长的对角线数据如图所示。
现在我们继续构造，
m（1,2）=min{m[1][1]+m[2][2]+p0p1p2}={0+0+303515}=15750
m(2,3) = min(m[2][2]+m[3][3]+p1p2p3=0+0+35155）=2625
同理，后面不再一一列举；
再多说一点，有时我们会遇到有多个划分，我们取最小值就可以了，
例如：
结果图如下：
那么，我们最后如何得知是哪个地方要加括号呢？
根据最后的公式。
例如，在最后计算中假设m[1:6]等于m[1,1]加上m[2][6]再加上p_0 p_2 p_6（这是笔者特意构造的一个案例，并不与前面的例子相关），那么我们就知道结果为(A_1(A_2 A_3 A_4 A_5 A_6))。接着查看m[2:6]这一部分，在公式指导下确定退出括号的位置，并逐步推进到末尾。
经观察可知，其加括号的位置实际上就是k值对应的索引构成的矩阵，在编写算法的过程中，则可利用另一个数组来存储相应位置处的k值。最终，在将该数组进行有条理地输出时就能完成相应的数据处理任务。
核心算法：
void MatrixChain(int n)
{
int r, i, j, k;
for (i = 0; i <= n; i++)//初始化对角线
{
m[i][i] = 0;
}
for (r = 2; r <= n; r++)//r个矩阵连乘
{
for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
{
j = i + r - 1;
m[i][j] = m[i][i]+m[i + 1][j] + A[i - 1] * A[i] * A[j];
s[i][j] = i;
for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
{
int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
if (t < m[i][j])//如果变换后的位置更优，则替换原来的分隔方法。
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}算法MatrixChain的主要计算开销受该算法中的三重循环结构的影响程度与其总运算次数成正比。
,因此，该算法的计算时间上界为
。
4.构造最优解
动态规划算法第四步的主要任务是构建问题的最佳解决方案。该算法仅计算获得最低乘法次数所需矩阵的数量而未提供具体的相乘顺序，在此之前无法确定具体的相乘步骤以达到最小数乘次数的目的。换句话说，在得到最低数乘次数之后仍需进一步推导出具体的矩阵相乘顺序才能完成整个优化过程。基于该算法的运算结果可知其只能确定最少数目乘法操作但无法直接推导出实际的操作步骤
事实上，在MatrixChain中已存储了构建最优解所需的前期信息。s[i][j]的数值表明，在计算矩阵链A[i:j]时的最佳策略是将运算在第k个矩阵与第k+1个矩阵之间中断（即选择在Ak和Ak+1之间断开），从而实现(A[i:k)和(A[k+1:j])的组合）。基于s[1][n]存储的信息可知，在计算A[1:n]时其最优加括号策略可表示为(A[1:s₁ⁿ])(A[s₁ⁿ+1:n])的形式。其中对子串A1:s₁ⁿ而言其优化方案同样适用上述策略即通过递归分解的方式可以逐步确定每一部分的具体加括号顺序直至最终构造出一个完整的最优解序列
下面是该算法的完整代码：
#include<iostream>
using namespace std;
const int N = 100;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n)
{
int r, i, j, k;
for (i = 0; i <= n; i++)//初始化对角线
{
m[i][i] = 0;
}
for (r = 2; r <= n; r++)//r个矩阵连乘
{
for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
{
j = i + r - 1;
m[i][j] = m[i][i]+m[i + 1][j] + A[i - 1] * A[i] * A[j];
s[i][j] = i;
for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
{
int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
if (t < m[i][j])//如果变换后的位置更优，则替换原来的分隔方法。
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
void print(int i, int j)
{
if (i == j)
{
cout << "A[" << i << "]";
return;
}
cout << "(";
print(i, s[i][j]);
print(s[i][j] + 1, j);//递归1到s[1][j]
cout << ")";
}
int main()
{
int n;//n个矩阵
cin >> n;
int i, j;
for (i = 0; i <= n; i++)
{
cin >> A[i];
}
MatrixChain(n);
cout << "最佳添加括号的方式为：";
print(1, n);
cout << "\n最小计算量的值为：" << m[1][n] << endl;
return 0;
}备忘录算法后期再写吧，今晚太累了