动态规划(一)

  • 算法动态规划部分(一),包括 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))

编号动态规划

  • 输入为 $x_1$ , $x_2$ , … ,$x_n$ ,子问题是 $x_1$ , $x_2$ , … ,$x_i$ ,子问题的复杂性是 $O(n)$.

  • 子结构的表示方法

    • 状态i表示前i个元素构成的最优解,可能不包括第i个元素.
    • 状态i表示前i个元素构成的最优解,必须包含第i个元素.
  • 这里的例子是最长 递增/不下降 子序列问题.

最长递增子序列

  • 问题定义

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

      $$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]$

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

  • 分析

    • 优化子结构

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

      • 以 $a_k$ $a_{k+1}$ 为例
      • $a_1,…,a_{k}$ 与 $a_1,…,a_{k+1}$ 的重叠子问题: $a_1,a_2, …,a_{k-1}$ 这个子序列 LIS 的最优解.
    • 所以LIS问题可以通过动态规划求解.

  • 其他

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

    • 最优解递归方程

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

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

  • 时间复杂度为 $nlogn$

    • 不再维护一个 $dp[i]$ 数组,转而维护 $tails[i]$ .
    • $tails[i]$ 代表了序列中长度为 i 的子序列的最小值.同时维护一个 size 变量,代表 $tails[i]$ 目前的最大有效长度.
    • 从前往后遍历整个序列,与 $tails[i]$ 比较,若在 $tails[,]$ 中某个位置,则更新对应位置的 $tails[i]$ .若大于 $tails[,]$ 的最大值,则 size+=1 并在对应位置存入该值.
    • 这里因为 $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

划分动态规划

  • 输入为 $x_1$ , $x_2$ , … ,$x_n$ ,子问题是 $x_i$ , $x_{i+1}$ , … ,$x_j$ ,子问题的复杂性是 $O(n^2)$.

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

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

凸多边形的最优三角剖分

  • 问题定义

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

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

    • 子问题表示: $matrix[i,j] = < v_i,…,v_j >$ 的最优三角剖分代价.
    • 最优解递归方程:
      • $$matrix[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]

数轴动态规划

  • 输入为 $x_1$ , $x_2$ , … ,$x_n$ 和数字C,子问题是 $x_1$ , $x_2$ , … ,$x_i$ $K(K<C)$,子问题的复杂性是 $O(nC)$.

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

0-1背包

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

  • 问题定义

    • 给定n种物品和一个背包,物品 i 的重量为 $w_i$ 价值为 $v_i$ ,背包容量为C,要求选择转入背包的物品使得背包的总价值最大.
    • 0-1背包限定物品只能选择装入/不装入,一个物品仅装入一次.
    • input: ${w_1,..,w_n \mid w_i > 0, i\in(1,n)}$ , ${v_1,..,v_n \mid v_i > 0,i\in(1,n)}$ , $C(C>0)$
    • output: ${x_1,x_2..,x_n \mid x_i\in(0,1)}$ 且 $\sum_{1\leq i \leq n}{v_i x_i} \leq C$, $Max\sum_{1\leq i \leq n}{w_i x_i}$
    • 我们这里假定$w_i$以及C 都是整数.
  • 分析

    • 优化子结构

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

        • $y_n=0$,没选,子问题就是去掉最后一个物品,C的0-1背包问题的优化解.
        • $y_n=1$,选了,子问题就是去掉最后一个物品,$C-w_n$的0-1背包问题的优化解.
      • 合并以上情况,子问题定义

      • $$max
        \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}$$

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

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

        $x_n=1$再加上$v_i$,$(z_1,…,z_{n-1},x_n)$就是原问题的最优解,与前提矛盾.

    • 重叠子问题

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

    • 子问题定义
      $matrix[m][n]$背包容量为n,可选物品为前m个时的最优解.
    • 最优解递归方程:
    • $$matrix[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]

前缀动态规划

  • 输入为 $x_1$ , $x_2$ , … ,$x_n$ 和 $y_1$ , $y_2$ , … ,$y_n$,子问题是 $x_1$ , $x_2$ , … ,$x_i$ 和 $y_1$ , $y_2$ , … ,$y_j$,子问题的复杂性是 $O(mn)$.

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

字符串编辑距离

  • 编辑距离

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

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

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

      1. $b_n$替换$a_m$,则子问题$D_{m-1,n-1} = D_{mn}-c(a_m,b_n)$
        $if,a_m==b_n , c = 0 , else , c = 1$
      2. 删除$a_m$,则子问题$D_{m-1,n} = D_{mn}-1$
      3. 插入$b_n$,则子问题$D_{m,n-1} = D_{mn}-1$
      • 证明: 反证法,不再赘述.
    • 重叠子问题

      • 以$D_{m,n}$与$D_{m-1,n}$ $D_{m,n-1}$ 和 $D_{m-1,n-1}$ 为例.
      • 通过优化子结构分析得知,计算$D_{i,j}$需要用到$D_{i-1,j}$ $D_{i,j-1} 和$D_{i-1,j-1},对应数据结构是一个二维矩阵,图形化后,正好对应元素上,左,左上.3个位置.
      • $D_{m,n}$ 与 $D_{m-1,n}$ $D_{m,n-1}$ 和 $D_{m-1,n-1}$ 的公共区域是以 $D_{0,0} \mid D_{m-1,n-1}$ 为对角线的公共矩形区域.
    • 所以编辑距离可以使用动态规划求解.

  • 其他

    • 子问题定义: $matrix[m][n]$表示字符串A的前m个字符与B字符串前n个字符的编辑距离.
    • 最优解递归方程:
    • $$matrix[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模块生成的随机字符串,几次生成之间几乎没有重复,手输几个看结果即可.

树型动态规划

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