动态规划(一)

发表于 分类于 ， 阅读次数： Disqus： 本文字数： 11k 阅读时长 ≈ 10 分钟

  • 算法动态规划部分(一),包括 python 源代码

  • 更新

    1
    19.02.06 初始
  • 参考资料

    https://www.zybuluo.com/codeep/note/163962
    https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000
    https://mooc.study.163.com/course/1000005000

导语

  • 计划重新整理一遍算法与数据结构,开始选择c实现,但是到了算法部分,这个吐血…
  • 无奈用python重写,好处是与伪代码几乎对应.恩,人生苦短,我用python.
  • 遂决定把算法部分重刷一遍,希望自己能刷完.

动态规划

概述

  • 动态规划简述是 把原问题分解为相对简单的子问题,再依次求解最终解决原问题的方法。

  • 许多子问题非常相似,动态规划中某个给定子问题的解已经得出，则存储，以便下次需要同一个子问题解之时直接查表。所以动态规划在输入的规模呈指数增长时特别有用。

  • 一个问题是否适用于动态规划求解,取决于 重叠子问题 最优子结构 和 无后效性

    • 最优子结构性质: 问题的最优解所包含的子问题的解也是最优的，可以通过求解子问题的最优解,来求解原问题.
    • 重叠子问题: 在自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划通过保存已求解的子问题答案,避免冗余计算.
    • 无后效性: 子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

  • 动态规划基本求解步骤

    • 分析优化解结构
    • 递归定义最优解代价
    • 自底向上计算最优解代价并保存子问题最优解
    • 根据最优解信息,构造优化解

randoms类

  • 提供原始数据,随机生成int , str 等.

  • 计算函数运行时间.

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class randoms(object):
      @classmethod
      def list_int(self, n=50, w=100):
          return [random.randint(0, w) for i in range(n)]

      @classmethod
      def list_str(self, lens=20, capital=True):
          return secrets.token_urlsafe(lens)

      @classmethod
      def time(self, method, setus):
          if callable(method):
              if isinstance(setus, str):
                  print(timeit.timeit(method, number=10, setup=setus))
              else:
                  print('setus is not str')
          else:
              print("%s is not a method" % method)

  • 测试文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class test_randoms(unittest.TestCase):
      def test_list_int(self):
          arr = randoms.list_int()
          self.assertTrue(isinstance(arr, list))
          for x in arr:
              self.assertTrue(isinstance(x, int))

      def test_list_str(self):
          strs = randoms.list_str()
          print(strs)
          self.assertTrue(isinstance(strs, str))

编号动态规划

  • 输入为 x1x_1 , x2x_2 , … ,xnx_n ,子问题是 x1x_1 , x2x_2 , … ,xix_i ,子问题的复杂性是 O(n)O(n).

  • 子结构的表示方法

    • 状态i表示前i个元素构成的最优解,可能不包括第i个元素.
    • 状态i表示前i个元素构成的最优解,必须包含第i个元素.

  • 这里的例子是最长 递增/不下降 子序列问题.

最长递增子序列

  • 问题定义

    • 子序列是数字序列的子集合,且与序列中的数字顺序相同.即

      ai1,ai2...,aik(1≤i1≤i2...≤ik≤n)a_{i_1},a_{i_2}...,a_{i_k}(1 \leq i_1 \leq i_2...\leq i_k \leq n)

    • 递增子序列是数字严格递增的子序列.不下降子序列即包括相等的元素.

    • 最长递增子序列LIS (Longest Increasing Subsequence),与最长不下降 子序列区别: 是否包括相同元素.

    • input: 一个数字序列 a[1...n]a[1...n]

    • output: 最大长度的递增子序列.(为了方便,这里仅输出递增子序列的长度)

  • 分析

    • 优化子结构

      • 假设 LIS 包含aka_k,那么一定存在一组最优解LISA,包含了 a1,a2,...,ak−1a_1,a_2,...,a_{k-1} 这个子序列的LIS.
      • 证明: 假设原序列的LIS的最优解 LISA 没有包含 a1,a2,...,ak−1a_1,a_2,...,a_{k-1} 这个子序列 LIS 的最优解 LISB ,那么 LISB + aka_k 就是一个 比 LISA 更优的解,与假设矛盾.

    • 重叠子问题

      • 以 aka_k ak+1a_{k+1} 为例
      • a1,...,aka_1,...,a_{k} 与 a1,...,ak+1a_1,...,a_{k+1} 的重叠子问题: a1,a2,...,ak−1a_1,a_2, ...,a_{k-1} 这个子序列 LIS 的最优解.

    • 所以LIS问题可以通过动态规划求解.

  • 其他

    • 子问题表示: dp[i]dp[i] 表示以第 i 个元素结尾的前i个元素构成序列的最长递增子序列的长度.

    • 最优解递归方程

      dp[i]=max{dp[j]∣0<j<i ; aj>ai}+1dp[i] = max \left\{ dp[j] \mid 0<j<i \,;\, a_j > a_i \right\} + 1

    • 注意 dp[i]dp[i] 表示的并不是前i个元素组成序列的LIS最优解.

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def lis_dp(self, arr):
      # dp = [0 for x in range(0, len(arr))]
      dp = [0] * len(arr) # 更方便
      for i, valuei in enumerate(arr):
          for j, valuej in enumerate(arr[0:i]):
              if valuej < valuei and dp[j] > dp[i]:
                  dp[i] = dp[j]
          dp[i] += 1
      return max(dp) # 返回LIS最优解还需要遍历回溯dp[]

  • 时间复杂度为 n2n^2 ,并不是最优的.分析来看时间主要花费在了 if valuej < valuei and dp[j] > dp[i]: 这个比较判断上,需要对此做出改进.

  • 时间复杂度为 nlognnlogn

    • 不再维护一个 dp[i]dp[i] 数组,转而维护 tails[i]tails[i] .
    • tails[i]tails[i] 代表了序列中长度为 i 的子序列的最小值.同时维护一个 size 变量,代表 tails[i]tails[i] 目前的最大有效长度.
    • 从前往后遍历整个序列,与 tails[i]tails[i] 比较,若在 tails[ ]tails[\,] 中某个位置,则更新对应位置的 tails[i]tails[i] .若大于 tails[ ]tails[\,] 的最大值,则 size+=1 并在对应位置存入该值.
    • 这里因为 tails[i]tails[i] 为递增的,可以使用二分查找.降低时间复杂度.
    • 当序列遍历完成后,size即为LIS的最大值.

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def lis_dp_binse(self, arr):
      tails = [0] * len(arr)
      size = 0
      for x in arr:
          i, j = 0, size
          while i != j:
              m = (i + j) // 2
              if tails[m] <= x:
                  i = m + 1
              else:
                  j = m
          tails[i] = x
          size = max(i + 1, size)
      return size

  • 测试

    1
    2
    3
    4
    5
    6
    if __name__ == "__main__":
      arr = randoms.list_int(500)
      n = functools.partial(lis.lis_dp, arr)
      s = functools.partial(lis.lis_dp_binse, arr)
      randoms.time(n, 'from lis import lis'),
      randoms.time(s, 'from lis import lis')

    结果如下

    1
    2
    0.4465395999999999
    0.026626600000000167

划分动态规划

  • 输入为 x1x_1 , x2x_2 , … ,xnx_n ,子问题是 xix_i , xi+1x_{i+1} , … ,xjx_j ,子问题的复杂性是 O(n2)O(n^2).

  • 这里的例子是 凸多边形的最优三角剖分, 矩阵链乘.

  • 两者很相似,矩阵链乘是用c写的,代码量实在太多,故仅提供 凸多边形的最优三角剖分的 python 代码.

凸多边形的最优三角剖分

  • 问题定义

    • 多边形: 一个顶点的坐标集合 P=(v0,v1,...vn)P=\left( v_0,v_1,...v_n \right) 或者顶点的序列 v0,v1,...vnv_0,v_1,...v_n
    • 简单多边形: 除顶点外没有任何交叉点的多边形,这个问题涉及到的都是简单多边形.
    • 弦: 多边形 P 上的任意两个不相邻的节点 vi, vi+1v_i,\,v_{i+1} 所对应的线段.vivi+1v_iv_{i+1} 称为弦.
    • 三角剖分: 多边形P的三角剖分是将P划分为不相交的三角剖分弦的集合.
    • 输入: 多边形P(序列)和代价函数W(任意)
    • 输出: P的三角剖分T,使得 ∑s∈STW(s)\sum_{s\in S_T}{W\left(s\right)} 最小.

  • 分析

    • 优化子结构
      • P=(v0,v1,...vn)P=\left( v_0,v_1,...v_n \right) 是 n+1 个顶点的多边形.TpT_p 是 P 的最优三角剖分, vkv_k 是 v0vnv_0 v_n中间一点.v0,vk,vnv_0,v_k,v_n构成一个三角形,则有:
        Tp=T( v0,...,vk)⋃T( vk,...,vn)⋃{v0vk,vkvn,vnv0}T_p=T\left(\ v_0,...,v_k \right)\bigcup T\left(\ v_k,...,v_n \right)\bigcup \{v_0 v_k,v_k v_n,v_n v_0\}
      • T( v0,...,vk)T\left(\ v_0,...,v_k \right) 与 T( vk,...,vn)T\left(\ v_k,...,v_n \right) 分别对应( v0,...,vk)\left(\ v_0,...,v_k \right) 和 ( vk,...,vn)\left(\ v_k,...,v_n \right) 的最优三角剖分.
      • 证明: 假设 T( v0,...,vk)T\left(\ v_0,...,v_k \right) 不是 ( v0,...,vk)\left(\ v_0,...,v_k \right) 的最优三角剖分,则 ( v0,...,vk)\left(\ v_0,...,v_k \right) 的最优三角剖分带回原式中会得到比 TpT_p 更优的解.与前提矛盾,故不成立.
      • 因为不知道具体 vkv_k 的取值,需要计算由 k∈{0,n}k\in\{0,n\} 所有取值,取到使 TpT_p 最小的 vkv_k .
    • 重叠子问题
      • 以(v0,...vk)\left( v_0,...v_{k} \right) 和 (v0,...vk+1)\left( v_0,...v_{k+1} \right) 为例.
      • 在确定 vkv_k 的循环中,(v0,...vk)\left( v_0,...v_{k} \right) 和 (v0,...vk+1)\left( v_0,...v_{k+1} \right) 用到的子问题结果除 T( v0,...,vk)T\left(\ v_0,...,v_k \right)外,完全一致,因此适用于动态规划求解.

  • 其他

    • 子问题表示: matrix[i,j]=<vi,...,vj>matrix[i,j] = < v_i,...,v_j > 的最优三角剖分代价.
    • 最优解递归方程:

      • matrix[i,j]={0j-i < 2 mini≤k<j{matrix[i,k]+matrix[k,j]+w(i,k,j)}othermatrix[i,j] = \begin{cases} 0& \text{j-i < 2 }\\ min_{i\leq k < j} \{matrix[i,k]+matrix[k,j]+w(i,k,j)\}& \text{other}\\ \end{cases}

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class aot(object):
      # 仅返回和
      def w(self, key1, key2, key3, arr):
          return (arr[key1] + arr[key2] + arr[key3])

      def aots(self, start, end, arr):
          matrix = [[0 for i in range(len(arr) + 1)]
                    for j in range(len(arr) + 1)]

          for i in range(start, end + 1):
              m = start
              n = i
              while m <= start + end - i and n <= end:
                  if abs(m - n) <= 1:
                      matrix[m][n] = 0
                  else:
                      matrix[m][n] = \
                          min([matrix[m][k]+matrix[k][n]+self.w(m, k, n, arr) for k in range(m+1, n)])
                  m += 1
                  n += 1
          return matrix[start][end]

数轴动态规划

  • 输入为 x1x_1 , x2x_2 , … ,xnx_n 和数字C,子问题是 x1x_1 , x2x_2 , … ,xix_i K(K<C)K(K<C),子问题的复杂性是 O(nC)O(nC).

  • 这里的例子是0-1背包问题.

0-1背包

  • 一个经典的组合优化问题.背包问题通常适用于动态规划和贪心法.贪心法对于0-1背包可能无法产生最优解.

  • 问题定义

    • 给定n种物品和一个背包,物品 i 的重量为 wiw_i 价值为 viv_i ,背包容量为C,要求选择转入背包的物品使得背包的总价值最大.
    • 0-1背包限定物品只能选择装入/不装入,一个物品仅装入一次.
    • input: {w1,..,wn∣wi>0,i∈(1,n)}\{w_1,..,w_n \mid w_i > 0, i\in(1,n)\} , {v1,..,vn∣vi>0,i∈(1,n)}\{v_1,..,v_n \mid v_i > 0,i\in(1,n)\} , C(C>0)C(C>0)
    • output: {x1,x2..,xn∣xi∈(0,1)}\{x_1,x_2..,x_n \mid x_i\in(0,1)\} 且 ∑1≤i≤nvixi≤C\sum_{1\leq i \leq n}{v_i x_i} \leq C, Max∑1≤i≤nwixiMax\sum_{1\leq i \leq n}{w_i x_i}
    • 我们这里假定wiw_i以及C 都是整数.

  • 分析

    • 优化子结构

      • 假设(y1,y2,...,yn)(y_1,y_2,...,y_n)是0-1背包的优化解,则(y1,...,yn−1)(y_1,...,y_{n-1}),是子问题的优化解,子问题分两种情况

        • yn=0y_n=0,没选,子问题就是去掉最后一个物品,C的0-1背包问题的优化解.
        • yn=1y_n=1,选了,子问题就是去掉最后一个物品,C−wnC-w_n的0-1背包问题的优化解.

      • 合并以上情况,子问题定义

      • max{∑1≤i≤n−1vixi∣∑1≤i≤n−1wixi≤C∑1≤i≤n−1vixi+v1∣∑1≤i≤n−1wixi≤C−wnmax \begin{cases} \sum_{1\leq i\leq n-1}{v_i x_i} \mid {\sum_{1\leq i\leq n-1}{w_i x_i \leq C}}\\ \sum_{1\leq i\leq n-1}{v_i x_i} + v_1 \mid {\sum_{1\leq i\leq n-1}{w_i x_i \leq C-w_n}} \end{cases}

      • 证明:
        假设 (y1,...,yn−1)(y_1,...,y_{n-1}) 不是子问题的优化解,那么存在更优解(z1,...,zn−1)(z_1,...,z_{n-1}).

        xn=0x_n=0没选,(z1,...,zn−1)(z_1,...,z_{n-1})就是的原问题的最优解,与前提矛盾.

        xn=1x_n=1再加上viv_i,(z1,...,zn−1,xn)(z_1,...,z_{n-1},x_n)就是原问题的最优解,与前提矛盾.

    • 重叠子问题

      • 分析见优化子结构.
      • 因为不知道wiw_i的具体数值,只能假设C为整数,wiw_i为整数的前提下,将背包的容量(1≤i≤C)(1\leq i \leq C)全部算出.需要二维数组存储子问题的计算结果.

  • 其他

    • 子问题定义
      matrix[m][n]matrix[m][n]背包容量为n,可选物品为前m个时的最优解.
    • 最优解递归方程:

    • matrix[m][n]=Max{matrix[m−1][n]matrix[m][n−wm]+vmmatrix[m][n]= Max \begin{cases} matrix[m-1][n] \\ matrix[m][n-w_m]+v_m \end{cases}

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def kp_dp(self, weight, value, wlimted):
      lens = len(weight)
      # 忽略matrix[0][x] matrix[x][0]
      matrix = [[0 for i in range(wlimted + 1)] for j in range(lens + 1)]
      # 填充 m=1 第一排
      for i in range(1, wlimted + 1):
          if i >= weight[1]:
              matrix[1][i] = value[1]
          else:
              matrix[1][i] = 0
      # 最优解递归方程
      for m in range(2, lens + 1):
          for n in range(1, wlimted + 1):
              # 可以以装入物品,输入的weight[]value[]值自0开始.
              if n >= weight[m-1]:
                  matrix[m][n] = max(
                      matrix[m - 1][n],
                      matrix[m - 1][n - weight[m - 1]] + value[m - 1])
              else:
                  matrix[m][n] = matrix[m - 1][n]

      return matrix[lens][wlimted]

前缀动态规划

  • 输入为 x1x_1 , x2x_2 , … ,xnx_n 和 y1y_1 , y2y_2 , … ,yny_n,子问题是 x1x_1 , x2x_2 , … ,xix_i 和 y1y_1 , y2y_2 , … ,yjy_j,子问题的复杂性是 O(mn)O(mn).

  • 典型的例子是 最长公共子序列(LCS) 和 字符串编辑距离

字符串编辑距离

  • 编辑距离

    • 编辑距离是衡量两个字符串相似程度的指标.具体指将A字符串转换成B字符串的最小代价.
    • 包括 B 中字符替换 A 中字符.删除A中字符,插入B中字符.

  • 问题定义

    • 编辑操作: 替换,删除,插入
    • input: 两个字符串 A=a1a2...amA=a_1 a_2...a_m 和 B=b1b2...bmB=b_1b_2...b_m
    • output: A转换为B的编辑的最小代价.

  • 分析

    • 优化子结构
      假设DmnD_{mn}是A与B的编辑距离.那么子问题可以分为3种情况,分别对应编辑距离定义的3中操作.

      1. bnb_n替换ama_m,则子问题Dm−1,n−1=Dmn−c(am,bn)D_{m-1,n-1} = D_{mn}-c(a_m,b_n)
        if am==bn c=0 else c=1if\,a_m==b_n \, c = 0 \, else \, c = 1
      2. 删除ama_m,则子问题Dm−1,n=Dmn−1D_{m-1,n} = D_{mn}-1
      3. 插入bnb_n,则子问题Dm,n−1=Dmn−1D_{m,n-1} = D_{mn}-1
      • 证明: 反证法,不再赘述.

    • 重叠子问题

      • 以Dm,nD_{m,n}与Dm−1,nD_{m-1,n} Dm,n−1D_{m,n-1} 和 Dm−1,n−1D_{m-1,n-1} 为例.
      • 通过优化子结构分析得知,计算Di,jD_{i,j}需要用到Di−1,jD_{i-1,j} Di,j−1和D_{i,j-1} 和D_{i-1,j-1},对应数据结构是一个二维矩阵,图形化后,正好对应元素上,左,左上.3个位置.
      • Dm,nD_{m,n} 与 Dm−1,nD_{m-1,n} Dm,n−1D_{m,n-1} 和 Dm−1,n−1D_{m-1,n-1} 的公共区域是以 D0,0∣Dm−1,n−1D_{0,0} \mid D_{m-1,n-1} 为对角线的公共矩形区域.

    • 所以编辑距离可以使用动态规划求解.

  • 其他

    • 子问题定义: matrix[m][n]matrix[m][n]表示字符串A的前m个字符与B字符串前n个字符的编辑距离.
    • 最优解递归方程:

    • matrix[m][n]=Min{matrix[m−1][n−1]+c(am,bn)matrix[m][n−1]+1matrix[m−1][n]+1matrix[m][n]= Min \begin{cases} matrix[m-1][n-1] +c(a_m,b_n) \\ matrix[m][n-1] + 1 \\ matrix[m-1][n] + 1 \end{cases}

    • python中字符串下标由0开始,需要额外注意一下.
    • 矩阵的填充顺序:
      1. 第一排,按照插入的子问题代价填入
      2. 第一列,按照插入的子问题代价填入
      3. 依次从左往右,由上到下填充整个矩阵.

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class ed(object):
      def editdistance(self, stra, strb):
          matrix = [[0 for i in range(len(strb) + 1)]
                    for j in range(len(stra) + 1)]
          # 左上角
          matrix[0][0] = 0
          # 第一列
          for m in range(1, len(stra) + 1):
              matrix[m][0] = m
          # 第一排
          for n in range(1, len(strb) + 1):
              matrix[0][n] = n
          # 其他
          for m in range(1, len(stra) + 1):
              for n in range(1, len(strb) + 1):
                  matrix[m][n] = min(
                      matrix[m - 1][n] + 1, matrix[m][n - 1] + 1,
                      matrix[m - 1][n - 1] +
                      (0 if stra[m - 1] == strb[n - 1] else 1))

          return matrix[len(stra)][len(strb)]

  • ps: randoms.list_str 是 引用secrets模块生成的随机字符串,几次生成之间几乎没有重复,手输几个看结果即可.

树型动态规划

  • 详情-算法-动态规划(二)