动态规划算法详解：Johnson不等式与矩阵连乘

"Johnson不等式-第三章 动态规划算法（上）" 动态规划算法是一种解决复杂问题的有效方法，它通过将问题分解为更小的子问题，并存储子问题的解决方案，以避免重复计算。这一概念在编程和算法设计中占有重要地位，特别是在寻找最优解的问题中。Johnson不等式是动态规划在作业调度问题中的一个重要工具，用于优化多任务在有限资源下的执行顺序。 在描述中提到的Johnson不等式，是针对作业调度问题的一种优化条件。当两个作业i和j满足min{bi, aj} ≥ min{bj, ai}时，它们满足Johnson不等式，其中bi和aj分别代表作业i和j的处理时间。这个不等式有助于确定在特定机器M2上，当等待时间为t时，如何安排作业i和j的顺序以达到总等待时间的最小化。在动态规划的递归表达式中，T(S, t)表示集合S中的所有作业在等待时间t时的总执行时间，T(S-{i,j}, tij)则表示去掉作业i和j后剩余作业的总执行时间。 动态规划算法通常包括以下四个关键步骤： 1. 问题定义：明确问题，分析问题的最优解应该具备的结构。 2. 状态定义：定义用于存储子问题解的状态，例如在矩阵连乘问题中，状态可能是一个数组，用来存储每个子矩阵的乘积。 3. 状态转移方程：建立从子问题到原问题的递归关系，例如在斐波纳契数列中，F(n) = F(n-1) + F(n-2)。 4. 优化策略：自底向上的计算最优解，避免重复计算，这通常通过表格填充实现，例如动态规划数组。 在矩阵连乘问题中，动态规划算法通过分析最优解的结构，即最优子结构性质，来确定矩阵的最佳连乘顺序。对于矩阵A1A2...An，我们可以通过分析每个子序列Ai...Aj的最优计算次序，来找到整个序列的最小计算量。动态规划在这里的关键是，最优的矩阵连乘顺序包含了子序列的最优连乘顺序。 总结起来，Johnson不等式是动态规划在作业调度中的一个优化准则，而动态规划算法本身则是一种解决最优化问题的强大工具，广泛应用于各种领域，如计算机科学、运筹学、经济学等，其核心在于利用子问题的最优解来构建原问题的全局最优解，有效地减少了计算复杂性。