0%

算法-动态规划(二)

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

  • 更新

    1
    19.02.13 初始

导语

  • 还是没有整理完二叉树部分,用c一时,重构一世…树的独立集合,放在数据结构部分再搞了.
  • 下一篇是贪心法和拟阵

动态规划

概述

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

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

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

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

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

randoms类

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

  • 计算函数运行时间.

  • 代码

    1
    2
    3
    4
    5
    6
    class randoms(object):
    @classmethod
    def matrix(self, size=10, limt=10):
    matrix = [[random.randint(0, limt) for i in range(size)]
    for j in range(size)]
    return matrix
  • 在原有 randoms 类中添加无负权的有向图生成.(当然这样每个结点都相连..)

树型动态规划

  • 输入是树,子问题是子树,复杂性是子树的个数.

最优二叉搜索树

  • 与划分动态规划类似.

  • 问题定义

    • 二叉搜索树(BST):

      • Optimal BST

      • 结点

        • $K={k_1,k_2,…,k_n}$
        • $D={d_0,d_1,…,d_n}$
        • $d_i$对应区间$(k_i,k_{i+1})$,$d_0$对应$(-\infty,k_1)$,$d_n$对应$(k_n,+\infty)$.
      • 搜索概率

        • 搜索到$k_i$的概率为$p_i$
        • 搜索到$d_i$的概率为$q_i$
        • $\sum_{i=1}^{n}{p_i}+\sum_{j=0}^{n}{q_j}=1$
      • 搜索期望

        $$E(T)=\sum_{i=1}^{n}{(DEP_T(k_i)+1)}p_i+\sum_{j=0}^{n}{(DEP_T(d_j)+1)}q_j$$

    • 构建最优二叉搜索树(Optimal BST),即对于相同的搜索概率下,构建搜索期望最小的二叉搜索树

    • input: $K={k_1,k_2,…,K_n},k_1<k_2<…<k_n$, $k_i$概率对应$P={p_1,p_2,..,p_n}$. $d_i$的概率对应$Q={q_0,p_1,..,q_n}$.

    • output: K的最优二叉搜索树,$E(T)$最小.

  • 分析

    • 优化子结构
      • 如果最优二叉搜索树$T$有一子树 $T’$ ,包含关键词 ${k_i,k_{i+1},..,k_j}$ ,则 $T’$ 是集合 ${k_i,k_{i+1},..,k_j}$ 的最优搜索二叉树.
      • 证明: 假设 $T’$ 不是集合 ${k_i,k_{i+1},..,k_j}$ 的最优搜索二叉树.则存在 $T’’$ 为集合 ${k_i,k_{i+1},..,k_j}$ 的最优搜索二叉树, $T’’$ 替换 $T’$ 在 $T$ 的位置,得到了比 $T$ 更优的解,与前提矛盾.
      • 在输入的 $K={k_1,k_2,…,K_n},k_1<k_2<…<k_n$ 中,一定存在一个 $k_r$ 作为OBST的根节点.因为无法事前知道 $k_r$ .只能从 $k_1,..,k_n$ 遍历.
    • 重叠子问题
      • 如优化子结构分析.
      • 在输入为 $K1={k_1,k_2,…,k_{n-1}}$ 与 $K2={k_1,k_2,…,k_n}$ 时,子问题求解 $k_r$ ,所需要的子问题的解基本相同.
    • 最优二叉搜索树可以使用动态规划求解.
  • 其他

    • $matrix[i,j]$ 为 ${k_i,…,k_j}$ 的最优二叉搜索树的搜索期望.
    • 当 $j=i-1$ ,集合中只有叶节点 $d_{i-1}$ , $matrix[i,i-1]=q_{i-1}$
    • 当 $j>i-1$ ,集合中存在可以选定为 $k_r$ 的根节点,此时假定我们选择的是 $k_r$.其 $matrix[i,j]$ 可以表示为 $matrix[i,j] = matrix[i,r-1] + p_r + matrix[r+1,j] + w(i,r-1) + w(r+1,j)$
      • $w(i,r-1)$ 为集合${k_i,…,k_{r-1}}$选定为左子树,全部深度+1,后的最优二叉搜索树的搜索期望与 $matrix[i,r-1]$ 的差值.
        • $$E(T)=\sum_{l=i}^{r-1}{(DEP_T(k_l)+1)}p_l+\sum_{j=i-1}^{r-1}{(DEP_T(d_j)+1)}q_j$$
        • $$E(T+1)=\sum_{l=i}^{r-1}{(DEP_T(k_l)+2)}p_l+\sum_{j=i-1}^{r-1}{(DEP_T(d_j)+2)}q_j$$
      • 则 $w(i,r-1) = \sum_{l=i}^{r-1}{p_l}+\sum_{j=i-1}^{r-1}{q_j}$,可以合并 $matrix[i,j]$ 表达式中的 $w(i,r-1),w(r+1,j)$ 为 $w(i,j)$ ,且 $w(i,j) = \sum_{l=i}^{j}{p_l}+\sum_{s=i-1}^{j}{q_s} - p_r - q_r$
      • 因为并不知道 $k_r$ 具体取值,只能遍历所有可能取值.
      • $$matrix[i,j] = min{matrix[i,r-1] + p_r + matrix[r+1,j] + w(i,j) \mid r\in(i,j) }$$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class bst(object):
    # p[0]为无效位
    def list_pq(self, size=10):
    tmp = randoms.list_int(size)
    tmq = randoms.list_int(size + 1)
    sums = sum(tmp) + sum(tmq)
    p = [x / sums for x in tmp]
    p.insert(0, 0)
    q = [x / sums for x in tmq]
    return [p, q]

    def w(self, k, i, j, p, q):
    return sum(p[i:j + 1]) + sum(q[i - 1:j + 1]) - q[k]

    def qbst(self, p, q):
    size = len(q) # 0~n n+1个
    matrix = [[0 for i in range(size)] for j in range(size + 1)]

    for i in range(0, size): # 填充第0斜线
    matrix[i + 1][i] = q[i]
    for i in range(1, size): # 填充1~n斜线
    m = 1
    n = i
    while m < size and n < size:
    matrix[m][n] = min([
    matrix[m][k - 1] + matrix[k + 1][n] + self.w(
    k, m, n, p, q) for k in range(m, n + 1)
    ])
    m += 1
    n += 1
    return matrix[1][size - 1]


    if __name__ == "__main__":
    test = bst()
    arr = test.list_pq()
    p = arr[0]
    q = arr[1]
    tmp = test.qbst(p, q)
    print(tmp)
  • 这里仅输出了QBST的搜索期望,还需要一个与 matrix 同等规模的矩阵 root 记录每次选择的结果,根据 root 矩阵输出对应的二叉树.

  • w 函数部分,也可以应用动态规划求解,使用第三个与 matrix 同等规模的矩阵 w,防止重复计算.

树的独立集合

  • 二叉树部分代码还在转置python中.延后.

任意两点最短路径

  • 问题定义

    • 寻找输入的图中任意两点的最短路径.这里讨论的是 Floyd-Warshall 算法,所以对输入的图存在限制.
    • input: 一个邻接矩阵表示的图G(V,E).可以为有向图但不含负向回路的负权图.
    • output: 输出全局最短路径矩阵P.
  • 分析

    • 优化子结构
      • ABC~D是A到D的最短路径,则其所包含的所有子路径必然都是对应首尾结点的最短路径.
      • 证明:
        • 假设BC这条子路径不是最短子路径,必然存在最短子路径BC’,用 BC’ 替换 BC 可以得到 ABC’D 比 ABCD 更优,与前提矛盾.
    • 重叠子问题
      • Floyd 算法定义了一个集合生长的过程,每次在原图中选中一个结点添加到集合 w .开始集合w为空,直到原图中所有结点都包含到了集合w.
      • 这样就将子问题限定在了这个有限的集合w中.
      • 集合w 最终与原图的规模相同,但其中记录的有效数据为对应两点之间的最短路径长度.
      • 这样,在添加一个新的结点时,可以利用现有集合w中最短路径数据,防止重复计算.
  • 其他

    • 定义

      • 令$D^{(k)}[i,j]$ 为 $v_i$ 到 $v_j$ 在集合仅包含 ${v_1,v_2,..,v_k}$ 时的最短路径.
        则 $D^{(0)}$ = $G(V,E)$ ,$D^{(0)}$ = 目标矩阵(包含全局任意两点的最短路径长度)
      • 则 $D^{(k)}[i,j]$ 有两种可能的取值
        • $$D^{(k)}[i,j] = D^{(k-1)}[i,j]$$
        • $$D^{(k)}[i,j] = D^{(k-1)}[i,k] + D^{(k-1)}[k,j]$$
        • 两者取最小.
      • 还需要一个与 $G(V,E)$ 同等规模的矩阵存储每次最短路径选择的结果.
      • 这样程序需要3重循环
        • 1~n-k 集合w由空集生长到包含全部结点.
        • 1n-i and 1n-j 对应 $D^{(k)}[i,j]$ 的选择.
        • ps: 时间复杂度 $N^3$.
    • 最优解递归方程

      • $$D^{(k)}[i,j] = min{D^{(k-1)}[i,j] ,, ,D^{(k-1)}[i,k] + D^{(k-1)}[k,j]}$$
      • 公式意义是当第K轮循环,第K个结点被添加到集合W时,路径从i到j,经过k结点是否更近.
  • 原始版本

    • 为简单表示,这里没有添加记录每次选择的矩阵P.
    • 由上面分析可知需要 N+1 个二维矩阵 空间复杂度 $N^3$.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def floyd_N3(self, G):
    size = len(G[0])
    matrix3 = [[[0 for i in range(size)] for j in rang(size]
    for k in range(size)]
    matrix3[0] = G[:] # 初始矩阵
    for k in range(1, size):
    for i in range(size):
    for j in range(size):
    matrix3[k][i][j] = min(
    matrix3[k - 1][i][j],
    matrix3[k - 1][i][k] + matrix3[k - 1[k[j])
    return matrix3[size - 1]
  • 但由递推方程可得,任何一个 $D^{(k)}$ 仅取决于 $D^{(k-1)}$,所以可以使用两个二维矩阵分别存储第一重循环每次 $D^{(n)}$ 和 $D^{(n-1)}$.这样空间复杂度 $N^2$ .

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def floyd_N2(self, G):
    size = len(G[0])
    matrix1 = [[0 for i in range(size)] for j in rang(size)]
    matrix2 = [[0 for i in range(size)] for j in rang(size)]
    matrix1 = G[:] # 初始矩阵
    for k in range(1, size):
    for i in range(size):
    for j in range(size):
    matrix2[i][j] = min(matrix1[i][j],
    matrix1[i][k] +matrix1[k][j])
    matrix1 = matrix2[:]
    return matrix2
  • 但还可以直接在输入的 G(V,E) 矩阵/或/只使用1个矩阵 直接存储结果.空间复杂度同样为 $N^2$ .

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def floyd_N22(self, G):
    size = len(G[0])
    matrix = G[:] # 初始矩阵
    for k in range(1, size):
    for i in range(size):
    for j in range(size):
    if matrix[i][j] > matrix[i][k] + matrix[k]
    [j]:
    matrix[i][j] = matrix[i][k] + matrix
    [k][j]
    return matrix
  • 验证,输出结果相同.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    tmp = randoms.matrix()
    # print(tmp)
    test = floyd()
    tm = test.floyd_N3(tmp)
    tn = test.floyd_N2(tmp)
    ts = test.floyd_N22(tmp)
    print(tm)
    print(tn)
    print(ts)