大家好,欢迎来到IT知识分享网。
动态规划
动态规划是解决多阶段决策过程最优化的一种方法,其基本思想是从终点逐段向始点方向寻找最短路线。
生活中平常的事例,即可深刻揭示最短路线的重要特性:
如果最短路线在第 \(K\) 站通过点 \(P_k\) , 则由点 \(P_k\) 出发到达终点的这条路线,对于从点 \(P_k\) 出发到达终点的所有可能选择的不同路线来说,必定也是最短路线。
动态规划的分类
- 按照决策过程的时间参量是离散/连续区分:离散(多段)决策过程 vs 连续决策过程
- 按照决策过程的演变是确定/随机区分:确定性决策过程 vs 随机性决策过程
- 按照上述分类可以得到四种组合:
- 离散确定性决策过程
- 离散随机性决策过程
- 连续确定性决策过程
- 连续随机性决策过程
多阶段决策问题
- 由于它的特殊性,可将过程划分为若干互相联系的阶段;
- 在它的每一个阶段都需要作出决策,并且一个阶段的决策确定以后,常影响下一个阶段的决策,从而影响整个过程的活动路线;
- 各个阶段所确定的决策就构成一个决策序列,通常称为一个策略;
- 每一个阶段可供选择的决策往往不止一个,对应于一个策略就有确定的活动效果;
- 多阶段决策问题,就是要在允许选择的那些策略中间,选择一个最优策略,使在预定的标准下达到最好的效果。
动态规划的基本概念
阶段(Stage)
把所给问题的过程,恰当地划分成若干个相互联系的阶段,以便于求解。通常用 \(k\) 表示阶段变量。
状态(State)
状态表示某段的出发位置。它既是该段某支路的始点,同时也是前一段某支路的终点。通常一个阶段包含若干个状态。
描述过程状态的变量,称为状态变量。常用 \(x_k\) 表示在第 \(k\) 段的某一状态。第 \(k\) 段状态集合可表示为:
决策(Decision)
决策就是某阶段状态给定以后,从该状态演变到下一阶段某状态的选择。
描述决策的变量,称为决策变量。
常用 \(u_k(x_k)\) 表示第 \(k\) 段当状态处于 \(x_k\) 时的决策变量。决策变量的取值往往限制在某一范围之内,此范围称为允许决策集合。通常以 \(D_k(x_k)\) 表示第 \(k\) 段当状态处于 \(x_k\) 时的允许决策集合。
策略(Policy)
由过程的第1阶段开始到终点为止的过程,称为问题的全过程。
由每段的决策 \(u_i(x_i)(i=1,2, \dots,n)\) 组成的决策函数序列就称为全过程策略,简称策略,记为 \(p_{1,n}\)。即:
由第 \(k\) 段开始到终点的过程称为原过程的后部子过程(或称为 \(k\) 子过程)。
其决策函数序列 \(\{ u_1(x_1), u_2(x_2), \dots, u_n(x_n) \}\) 称为 \(k\) 子过程策略,简称子策略。即
在实际问题中,可供选择的策略有一定的范围,此范围称为允许策略集合,用 \(P\) 表示。从允许策略中找出的达到最优效果的策略称为最优策略。
指标函数
在多阶段决策过程最优化问题中,指标函数是用来衡量所实现过程的优劣的一种数量指标,它是一个定义在全过程和所有后部子过程上的确定数量函数,常用 \(V_{k,n}\) 表示。即
不同的问题中,指标的含义也不同:距离、利润、成本、产量、资源消耗等。
第 \(k\) 阶段由状态 \(x_k\) 作出决策 \(u_k(x_k)\) 的所对应的指标称为阶段指标(阶段效益),可记为 \(d_k(x_k, u_k)\)。
比如由 点\(x_k\) 到 点\(u_k(x_k)\) 的距离,就是一个阶段指标。
最优指标函数
指标函数 \(V_{k,n}\) 的最优值,称为相应的最优指标函数。记为 \(f_k(x_k)\)
举例: \(f_k(x_k)\) 可以代表从第 \(k\) 段 点\(x_k\) 到 终点\(G\) 的最短距离。
动态规划的基本思想和基本方程
动态规划最优化原理
作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。
可逆过程
顺序解法:假设求点A到点G的最短路线,那么以G为始端,以A为终端的左行解法程序称为顺序解法。
逆序解法:同理。
可逆过程:可以把段次颠倒过来求最优解的多阶段决策过程称为可逆过程。
构成动态规划模型的条件 (通用解法)
建立动态规划模型时,除了要将实际问题恰当地划分若干个阶段(一般是根据时间和空间而划分的)外,主要明确以下四个方面:
1、正确选择状态变量
正确选择状态变量 \(x_k\),使它既能描述过程的状态,又要满足无后效性。
动态规划中的状态与一般所说的状态概念是不同的,它必须具有三个特性:
- 要能够用来描述受控过程的演变特征。
- 要满足无后效性。所谓无后效性是指:如果某段状态给定,则在这段以后过程的发展不受前面各阶段状态的影响。
- 可知性。即是规定的各段状态变量的值,由直接或间接都是可以知道的。
2、确定决策变量及每阶段的允许决策集合
确定决策变量 \(u_k\) 及每阶段的允许决策集合 \(D_k(x_k)={u_k}\)
3、写出状态转移方程
如果给定第 \(k\) 段状态变量 \(x_k\) 的值,则该段的决策变量 \(u_k\) 一经确定,第 \(k+1\) 段状态变量 \(x_{k+1}\) 的值也就完全确定。
\(x_{k+1}\) 的值随 \(x_k\) 和 \(u_k\) 的值的变化而变化的这种对应关系,表示为:
它表示由 \(k\) 段到 \(k+1\) 段的整体转移规律,称为状态转移方程。
4、根据题意,列出指标函数关系,并要满足递推性。
正确列出指标函数 \(V_{k,n}\) 关系,必须使它具有三个性质:
- 它是定义在全过程和所有后部子过程上的数量函数;
- 要满足递推关系。 即:
- $ \Psi[x_k, u_k, V_{k+1, n}]$ 对其变元 \(V_{k+1,n}\) 来说要严格单调。
常见的指标函数是取各段指标和的形式。即
其中 \(v_j(x_j, u_j)\) 表示第 \(j\) 段的指标。它显然是满足上述三个性质的。所以上式可写成:
当初始状态给定,过程的策略也确定了时,指标函数也就确定了。
因此,指标函数是初始状态和策略的函数,记为 \(V_{k,n}[x_k, p_{k,n}(x_k)]\)。故上面递推关系又可写成:
因其子策略 \(p_{k,n}(x_k)\) 可看成是由决策 \(u_k(x_k)\) 和 \(p_{k+1,n}(x_{k+1})\) 组合而成。即
对于最优策略的指标函数值,有
其中 \(P^*_{k,n}(x_k)\) 表示初始状态为 \(x_k\) 的后部子过程所有子策略中的最优子策略
由上述四个条件(组成部分)得出动态规划的基本方程:
动态规划的基本方程
若从 \(x_k\) 出发,有:
于是可得:
以及:
以上是逆序解法的基本方程。
其递推过程从 \(k = n\) 开始,逐段向前推移,一直到求出 \(f_1(x_1)\) 时,就得到了整个过程的最优解,包括最优策略和相应的最优指标函数值。
问题举例
上面的公式太抽象了,我们来看看在实际问题中是怎么操作的:
机器负荷分配问题
某种机器,可以在高低两种不同的负荷下进行生产。
在高负荷下进行生产时,产品的年产量 \(s_1\) 和投入生产的机器数量 \(u_1\) 的关系为:
\[s_1 = g (u_1) \]这时,机器的年折损率为 \(a\),即如果年初完好机器的数量为 \(u\),到年终时完好的机器就为 \(au\),\(0<a<1\) 。
在低负荷下生产时,产品的年产量 \(s_2\) 和投入生产的机器数量 \(u_2\) 的关系为:
\[s_2 = h(u_2) \]相应的机器的年折损率为 \(b\) , \(0<b<1\) 。
假定开始生产时完好的机器数量为 \(x_1\)。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。
设机器在高负荷下生产的产量函数为 \(S_1=8u_1\),折损率为 \(a=0.7\);
在低负荷下生产的产量函数为 \(S_2=5u_2\) ,年折损率为 \(b=0.9\)。
开始生产时完好机器的数量 \(x_1=1000\) 台。按题意要安排好五年的生产计划,使产品的总产量最高。
问题的动态规划模型:
- 设阶段序数 \(K\) 表示年度。
- 状态变量 \(x_k\) 为第 \(K\) 年度初拥有的完好机器数量,亦为第 \(K-1\) 年度末时的完好机器数量。
- 决策变量 \(u_k\) 为第 \(K\) 年度中分配高负荷下生产的机器数量。则 \(x_k-u_k\) 为该年度中分配在低负荷下生产的机器数量。
- 这里 \(x_k\) 和 \(u_k\) 均取连续变量。如 \(u_k=0.3\),表示一台机器在该年度只有 \(3/10\) 的时间在高负荷下工作。
- 状态转移方程为:
- 第 \(k\) 阶段的允许决策集合为 \(D_k(x_k) = \{u_k| 0 \le u_k \le x_k \}\)
- 所以,指标函数 为 \(V_{1,5} = \sum\limits_{k=1}^5v_k(x_k, u_k)\)
- 令 \(f_k(x_k)\) 表示由 \(x_k\) 出发采用最优分配方案到第5年度结束这段期间的产品产量,根据最优化原理,则有递推关系式:
- 逆序计算,得 \(u_k = \{0, 0, x_3, x_4, x_5\}\),故最高产量为 23700。
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
- 阶段序数:第 \(k\) 步移动棋子,假设移动后处于 \((i,j)\)格,则用 \(g_k(i,j)\) 表示在 \((i,j)\) 格获得的礼物数,\(k = 1, 2, …, m+n-1\)
- 状态变量: \(x_k\) 表示为 \((i,j)\)格 移动到 \((m,n)\)格 的总礼物数量
- 决策变量: \(u_k\) 表示下一步(\(k+1\)步,选择移动到 \((i+1,j)\)格 或者 \((i,j+1)\)格)获得的礼物数量
- 状态转移方程:\(x_{k+1} = x_k – u_k\) ,\(x_{k+1}\) 表示从第 \(k+1\) 步所处的格子 到 \((m,n)\)格 的总礼物数(因为是逆序解法,也可以表示为 \(x_{k} = u_k + x_{k+1}\) )
- 允许决策集合: \(D_k(x_k) = \{g_k(i+1,j), g_k(i, j+1) | 0 < i \le m, 0 < j \le n\}\)
- 最优递推式:\(f_k(x_k)\) 表示 \((i,j)\)格 移动到 \((m,n)\)格 的最优总礼物数量
-
代码实现:
class Solution: def maxValue(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) dp = [[0] * n] * m # dp[i][j]: (i, j) 到 (n, n) 的最优礼物数 for i in range(m-1, -1, -1): for j in range(n-1, -1, -1): if i == m-1 and j == n-1: dp[m-1][n-1] = grid[m-1][n-1] down = dp[i+1][j] + grid[i][j] if i != m-1 else 0 # 状态转移方程 x_k = x_{k+1} +u_k right = dp[i][j+1] + grid[i][j] if j != n-1 else 0 # 注意i,j的边界条件 decision_set = {down, right} # 允许决策集合 dp[i][j] = max(decision_set) # 最优递推式 return dp[0][0]
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/27790.html