算法-动态规划(二)

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

• 参考资料

  https://www.zybuluo.com/codeep/note/163962

  https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000

  https://mooc.study.163.com/course/1000005000

• 更新

  19.02.13 初始
  

导语

• 还是没有整理完二叉树部分,用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$

    • 搜索期望

  • 构建最优二叉搜索树(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]$ 的差值.
    • 则 $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$ 具体取值,只能遍历所有可能取值.

• 代码

  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中.延后.