分治算法与动态规划的区别

Question

Divide和Conquer算法和动态规划算法有什么区别？这两个术语有何不同？我不明白他们之间的区别.

请举一个简单的例子来解释两者之间的差异以及它们看起来相似的基础.

Answer 1

分而治之

Divide and Conquer的工作原理是将问题分解为子问题,递归地克服每个子问题并组合这些解决方案.

动态编程

动态编程是一种解决重叠子问题的技术.每个子问题仅解决一次,并且每个子问题的结果存储在表(通常实现为数组或散列表)中以供将来引用.这些子解决方案可用于获得原始解决方案,并且存储子问题解决方案的技术称为存储器化.

你可能会想到 DP = recursion + re-use

理解差异的一个典型例子是看到这两种获得第n个斐波纳契数的方法.从麻省理工学院查看此材料.

分而治之的方法

动态规划方法

Answer 2

分而治之和动态编程之间的另一个区别可能是:

分而治之:

1. 更多的工作在子问题上,因此有更多的时间消耗.
2. 在分而治之中,子问题是相互独立的.

动态编程:

1. 仅解决子问题一次,然后将其存储在表中.
2. 在动态编程中,子问题不是独立的.

Answer 3

有时在递归编程时,你会多次调用具有相同参数的函数,这是不必要的.

着名的例子斐波那契数字:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

我们运行F(5):

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

所以我们称之为:1次F(4)2次F(3)3次F(2)2次F(1)

动态编程方法:如果多次调用具有相同参数的函数,请将结果保存到变量中,以便下次直接访问它.迭代方式:

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

我们再次打电话给F(5):

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

如您所见,只要您需要多次调用,您只需访问相应的变量即可获取值而不是重新计算它.

顺便说一下,动态编程并不意味着将递归代码转换为迭代代码.如果需要递归代码,还可以将子结果保存到变量中.在这种情况下,该技术称为memoization.对于我们的示例,它看起来像这样:

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

因此,与分而治之的关系是D&D算法依赖于递归.并且它们的某些版本具有"具有相同参数问题的多个函数调用".搜索需要DP以改善D&D算法的T(n)的示例的"矩阵链乘法"和"最长公共子序列".

Answer 4

动态规划与分而治之的相似之处

正如我现在所看到的,我可以说动态编程是分而治之的范例的延伸.

我不会将它们视为完全不同的东西.因为它们都通过递归地将问题分解为相同或相关类型的两个或更多个子问题来工作,直到这些子问题变得足够简单直接解决.然后组合子问题的解决方案以给出原始问题的解决方案.

那么为什么我们仍然有不同的范式名称以及为什么我将动态编程称为扩展.这是因为只有当问题具有某些限制或先决条件时,才可以将动态编程方法应用于该问题.之后,动态编程通过memoization或制表技术扩展了分而治之的方法.

我们一步一步走......

动态编程先决条件/限制

正如我们刚刚发现的那样,为了使动态编程适用,有两个关键属性可以划分和征服问题:

• 最优子结构  - 最优解可以从其子问题的最优解构造

• 重叠的子问题  - 问题可以分解为多次重复使用的子问题,或者问题的递归算法一遍又一遍地解决相同的子问题,而不是总是生成新的子问题

一旦满足这两个条件,我们可以说使用动态编程方法可以解决这种分而治之的问题.

分治的动态规划扩展

动态编程方法通过两种技术(memoization和制表)扩展了分而治之的方法,这两种技术都有一个存储和重用子问题解决方案的目的,可以大大提高性能.例如,Fibonacci函数的朴素递归实现具有时间复杂性,O(2^n)其中DP解决方案仅在O(n)时间内执行相同操作.

Memoization(自上而下缓存填充)是指缓存和重用先前计算结果的技术.因此,memoized fib函数看起来像这样:

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)

        mem[n] = result
    return mem[n]
}

制表(自下而上缓存填充)类似,但重点是填充缓存的条目.迭代地计算缓存中的值是最容易的.制表版本fib将如下所示:

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

您可以在此处阅读有关记忆和制表比较的更多信息.

你应该掌握的主要思想是,因为我们的分而治之问题存在重叠的子问题,所以子问题解决方案的缓存成为可能,因此记忆/制表逐步上升到现场.

那么DP和DC毕竟有什么区别呢

由于我们现在熟悉DP先决条件及其方法,我们已准备好将上面提到的所有内容放在一张图片中.

如果您想查看代码示例,可以在此处查看更详细的说明,其中您将找到两个算法示例:二进制搜索和最小编辑距离(Levenshtein距离),它们说明了DP和DC之间的差异.

Answer 5

我假设您已经阅读过维基百科及其他学术资源,因此我不会回收任何这些信息.我还必须指出,我不是一个计算机科学专家,但我会分享我对这些主题的理解.

动态编程

将问题分解为离散的子问题.Fibonacci序列的递归算法是动态规划的一个例子,因为它通过首先求解fib(n-1)来求解fib(n).为了解决原始问题,它解决了一个不同的问题.

分而治之

这些算法通常解决问题的类似部分,然后将它们放在一起.Mergesort是分而治之的典型例子.这个例子与Fibonacci例子的主要区别在于,在mergesort中,除法可以(理论上)是任意的,无论你如何对它进行分割,你仍然在合并和排序.无论你如何分割数组,都必须完成相同数量的工作来合并数组.解决fib(52)需要比解决fib(2)更多的步骤.

Answer 6

我认为Divide & Conquer是一种递归方法和Dynamic Programming表填充.

例如,Merge Sort是一个Divide & Conquer算法,如在每个步骤中,您将数组分成两半,递归调用Merge Sort两半,然后合并它们.

Knapsack是一种Dynamic Programming算法,因为您填写的表格表示整体背包的子问题的最佳解决方案.表中的每个条目对应于给定项目1-j的重量包中可以携带的最大值.

Answer 7

分而治之在每个递归级别都涉及三个步骤：

1. 将问题划分为子问题。
2. 通过递归解决子问题来解决它们。
3. 将子问题的解决方案合并到原始问题的解决方案中。
   
   • 这是一种自上而下的方法。
     
   • 它在子问题上做更多的工作，因此消耗更多的时间。
   • 例如。斐波那契数列的第 n 项可以以 O(2^n) 时间复杂度计算。
     
     

动态规划包括以下四个步骤：

1.描述最优解的结构。
2.递归地定义最优解的值。
3.计算最优解的值。
4.根据计算信息构建最优解决方案。

• 这是一种自下而上的方法。
• 比分治法消耗的时间更少，因为我们使用之前计算的值，而不是再次计算。
• 例如。斐波那契数列的第 n 项可以以 O(n) 时间复杂度计算。
  
  

为了更容易理解，让我们将分而治之视为强力解决方案，并将其优化视为动态规划。

NB具有重叠子问题的分而治之算法只能用 dp 来优化。