为什么mergesort不是动态编程

Question

我读过这些话:

为了使动态编程适用,问题必须具有两个关键属性:最佳子结构和重叠子问题.如果通过将最优解与非重叠子问题相结合可以解决问题,则该策略称为"分而治之".这就是mergesort和quicksort未被归类为动态编程问题的原因.

我有3个问题:

1. 为什么mergesort和quicksort不是动态编程？我认为mergesort也可以分为小问题和小问题然后做同样的事情等等.
2. Dijkstra算法是使用动态算法吗？
3. 是否有使用动态编程的应用示例？

Answer 1

1. 这里的关键词是"重叠子问题"和"最优子结构".当您执行quicksort或mergesort时,您将递归地将数组分解为不重叠的较小块.在任何给定的递归级别期间,您永远不会对原始数组的相同元素进行两次操作.这意味着没有机会重复使用以前的计算.另一方面,许多问题涉及在重叠子集上执行相同的计算,并且具有在计算针对较大问题的最优解时可以重用子问题的最优解的有用特性.

2. Dijkstra的算法是动态编程的典型例子,因为它重新使用先前的计算来发现两个节点A和Z之间的最短路径.假设A的直接邻居是B和C.我们可以找到从A到Z的最短路径.用从B到Z的计算最短路径求和A和B之间的距离; 并且类似地找到从C到Z的最短路径.然后,从A到Z的最短路径将是这两条路径中较短的路径.这里的关键见解是,当计算长度为3的最短路径时,我们可以重新使用长度为2的路径的最短路径计算,依此类推.这样做会产生更有效的算法.

3. 动态编程可用于解决许多类型的问题 - 有关示例,请参阅http://en.wikipedia.org/wiki/Dynamic_programming#Examples:_Computer_algorithms.

Answer 2

1. 为了使动态规划适用于某个问题，应该有

   我。子问题的最优结构：

这意味着当您将问题分解为更小的单元时，这些更小的单元也需要分解为更小的单元以获得最佳解决方案。例如，在合并排序中，如果我们将数字数组分成两个子数组，对它们进行排序并组合它们，则可以对其进行排序。对这两个子数组进行排序时，重复与上一句相同的过程。因此，当我们找到子问题的最优解（对子数组进行排序并组合它们）时，就得到了最优解（已排序的数组）。归并排序就满足了这个要求。此外，子问题必须是独立的，才能遵循最佳结构。这也可以通过合并排序来实现，因为子问题的解决方案不会受到彼此解决方案的影响。例如，数组的两个部分的解不受彼此排序的影响。

二. 重叠子问题：

这意味着在求解解决方案时，您提出的子问题会重复，因此只需要解决一次。在合并排序的情况下，正常情况下很少会满足此要求。像 2 1 3 4 9 4 2 1 3 1 9 4 这样的数字数组可能是合并排序重叠子问题的良好候选者。在这种情况下，子问题 sort(2 1 3) 的解可以存储在表中以供重用，因为在计算过程中它将被调用两次。但正如您所看到的，随机数字数组出现这种重复设计的可能性非常小。因此，如果我们对合并排序等算法使用记忆化等动态编程技术，效率只会很低。

2. 是的。Dijkstra 的算法使用 @Alan 在评论中提到的动态规划。关联

3. 是的。如果我可以在这里引用维基百科的话，“动态编程广泛应用于生物信息学中的任务，例如序列比对、蛋白质折叠、RNA 结构预测和蛋白质-DNA 结合。” ¹

1 https://en.wikipedia.org/wiki/Dynamic_programming