动态规划之基本概念和术语

动态规划之基本概念和术语

动态规划

引言

  1951年,美国数学家贝尔曼(R.Bellman)等根据一类所谓多阶段决策问题的特性,提出了解决这类问题的“最优化原理”,并研究了许多实际问题,从而创立了最优化的一个新分支----动态规划
  动态规划没有统一的数学模型,对不同的问题要采用不同的方法去建立它们的模型。有了模型之后,要想得到数值解,仍然没有统一的处理方法。这是应当注意的。

1 动态规划原理

1.1 最短路问题及其解法

动态规划之最短路问题及其解法

1.2 动态规划的基本概念和术语

1.2.1 多阶段决策问题

  如果一个问题的整个过程可以分成若干个互相联系的阶段,每个阶段都需要作出决策,而当每个阶段的决策都确定之后,整个过程就确定了,那么这个问题就叫做多阶段决策问题。动态规划就是解决这类问题的一种重要方法。
  一个问题是不是多阶段决策 问题是需要判断的,而这种判断并没有一般规律可循,只能靠经验和技巧。

1.2.2 阶段变量

  描述多阶段决策问题阶段数的变量叫阶段变量,记作 k ( k = 1 , 2 , ⋯   ) k(k=1,2,\cdots) k(k=1,2,⋯)。如果阶段变量是确定的、有限的,而且在决策前就知道其数值,则称此问题为定期问题。如果阶段变量虽然是确定的、有限的,但在决策之前并不知道它的数值,则称此问题为不定期问题

1.2.3 状态变量

  对于多阶段决策问题,每一阶段的起始“位置”叫状态,它既是该阶段的某一起点,也是前一阶段的终点。不同问题其状态的含义是不同的。
  描述过程状态的变量叫状态变量,用 x k x_k xk​表示第 k k k阶段的某一状态。

1.2.4 决策变量

  将过程由一个状态变到另一个状态的决定或选择叫做决策。描述决策的变量叫决策变量,用 u k ( x k ) u_k(x_k) uk​(xk​)表示从第 k k k阶段的状态 x k x_k xk​处所采取的决策。在第 k k k阶段的状态 x k x_k xk​处的所有决策构成的集合叫做决策集合,记作 D k ( x k ) D_k(x_k) Dk​(xk​)。

1.2.5 整体策略

  对于 n n n阶段决策问题,当每个阶段的决策都确定以后,由每个阶段的决策 u k ( x k ) ( k = 1 , 2 , ⋯   , n ) u_k(x_k)(k=1,2,\cdots,n) uk​(xk​)(k=1,2,⋯,n)所构成的决策序列称为一个整体策略,简称策略,记作 p 1 , n ( x 1 ) p_{1,n}(x_1) p1,n​(x1​),即
p 1 , n ( x 1 ) = ∣ u 1 ( x 1 ) , u 2 ( x 2 ) , ⋯   , u n ( x n ) ∣ . p_{1,n}(x_1)=|u_1(x_1),u_2(x_2),\cdots,u_n(x_n)|. p1,n​(x1​)=∣u1​(x1​),u2​(x2​),⋯,un​(xn​)∣.

p k , n ( x k ) = ∣ u k ( x k ) , u k + 1 ( x k + 1 ) , ⋯   , u n ( x n ) ∣ p_{k,n}(x_k)=|u_k(x_k),u_{k+1}(x_{k+1}),\cdots,u_n(x_n)| pk,n​(xk​)=∣uk​(xk​),uk+1​(xk+1​),⋯,un​(xn​)∣

p 1 , k ( x 1 ) = ∣ u 1 ( x 1 ) , u 2 ( x 2 ) , ⋯   , u k ( x k ) ∣ p_{1,k}(x_1)=|u_1(x_1),u_2(x_2),\cdots,u_k(x_k)| p1,k​(x1​)=∣u1​(x1​),u2​(x2​),⋯,uk​(xk​)∣
则分别称为一个后部 k k k段子策略前部 k k k段子策略。用 P 1 , n ( x 1 ) P_{1,n}(x_1) P1,n​(x1​), P 1 , k ( x 1 ) P_{1,k}(x_1) P1,k​(x1​)及 P k , n ( x k ) P_{k,n}(x_k) Pk,n​(xk​)分别表示整体策略集合前部及后部 k k k段子策略集合
  如果一个策略使得多阶段决策问题达到所要求的最优,则称此策略为最优策略

1.2.6 状态转移方程

  把过程由一个状态变到另一个状态叫做状态转移,显然它既与状态有关,又与决策有关。
  如果第 k k k阶段的状态 x k x_k xk​和决策 u k u_k uk​都确定以后,第 k + 1 k+1 k+1阶段的状态 x k + 1 x_{k+1} xk+1​就随之确定,那么就把这个对应关系记作
x k + 1 = T k ( x k , u k ) , x_{k+1}=T_k(x_k,u_k), xk+1​=Tk​(xk​,uk​),
并称它为由状态 x k x_k xk​到 x k + 1 x_{k+1} xk+1​的顺序状态转移方程
  如果第 k k k阶段的状态 x k x_k xk​和第 k − 1 k-1 k−1阶段的决策 u k − 1 u_{k-1} uk−1​都确定以后,第 k − 1 k-1 k−1阶段的状态 x k − 1 x_{k-1} xk−1​就随之确定,则把这个对应关系记作
x k − 1 = T k − 1 ( u k − 1 , x k ) , x_{k-1}=T_{k-1}(u_{k-1},x_k), xk−1​=Tk−1​(uk−1​,xk​),
并称它为由状态 x k x_k xk​到 x k − 1 x_{k-1} xk−1​的逆序状态转移方程

1.2.7 指标函数

  每个多阶段决策问题都存在很多策略,而每个策略都会对应某种“效益”。不同问题效益的含义是不同的,同一问题采取不同的策略其效益也会不一样。衡量问题效益优劣的数量指标称为指标函数
  对 n n n阶段决策问题,用 F k , n ( x k , p k , n ) F_{k,n}(x_k,p_{k,n}) Fk,n​(xk​,pk,n​)表示从第 k k k阶段的状态 x k x_k xk​出发,采用策略 p k , n p_{k,n} pk,n​到达终点 x k + 1 x_{k+1} xk+1​的后部指标函数。若上述过程采用的是最优策略 p k , n ∗ p^{\ast}_{k,n} pk,n∗​,则相应的后部指标函数记作 f k , n ( x k , p k , n ∗ ) f_{k,n}(x_k,p^{\ast}_{k,n}) fk,n​(xk​,pk,n∗​),简记为 f k ( x k ) f_k(x_k) fk​(xk​),并称为后部最优指标函数,简称为最优函数。 f k ( x k ) f_k(x_k) fk​(xk​)与 F k , n ( x k , p k , n ) F_{k,n}(x_k,p_{k,n}) Fk,n​(xk​,pk,n​)间的关系为
f k ( x k ) = F k , n ( x k , p k , n ∗ ) = o p t p k , n ∈ P k , n F k , n ( x k , p k , n ) , f_k(x_k)=F_{k,n}(x_k,p^{\ast}_{k,n})=\mathop{opt}\limits_{p_{k,n}\in P_{k,n}}{F_{k,n}(x_k,p_{k,n})}, fk​(xk​)=Fk,n​(xk​,pk,n∗​)=pk,n​∈Pk,n​opt​Fk,n​(xk​,pk,n​),
这里 o p t opt opt是optimization的缩写,表示最优,通常取max或min。这时 f 1 ( x 1 ) f_1(x_1) f1​(x1​)表示整体最优函数
  类似地有前部指标函数 F 1 , k ( x 1 , p 1 , k ) F_{1,k}(x_1,p_{1,k}) F1,k​(x1​,p1,k​)和前部最优指标函数 f 1 , k ( x 1 , p 1 , k ∗ ) f_{1,k}(x_1,p^{\ast}_{1,k}) f1,k​(x1​,p1,k∗​),并同样记作 f k ( x k ) f_k(x_k) fk​(xk​),且
f k ( x k ) = F 1 , k ( x 1 , p 1 , k ∗ ) = o p t p 1 , k ∈ P 1 , k F 1 , k ( x 1 , p 1 , k ) , f_k(x_k)=F_{1,k}(x_1,p^{\ast}_{1,k})=\mathop{opt}\limits_{p_{1,k}\in P_{1,k}}{F_{1,k}(x_1,p_{1,k})}, fk​(xk​)=F1,k​(x1​,p1,k∗​)=p1,k​∈P1,k​opt​F1,k​(x1​,p1,k​),
这时 f n + 1 ( x n + 1 ) f_{n+1}(x_{n+1}) fn+1​(xn+1​)表示整体最优函数
  用 d ( x k , x k + 1 ) d(x_k,x_{k+1}) d(xk​,xk+1​)表示状态 x k x_k xk​与 x k + 1 x_{k+1} xk+1​之间对应的指标,称为阶段指标。当过程是由状态 x k x_k xk​出发,采取决策 u k u_k uk​到达状态 x k + 1 = T k ( x k , u k ) x_{k+1}=T_k(x_k,u_k) xk+1​=Tk​(xk​,uk​)时,则把 d ( x k , x k + 1 ) d(x_k,x_{k+1}) d(xk​,xk+1​)写成 d ( x k , u k ) d(x_k,u_k) d(xk​,uk​);当过程是由状态 x k + 1 x_{k+1} xk+1​出发,采取决策 u k u_k uk​去确定状态状态 x k = T k ( u k , x k + 1 ) x_k=T_k(u_k,x_{k+1}) xk​=Tk​(uk​,xk+1​)时,则把 d ( x k , x k + 1 ) d(x_k,x_{k+1}) d(xk​,xk+1​)写成 d ( u k , x k + 1 ) d(u_k,x_{k+1}) d(uk​,xk+1​)。
  指标函数通常采用如下两种形式:
  (1)指标函数为阶段指标之和的形式,即
F k , n = ∑ j = k n d ( x j , u j ) = d ( x k , u k ) + F k + 1 , n , F_{k,n}=\sum\limits_{j=k}^n{d(x_j,u_j)}=d(x_k,u_k) + F_{k+1,n}, Fk,n​=j=k∑n​d(xj​,uj​)=d(xk​,uk​)+Fk+1,n​,
F 1 , k = ∑ j = 2 k d ( u j − 1 , x j ) = d ( u k − 1 , x k ) + F 1 , k − 1 . F_{1,k}=\sum\limits_{j=2}^k{d(u_{j-1},x_j)}=d(u_{k-1},x_k) + F_{1,k-1}. F1,k​=j=2∑k​d(uj−1​,xj​)=d(uk−1​,xk​)+F1,k−1​.

  (2)指标函数为阶段指标之积的形式,即
F k , n = ∏ j = k n d ( x j , u j ) = d ( x k , u k ) ⋅ F k + 1 , n , F_{k,n}=\prod\limits_{j=k}^n{d(x_j,u_j)}=d(x_k,u_k) \cdot F_{k+1,n}, Fk,n​=j=k∏n​d(xj​,uj​)=d(xk​,uk​)⋅Fk+1,n​,
F 1 , k = ∏ j = 2 k d ( u j − 1 , x j ) = d ( u k − 1 , x k ) ⋅ F 1 , k − 1 . F_{1,k}=\prod\limits_{j=2}^k{d(u_{j-1},x_j)}=d(u_{k-1},x_k) \cdot F_{1,k-1}. F1,k​=j=2∏k​d(uj−1​,xj​)=d(uk−1​,xk​)⋅F1,k−1​.

上一篇:IntelliJ IDEA 2020.3使用教程:重构代码的3种方法


下一篇:删除hao123这个恶心的毒瘤