动态规划(二)

发表于 2019-02-17 分类于算法阅读次数： Disqus：本文字数： 5.4k 阅读时长 ≈ 5 分钟

算法动态规划(二),图论部分,包括 python 源代码
更新
1
19.02.13 初始

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

导语

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

动态规划

概述

动态规划简述是把原问题分解为相对简单的子问题,再依次求解最终解决原问题的方法。
许多子问题非常相似,动态规划中某个给定子问题的解已经得出，则存储，以便下次需要同一个子问题解之时直接查表。所以动态规划在输入的规模呈指数增长时特别有用。
一个问题是否适用于动态规划求解,取决于重叠子问题最优子结构和无后效性
- 最优子结构性质: 问题的最优解所包含的子问题的解也是最优的，可以通过求解子问题的最优解,来求解原问题.
- 重叠子问题: 在自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划通过保存已求解的子问题答案,避免冗余计算.
- 无后效性: 子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
动态规划基本求解步骤
- 分析优化解结构
- 递归定义最优解代价
- 自底向上计算最优解代价并保存子问题最优解
- 根据最优解信息,构造优化解

randoms类

提供原始数据,随机生成int , str 等.
计算函数运行时间.

代码

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):
  - 结点
    - $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) }$$

代码

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的最短路径,则其所包含的所有子路径必然都是对应首尾结点的最短路径.
  - 证明:
    - 假设B~~C这条子路径不是最短子路径,必然存在最短子路径B~~C’,用 B~~C’ 替换 B~~C 可以得到 ABC’~~D 比 A~~BCD 更优,与前提矛盾.
- 重叠子问题
  - 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由空集生长到包含全部结点.
    - 1~~n-i and 1~~n-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$.

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

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

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

验证,输出结果相同.

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)