算法学习--动态规划

动态规划(Dynamic Programming)

1.动态规划的基本概念

动态规划是解决多阶段决策过程最优化的一种方法。

对于离散问题，解析数学无法施展，动态规划则成为非常有效的工具。

两个弱点：

1.       得出目标函数方程后，尚无统一的处理方法，必须根据具体问题的性质结合相应的数学技巧来求解；

2.       维数障碍。

动态规划模型的分类：

根据决策过程的时间参量是离散的还是连续的变量

1.       离散（多段）决策过程

2.       连续决策过程

根据决策过程的演变是确定性的还是随机性的

1.       确定性决策过程

2.       随机性决策过程

2.多阶段决策问题

1.       由于它的特殊性，可将过程划分为若干互相联系的阶段；

2.       在它的每一个阶段都需要作出决策，并且一个阶段的决策确定以后，常影响下一个阶段的决策，从而影响整个过程的活动路线；

3.       各个阶段所确定的决策就构成一个决策序列，通常称为一个策略；

4.       每一个阶段可供选择的决策往往不止一个，对应于一个策略就有确定的活动效果；

5.       多阶段决策问题，就是要在允许选择的那些策略中间，选择一个最优策略，使在预定的标准下达到最好的效果。

3.动态规划的基本概念

阶段(Stage)

把所给问题的过程，恰当地划分成若干个相互联系的阶段，以便于求解。通常用k表示阶段变量。

状态（State）

状态表示某段的出发位置。它既是该段某支路的始点，同时也是前一段某支路的终点。通常一个阶段包含若干个状态。

       描述过程状态的变量，称为状态变量。常用x_k表示在第k段的某一状态。第k段状态集合可表示为

       X_k = { x_k⁽¹⁾, x_k⁽²⁾, …, x_k⁽ⁱ⁾ , …, x_k^(r)}

故第三阶段的状态集合就可记为

    X₃ = { x₃⁽¹⁾, x₃⁽²⁾, x₃⁽³⁾ , x₃⁽⁴⁾}={1, 2, 3, 4}

    或  X₃ = {C₁, C₂, C₃, C₄}

决策（Decision）

决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。

       描述决策的变量，称为决策变量。

       常用u_k(x_k)表示第k段当状态处于x_k 时的决策变量。决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。通常以D_k(x_k)表示第k段的允许决策集合。

u_k(x_k) ∈ D_k(x_k)

策略（Policy）

由过程的第1阶段开始到终点为止的过程，称为问题的全过程。

由每段的决策u_i(x_i)(i=1,2……,n)组成的决策函数序列就称为全过程策略，简称策略，记为p_1,n。

即  p_1,n(x_k)={ u₁(x₁), u₂(x₂), ……, u_n(x_n)}

由第k段开始到终点过程称为原过程的后部子过程（或称为k子过程）。

    其决策函数序列{ u_k(x_k)，……, u_n(x_n)}称为k字过程策略，简称子策略。即

    p_k,n(x_k)={u_k(x_k), u_k+1(x_k+2), ……, u_n(x_n)}

在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。从允许策略中找出达到最优效果的策略称为最优策略。

指标函数和最优指标函数

在多阶段决策过程最优化问题中，指标函数是用来衡量所实现过程的优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的确定数量函数，常用V_k,n表示。

•   指标函数V_k,n的最优值，称为相应的最优指标函数。记为f_k(x_k).

•   在例1中，f_k(x_k)表示从第k段x_k点到终点G的最短距离。如f₄(D₁)就表示从第4段中的D₁点到G 点的最短距离。

4.动态规划最优化原理

作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。

可逆过程

可以把段次颠倒过来球最优解的多阶段决策过程称为可逆过程。

顺序解法和逆序解法只表示行进方向的不同或始端的颠倒。但用动态规划方法求最优解时，都是在行进方向规定后，均要逆着这个规定的行进方向，从最后一段向前逆推计算，逐段找出最优途径。

5.构成动态规划模型的条件

建立动态规划模型时，除了要将实际问题恰当地划分若干个阶段（一般是根据时间和空间而划分的）外，主要明确以下四个方面：

1.     正确选择状态变量x_k, 使它既能描述过程的状态，又要满足无后效性。

动态规划中的状态与一般所说的状态概念是不同的，它必须具有三个特性：

1)      要能够用来描述受控过程的演变特征。

2)      要满足无后效性。 所谓无后效性是指：如果某段状态给定，则在这段以后过程的发展不受前面各阶段状态的影响。

3)      可知性。即是规定的各段状态变量的值，由直接或间接都是可以知道的。

2 确定决策变量u_k及每段的允许决策集合D_k(x_k)={u_k}。

3 写出状态转移方程

1)      如果给定第k段状态变量x_k的值，则该段的决策变量u_k一经确定，第k+1段状态变量x_k+1的值也就完全确定。

2)      x_k+1的值随x_k和u_k的值的变化而变化的这种对应关系，用

1.       x_k+1 = T_k(x_k, u_k) 表示。

3)      它表示由k段到k+1段的整体转移规律，称为状态转移方程。

4   根据题意，列出指标函数V_k,n 关系，并要满足递推性。

       正确列出指标函数关系，必须使它具有三个性质：

1)      它是定义在全过程和所有后部子过程上的数量函数；

  2)      要满足递推关系。
 

6. 动态规划的基本方程

下面还有一个将动态规划很好的文档，上面有相应的关于动态规划方面的例题，以及详细的解题过程！

文件:	动态规划.pdf
大小:	156KB
下载:	下载