下载文档原格式
第三章：动态规划3.1 动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。
即决策过程可划分为明显的阶段。
二、什么叫动态规划(D.P.–Dynamic Program)：多阶段决策问题最优化的一种方法。
广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。
三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。
四、动态决策问题分类：1、按数据给出的形式分为：•离散型动态决策问题。
•连续型动态决策问题。
2、按决策过程演变的性质分为：•确定型动态决策问题。
•随机型动态决策问题。
五1、阶段(stage)n ：作出决策的若干轮次。
n = 1、2、3、4、5。
2、状态(state)S n ：每一阶段的出发位置。
构成状态集，记为S nS 1={A}，S 2={B 1,B 2,B 3}，S 3={C 1,C 2,C 3}，S 4={D 1,D 2,D 3}，S 5={E 1,E 2}。
阶段的起点。
3、决策(decision)X n ：从一个阶段某状态演变到下一个阶段某状态的选择。
构成决策集，记为D n (S n )。
阶段的终点。
D 1(S 1)={X 1(A)}={B 1,B 2,B 3}= S 2，D 2(S 2)={X 2(B 1),X 2(B 2),X 2(B 3)}={C 1,C 2,C 3}=S 3，D 3(S 3)={X 3(C 1),X 3(C 2),X 3(C 3)}={D 1,D 2,D 3}=S 4，D 4(S 4)={X 4(D 1),X 4(D 2),X 4(D 3)}={E 1,E 2}=S 5D 5(S 5)={X 5(E 1),X 5(E 2)}={F;F}={F}。
4、策略(policy)：全过程中各个阶段的决策Xn 组成的有序总体{Xn }。
如 A àB2àC1àD1àE2àF5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。
第3章动态规划动态规划是一种通过将问题分解为子问题，并且以自底向上的方式求解子问题从而求解整个问题的算法设计方法。
它在计算机科学中的应用非常广泛，特别是在优化问题和组合优化问题中。
动态规划的核心思想是将问题划分为多个重叠子问题，并且将计算结果储存起来以供后续使用。
通过这种方式，可以避免重复计算，提高算法效率。
动态规划通常适用于满足最优子结构的问题，即问题的最优解可以通过一系列子问题的最优解得到。
在动态规划中，需要定义一个状态转移方程，用于描述问题的最优解与其子问题的最优解之间的关系。
通过利用状态转移方程，可以从最底层的子问题开始，逐步求解出更大规模的问题的最优解。
最终，可以得到整个问题的最优解。
动态规划的基本步骤包括问题建模、确定状态、定义状态转移方程、确定边界条件和计算最优解。
首先，需要将原始问题转化为适合动态规划求解的形式，通常可以采用数学建模的方法。
然后，需要确定问题的状态，即将问题划分为多个子问题，并且定义子问题的状态。
接下来，需要定义状态转移方程，该方程记录了问题的最优解与子问题的最优解之间的关系。
然后，需要确定边界条件，即问题的最基本解。
最后，通过逐步计算子问题的最优解，得到整个问题的最优解。
动态规划在多个领域都有广泛的应用。
在计算机科学中，动态规划被广泛应用于图论算法、字符串处理算法、序列比对算法等。
此外，动态规划还被应用于经济学、运筹学和生物学等领域的优化问题。
通过应用动态规划，可以有效地解决这些领域中的复杂问题。
总结起来，动态规划是一种通过将问题划分为多个子问题，并且利用状态转移方程求解子问题从而求解整个问题的算法设计方法。
通过避免重复计算，动态规划可以提高计算效率，并且被广泛应用于计算机科学和其他领域的问题求解。
