动态规划决策示例：广告牌选址与数塔最大和问题

动态规划是一种在多阶段决策问题中寻找最优解的方法，其核心思想在于将复杂问题分解成更小、更易管理的部分，并通过这些部分之间的相互作用来找到全局最优解。在给定的讲义中，我们探讨了如何在一个带有权重的图中应用动态规划算法来确定从城市0出发经多个城市并最终返回城市0的最短路径。 决策过程基于成本矩阵C，其中每个单元格cij代表从城市i到城市j的成本。在这个问题中，关键步骤是计算到达每一对相邻城市组合的成本和从这些城市继续前进到下一阶段的成本之和。例如，从城市1到城市2和3的成本分别为c12和c13，再结合下一个阶段从2或3到达其他城市的成本，形成如下的状态转移关系： - d(1, {2, 3}) = min{c12 + d(2, {3}), c13 + d(3, {2})} - d(2, {1, 3}) = min{c21 + d(1, {3}), c23 + d(3, {1})} - d(3, {1, 2}) = min{c31 + d(1, {2}), c32 + d(2, {1})} 在第一阶段，决策者还需根据起点城市0到每个城市的直接成本（c01, c02, c03）来初始化状态值，如d(1, {}) = c10, d(2, {}) = c20, 和 d(3, {}) = c30。 通过这样的递归关系，动态规划算法逐层推进，解决子问题，直到到达最后一层（城市0），此时的最短路径长度即为d(0, {1, 2, 3})，它是所有可能路径成本中的最小值。这个过程强调了决策的灵活性，即每个阶段的选择不仅取决于当前状态，还依赖于先前阶段的结果，这与线性决策策略和贪婪算法有着显著的区别。 以数塔问题为例，动态规划通过将大问题分解为更小的子问题，比如从第五层开始，依次决定每一步的最佳路径，然后递推到下一层，避免了局部最优导致的整体较差结果。这种方法的优势在于能够找到全局最优解，即使初始问题看起来非常复杂。 总结来说，动态规划的关键在于阶段划分、状态转移、递归求解以及优化策略的选择，它在解决涉及多个阶段决策和最优路径的问题时表现出了强大的效率和准确性。在实际应用中，动态规划被广泛应用于诸如最优化问题、背包问题、网络流问题等领域。