关于算法:Golang-算法导论动态规划Dynamic-Programming理解-一

42次阅读

共计 1833 个字符,预计需要花费 5 分钟才能阅读完成。

本篇内容为浏览《算法导论》动静布局算法设计时的一些了解和记录。倡议大家去看原书,真的好。

动静布局 有点像 分治法 ,都是通过合并原问题的子问题的解来失去原问题的解。不同的是 分治法 将原问题划分为不相交的子问题,递归地解决子问题,而后组合它们的解来失去原问题的解。而 动静布局 须要原问题划分为有重叠的子问题,即其子问题又须要独特的子子问题。

当划分的子问题有重叠时,应用 分治法 会导致重叠子问题的反复计算。动静布局 实际上就是通过存储子问题的解来防止这样的反复计算,这是 动静布局 的根本思维。

动静布局 个别用于求一个最优解的问题,解决这样的问题蕴含四步:

  • 演绎出一个最优解的构造。
  • 递归定义一个最优解的值。
  • 计算一个最优解的值。(个别应用从底向上的形式)
  • 从结算中构建出最优解。

这样直白的语言概括其实很难了解的,还须要依据例子来了解,《算法导论》中给出了几个例子,咱们也借用他来记录一下。

例一

将一根长度为 n 的铁棒进行宰割,不同长度能够卖不同的价格(遵循一个价格表 P),问能够卖出的最大的价格是多少?(一个最优解的问题)

设长度为 n 的铁棍通过切割最多能卖出的价格为 rn,第一次宰割的长度为 i,其余部分为 n-i。其中 i 的范畴是 [1,n],那咱们能够示意出 rn

rn = max (pi + rn-i)

留神 i 的范畴是 [1,n],这里的 max 要求的是例如 p 1 + rn-1,p2 + rn-2,… 之类的最大值。

很显然,这是个递归,咱们很容易写出代码(Go):

func cutRod(p []int, n int) int {
  if n == 0 {return 0}
  q := math.MinInt
  for i := 1; i <= n; i++ {q = max(q, p[i]+cutRod(p, n-i))
  }
  return q
}

理论运行中,咱们会发现,效率十分非常低。。。为什么呢?因为计算中存在了大量的冗余,例如 n = 3 的计算过程须要 cutRod(p, 0),cutRod(p, 1),cutRod(p, 2)。而计算 cutRod(p, 2) 须要 cutRod(p, 1)cutRod(p, 0)。计算 cutRod(p, 1) 须要 cutRod(p, 0)。这个过程中,很多雷同的函数计算了屡次。能够证实的是,该算法复杂度是指数级别的。

如何进行优化呢?直观的,咱们存储每个函数的执行后果,当发现执行的雷同的函数时,间接返回值就好,这是个空间换工夫的考量。先贴代码(Go):

func cutRod(p []int, n int) int {var r []int
   for i := 0; i < n; i++ {r = append(r, math.MinInt)
   }
   return cutRodAux(p, n, r)

}

func cutRodAux(p []int, n int, r []int) int {if r[n] >= 0 {return r[n]
   }
   q := math.MinInt
   if n == 0 {q = 0} else {
      for i := 1; i <= n; i++ {q = max(q, p[i]+cutRodAux(p, n-i, r))
      }
   }
   r[n] = q
   return q
}

咱们额定开拓了一个数组 r 用来记录曾经计算过的函数的值,其中 r[n] 代表长度为 n 的铁棒通过切割最多能卖出的价格。

咱们这个办法是 自上而下 计算的,艰深一点,就是采纳递归的形式,我想要算 A,在计算过程中我发现须要 B 的后果,所以我压栈,而后去算 B

递归是有老本耗费的。咱们能够选用 自下而上 的形式来防止这个耗费,即 我曾经晓得 B 的后果了,我发现只须要一步就能算出 A,所以我只花了一步失去了 A 的后果。

自下而上 能够间接应用循环的形式实现,先贴代码(Go):

func cutRod(p []int, n int) int {var r []int
   r = append(r, 0)
   for j := 1; j <= n; j++ {
      q := math.MinInt
      for i := 1; i <= j; i++ {q = max(q, p[i]+r[j-i])
      }
      r[j] = q
   }
   return r[n]
}

模式上看起来是不是更简略!自下而上 中“最上面”的 base case 个别能够间接看进去,如这个例子中的 r[0],显然等于 0。咱们依据这个 base case,一直失去 r[1]r[2]…,能够始终计算正无穷,然而咱们只须要计算到 n 即可满足咱们算法要求,也就是外层循环计算到 n 的起因。

自上而下 就像 深度优先搜寻 自下而上 就像 逆拓扑排序

当咱们思考一个动静布局问题时,咱们应该了解所波及的子问题的汇合,以及子问题之间如何相互依赖。

之后咱们将持续介绍其余动静布局问题的案例,同时将摸索什么样的问题适宜用动静布局解决。

正文完
 0