第5章动态规划.pptx

2023/3/10第第5章章 动态规划动态规划5.1,5.2 多阶段决策和最优化原理多阶段决策和最优化原理2023/3/10山东大学 软件学院2动态规划研究的问题动态规划起源于动态规划起源于1950年代，创始人为年代，创始人为R.Bellman。动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。这样的问题可以转化为一系列相互联系的单阶段优化问题。这样的问题可以转化为一系列相互联系的单阶段优化问题。在每个阶段都需要作出决策。在每个阶段都需要作出决策。每个阶段的决策确定以后，就得到一个决策序列，称为策略。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的总体目标达到多阶段决策问题就是求一个策略，使各阶段的总体目标达到最优（如最小化费用，或最大化收益）。最优（如最小化费用，或最大化收益）。相对于线性规划一次性地对一个问题求出整体最优解，多相对于线性规划一次性地对一个问题求出整体最优解，多阶段决策问题的这种解决办法称为阶段决策问题的这种解决办法称为动态规划动态规划（Dynamic Programming）。而原来的线性规划方法被称为静态规划。）。而原来的线性规划方法被称为静态规划。2023/3/10山东大学 软件学院3内容多阶段决策问题和最优化原理多阶段决策问题和最优化原理定期多阶段决策问题定期多阶段决策问题不定期多阶段决策问题不定期多阶段决策问题2023/3/10山东大学 软件学院4问题举例一：最短路问题如图，求从如图，求从a到到g的最短路。的最短路。由于这是一个多阶段图（分层图），该图上的最短路问题由于这是一个多阶段图（分层图），该图上的最短路问题是一个多阶段决策（优化）问题。是一个多阶段决策（优化）问题。2023/3/10山东大学 软件学院5如何求解？（后向优化）2023/3/10山东大学 软件学院6逆向求解递推方程（标号法）4375476813109121316182023/3/10山东大学 软件学院7动态规划表格2023/3/10山东大学 软件学院8递归如何？循环如何？递归程序递归程序f(i,u,g)1 if i=1 then return d(u,g)，2 else return min v N(u)d(u,v)+f(i 1,v,g)。循环程序循环程序f(u,g)1 p (a,b1,c1,d1,e1,d1,f1,g)。2 for b b1 到到 b2 do 3 for c c1 到到 c4 do 4 for d d1 到到 d3 do 5 for e e1 到到 e3 do2023/3/10山东大学 软件学院9循环？6 for f f1 到到 f2 do 7 q (a,b,c,d,e,f,g)。8 if q的长度的长度 v then v t。5 endfor 6 return v。2023/3/10山东大学 软件学院16说明每计算一个单元格的每计算一个单元格的 fk(x)，都需要计算一个，都需要计算一个max 0 y x 函数。因此，尽管使用表格暂存了计算结果，为计算出最函数。因此，尽管使用表格暂存了计算结果，为计算出最后的后的 fn(x)仍需要大量的计算。仍需要大量的计算。小技巧：不用每行都从小技巧：不用每行都从 0 计算到计算到 1000。每年无论如何投放，。每年无论如何投放，回收的机床最多是回收的机床最多是 0.8x 台（台（maxa,b=0.8）。例如表格第）。例如表格第 5 行表示最后一个阶段，其前面有行表示最后一个阶段，其前面有 4 个阶段。因此对于第个阶段。因此对于第5行，只需要从行，只需要从 0 计算到计算到 0.84 1000 4096。但动态规划法已经比直接用递归的方法解递推方程减少了但动态规划法已经比直接用递归的方法解递推方程减少了大量的计算。大量的计算。计算结果2023/3/10山东大学 软件学院172023/3/10山东大学 软件学院18递归的方法f(k,x)1 v 0。2 if k=1 then 3 for y 0 到到 x do 4 t g(y)+h(x y)。5 if t v then v t。6 endfor 7 else 8 for y 0 到到 x do 9 t g(y)+h(x y)+f(k 1,ay+b(x y)。10 if t v then v t。2023/3/10山东大学 软件学院19递归的方法11 endfor12 endif13 return v。2023/3/10山东大学 软件学院20多阶段决策问题有一个系统，可以分成若干个阶段。有一个系统，可以分成若干个阶段。任意一个阶段任意一个阶段 k，系统的状态可以用，系统的状态可以用 xk 表示（可以是数量、表示（可以是数量、向量、集合等）。向量、集合等）。每一状态每一状态 xk 都有一个决策集合都有一个决策集合 Qk(xk)，在，在 Qk(xk)中选定一中选定一个决策个决策 qk Qk(xk)，状态，状态 xk 就转移到新的状态就转移到新的状态x k+1=Tk(xk,qk)，并且得到效益（或费用），并且得到效益（或费用）Rk(xk,qk)。系统的目标就是在每一个阶段都在它的决策集合中选择一系统的目标就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大（或总费用达到最个决策，使所有阶段的总效益达到最大（或总费用达到最小）。小）。这样的多阶段决策问题通常使用动态规划方法来求解。这样的多阶段决策问题通常使用动态规划方法来求解。2023/3/10山东大学 软件学院21动态规划的最优子结构性质动态规划的动态规划的最优化原理最优化原理：需要问题的最优解具有如下所述的：需要问题的最优解具有如下所述的最最优子结构性质优子结构性质：一个多阶段决策问题，假设其最优策略的第一阶段的决策一个多阶段决策问题，假设其最优策略的第一阶段的决策为为 q1，系统转移到的新状态为，系统转移到的新状态为 x2。则该最优策略以后诸决。则该最优策略以后诸决策对以策对以 x2 为初始状态的为初始状态的子问题子问题而言，必须构成其最优策略。而言，必须构成其最优策略。该子问题与原问题是同一类问题，只是问题规模下降了。该子问题与原问题是同一类问题，只是问题规模下降了。当观察到问题解的最优子结构性质时，就意味着问题可能当观察到问题解的最优子结构性质时，就意味着问题可能用动态规划法求解。用动态规划法求解。2023/3/10山东大学 软件学院22动态规划的子问题重叠性质从算法角度而言，（离散变量的）动态规划所依赖的另一从算法角度而言，（离散变量的）动态规划所依赖的另一个要素是个要素是子问题重叠性质子问题重叠性质：一个问题的求解可以划分成若：一个问题的求解可以划分成若干子问题的求解，而处理这些子问题的计算是部分重叠的。干子问题的求解，而处理这些子问题的计算是部分重叠的。动态规划法利用问题的子问题重叠性质设计算法，能够节动态规划法利用问题的子问题重叠性质设计算法，能够节省大量的计算。对一些看起来不太可能快速求解的问题，省大量的计算。对一些看起来不太可能快速求解的问题，往往能设计出多项式时间算法。往往能设计出多项式时间算法。在算法理论中，多项式时间算法通常被认为是在算法理论中，多项式时间算法通常被认为是“有效的算有效的算法法”（efficient algorithm）。）。2023/3/10山东大学 软件学院23前向优化写动态规划递推方程时，一般有两种写法：前向优化和后写动态规划递推方程时，一般有两种写法：前向优化和后向优化。假设问题有向优化。假设问题有n个阶段。个阶段。定义定义fk()为问题的前为问题的前k个阶段（从第个阶段（从第1阶段到第阶段到第k阶段）的最阶段）的最优解值，然后将优解值，然后将fk()递推至递推至fk 1()。最后写出递推的终止条件最后写出递推的终止条件f1()的表达式。的表达式。原问题就是计算原问题就是计算fn()。这称为。这称为前向优化前向优化。12nn 1fn 1()fn()2023/3/10山东大学 软件学院24后向优化假设问题有假设问题有n个阶段。个阶段。定义定义fk()为问题的后为问题的后k个阶段（从第个阶段（从第n k+1阶段到第阶段到第n阶段）阶段）的最优解值，然后将的最优解值，然后将fk()递推至递推至fk 1()。最后写出递推的终止条件最后写出递推的终止条件f1()的表达式。的表达式。原问题就是计算原问题就是计算fn()。这称为。这称为后向优化后向优化。12nn 1fn 1()fn()说明前面给出的两个例子，最短路问题和资源分配问题，都是前面给出的两个例子，最短路问题和资源分配问题，都是采用后向优化技术解决的。采用后向优化技术解决的。原则上，多阶段决策问题既可以使用前向优化技术解决，原则上，多阶段决策问题既可以使用前向优化技术解决，也可以使用后向优化技术解决。也可以使用后向优化技术解决。依据问题不同，前向优化和后向优化其中的一种或二者是依据问题不同，前向优化和后向优化其中的一种或二者是“自然自然”的解法。的解法。2023/3/10山东大学 软件学院252023/3/10山东大学 软件学院26最短路问题，前向优化2023/3/10山东大学 软件学院27资源分配问题，前向优化2023/3/10山东大学 软件学院28资源分配问题，前向优化2023/3/10山东大学 软件学院29动态规划所研究的问题阶段数固定还是不固定？阶段数固定还是不固定？阶段数固定（也称为阶段数固定（也称为“定期定期”），指阶段数有限且固定。），指阶段数有限且固定。阶段数不固定（也称为阶段数不固定（也称为“不定期不定期”）：指阶段数有限但不固）：指阶段数有限但不固定，以及阶段数无限大两种情况。定，以及阶段数无限大两种情况。离散变量还是连续变量？离散变量还是连续变量？很多阶段数不明显的优化问题，也可以使用动态规划方法很多阶段数不明显的优化问题，也可以使用动态规划方法求解。求解。2023/3/10山东大学 软件学院30