动态规划 1 ——基本概念
发布网友
发布时间：2024-10-16 02:22
共1个回答
热心网友
时间：2024-10-17 13:02
动态规划三大要素包括阶段、状态和决策。
阶段：将问题分解为多个相互关联的阶段，以便逐步求解。阶段变量描述了问题的时间或空间特征，应便于问题转化为多阶段决策。
状态：表示每个阶段开始时的自然状态或条件。状态变量通常可以描述过程中的多种状态。在多个阶段问题中，状态的数量可能不止一个。
决策：表示在某一阶段的特定状态下可以做出的不同决定，这些决定会影响下一阶段的状态。
动态规划求解一般遵循以下步骤：
1. 划分阶段
2. 正确选择状态变量
3. 确定状态转移方程
4. 建立动态规划基本方程，包括确定阶段指标函数和最优指标函数。
动态规划适用范围：
1. 多阶段决策最优化问题
2. 最优子结构（最优化原理）：每个阶段的最优策略相对于前面的决策具有最优子策略性质。
3. 无后效性：当前状态完全依赖于过去状态，而与过去无关。如果状态定义或划分方法不满足无后效性，需调整。
动态规划解决思路：
1. 模型匹配法：寻找问题与已知模型的相似性，利用已知模型的解决方案。
2. 三要素法：分析问题，确定阶段、状态和决策。阶段常在数塔或走路问题中首先确定，状态问题中状态通常首先确定，决策问题则常见于背包问题。
3. 寻找规律法：通过观察多组数据，发现规律。
4. 边界条件法：识别问题的边界条件，分析边界条件与邻接状态的关系。
接下来的文章将通过具体例题展示动态规划的应用。
【说明】接下来的例题分析将采用Solution类结构，类中的solve函数封装了解题算法。
