我读过这些话：
为了使动态规划适用，问题必须具有两个关键属性：最优子结构和重叠子问题。如果可以通过组合非重叠子问题的最优解来解决问题，则该策略称为“分而治之”。这就是为什么归并排序和快速排序不属于动态规划问题的原因。
我有3个问题：
- 为什么mergesort和quicksort不是动态编程？我认为mergesort也可以划分小问题和小问题然后做同样的事情等等。
- Dijkstra 算法是否使用动态算法？
- 是否有使用动态规划的应用示例？
问问题
9881 次
2 回答
16
这里的关键词是“重叠子问题”和“最优子结构”。当您执行快速排序或合并排序时，您会递归地将数组分解为不重叠的较小部分。在任何给定的递归级别期间，您永远不会对原始数组的相同元素进行两次操作。这意味着没有机会重复使用以前的计算。另一方面，许多问题确实涉及在重叠子集上执行相同的计算，并且具有有用的特性，即在计算更大问题的最优解时可以重复使用子问题的最优解。
Dijkstra 算法是动态规划的经典示例，因为它重用先前的计算来发现两个节点 A 和 Z 之间的最短路径。假设 A 的直接邻居是 B 和 C。我们可以通过以下方式找到从 A 到 Z 的最短路径将 A 和 B 之间的距离与我们计算的从 B 到 Z 的最短路径相加；并类似地寻找从 C 到 Z 的最短路径。那么从 A 到 Z 的最短路径将是这两条路径中较短的一条。这里的关键见解是，在计算长度为 3 的最短路径时，我们可以对长度为 2 的路径重新使用最短路径计算，依此类推。这样做会产生更有效的算法。
动态编程可用于解决多种类型的问题——有关一些示例，请参见http://en.wikipedia.org/wiki/Dynamic_programming#Examples:_Computer_algorithms。
于 2013-03-24T08:51:07.827 回答
4
为了使动态规划适用于一个问题，应该有
一世。子问题中的最优结构：
这意味着当您将问题分解为更小的单元时，这些更小的单元也需要被分解为更小的单元以获得最佳解决方案。例如，在归并排序中，如果我们将一个数字数组分成两个子数组，对它们进行排序并组合它们，则可以对其进行排序。在对这两个子数组进行排序时，重复您在上一句中遵循的相同过程。因此，当我们找到其子问题的最优解（我们对子数组进行排序并组合它们）时，就会得到最优解（排序数组）。合并排序满足此要求。此外，子问题必须是独立的，它们才能遵循最佳结构。这也可以通过合并排序来实现，因为子问题的解决方案不会受到彼此解决方案的影响。例如，
ii. 重叠子问题：
这意味着在求解解决方案时，您制定的子问题会重复，因此只需求解一次。在归并排序的情况下，这个要求在正常情况下只会很少满足。像 2 1 3 4 9 4 2 1 3 1 9 4 这样的数字数组可能是合并排序的重叠子问题的良好候选者。在这种情况下，子问题 sort(2 1 3) 的解决方案可以存储在一个表中以供重复使用，因为它在计算过程中会被调用两次。但正如你所看到的，随机数字数组具有这种重复设计的可能性非常小。因此，如果我们将动态编程技术（如记忆化）用于合并排序等算法，则只会效率低下。
于 2016-08-08T16:47:38.707 回答