计算机算法设计与分析：第四章 动态规划.ppt

动态规划是一种重要的算法设计策略，尤其在解决多阶段决策问题时极为有效。它适用于那些问题的最优解可以通过组合子问题的最优解来获得的情况。在动态规划中，我们不重复计算相同状态下的子问题，而是将子问题的解存储起来，以备后续使用，这种方法被称为记忆化。 动态规划的核心思想是基于最优性原理，即最优决策序列的性质是：无论初始状态和初始决策如何，后续的决策相对于这个初始状态必须构成最优决策序列。这意味着如果一个问题的最优解可以通过将某个阶段的决策与后续阶段的最优解组合得到，那么我们可以逐步构建整个问题的最优解。 实现动态规划通常包括三个关键步骤： 1. **建立多阶段决策模型**：我们需要将问题转化为一个多阶段的过程，每个阶段都有若干决策选项，并且每个决策都会影响最终结果。 2. **证明最优性原理**：确保问题的最优解可以通过局部最优决策的组合获得，这是动态规划适用的前提。 3. **获取各阶段间的递推关系**：通过向前处理或向后处理，找出从当前阶段到下一阶段或从前一阶段到当前阶段的决策关系式，这些关系式能够帮助我们计算出每个阶段的最优决策。 向前处理法是从问题的最后阶段开始，反向推导至初始阶段。例如，在多段图问题中，我们从终点开始，逐步计算到达每个节点的最小成本路径，然后回溯找到起点到终点的最短路径。向前处理法的递推关系式是：COST(i, j) = min{c(j, l) + COST(i+1, l)}，其中l是下一阶段的节点，c(j, l)是边的成本。 向后处理法则相反，从起点开始，逐步向前计算每个阶段的最优决策，直到达到终点。这种方法同样可以找到最小成本路径。 在多段图问题中，图的节点被分成多个阶段（集合Vi），每个阶段的决策影响着后续阶段的成本。若能找到从源点s到汇点t的最小成本路径，就解决了这个问题。最优性原理在此问题中的满足性可以通过反证法来证明：假设存在一个更优路径，那么这个更优路径的局部决策（如从V2到t）也应该优于原始路径的相应部分，否则就与全局最优矛盾。 总结来说，动态规划是通过构建决策模型，利用最优性原理，以及通过递推关系式来逐步求解问题的一种方法。它在计算机科学中有着广泛的应用，如在路径规划、资源分配、字符串匹配、网络流量优化等众多领域。理解和掌握动态规划技巧，对于提升问题解决能力，尤其是在面对复杂优化问题时，显得尤为重要。