北京大学屈婉玲教授解析动态规划：实例涵盖最短路径、矩阵乘法等

动态规划是一种在数学优化问题中常用的方法，它通过将大问题分解成相互重叠的子问题来寻找最优化解决方案。屈婉玲在北京大学的课程中，动态规划涉及了多个具体的应用场景，如最短路径问题、背包问题、矩阵链乘积、最长公共子序列、凸多边形最优三角剖分、图像压缩、电路布线、流水作业调度、最优二叉搜索树以及旅行商问题等。 1. **基本思想和使用条件**： - 动态规划的核心思想是"最优子结构"，即任何问题的最优解都可以由其子问题的最优解组合而成。例如，在最短路径问题中，最短路径的任意子路径也是相对子路径起点和终点的最短路径。 - 使用动态规划的前提是问题满足“优化原则”，即一个最优决策序列的任何子序列也必须是相对于子序列初始和结束状态的最优决策。然而，不是所有问题都适合用动态规划解决，如例2中的总长模10的最小路径问题，因为它的最优解并非由子问题最优解简单相加得到，不满足动态规划的优化原则。 2. **应用实例**： - **最短路径**：通过递归地计算每个节点到目标节点的最短路径，例如通过Dijkstra或Floyd-Warshall算法实现。 - **矩阵链乘积**：通过调整矩阵的乘法顺序，减少总的乘法次数，通过贪心策略或穷举法来寻找最优的乘法序列。 - **背包问题**：0-1背包问题或完全背包问题，通过遍历所有可能的物品选择组合，找到总价值最大且不超过背包容量的解。 - **旅行商问题**：著名的NP完全问题，通过启发式方法如遗传算法或模拟退火寻找近似最优解。 3. **算法设计步骤**： - 定义状态：确定问题的状态空间，通常表示为二维数组或表格。 - 状态转移方程：定义从一个状态转移到另一个状态所需的函数，通常是前一状态的结果加上当前决策的成本。 - 初始化：定义边界条件或基础状态，通常是易于处理的小规模问题。 - 递推过程：按照特定顺序填充状态表，通常从较小规模的子问题开始，逐步构建最终解。 - 解析答案：从最终状态回溯，得到原始问题的最优解。 北京大学屈婉玲教授的课程深入浅出地讲解了动态规划的基本原理、适用条件及一系列实际应用案例，让学生对这一强大工具有了全面理解，并能灵活运用到实际问题中去。通过这些实例，学生不仅掌握了动态规划的理论知识，还提升了解决问题的能力。