算法设计与分析

简答

• 以比较为基础的检索算法的时间下界是O(logn);Ω还是O?
  以比较为基础的分类算法的时间下界是Ω(nlogn);
  简要说明理由：理由

• 算法的五大特性：确定性，能行性，输入，输出，有穷性。
  而计算过程只满足前4条特性，不满足有穷性

• 最优性原理：
  无论过程的初始状态或者初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
  最优性原理成立的例子：流水线调度问题，货郎担问题；
  最优性原理不成立的例子：多段图问题（以乘法作为路径长度且出现负权边时 或 包含负长度环的任意两点间最短路径问题；

• 贪心方法不一定能得到01背包问题的最优解。举例

• c^(x)<=c(x)

• 问题状态：树中每一个节点确定所求解问题的一个问题状态；
  状态空间：由根节点到其他节点的所有路径确定了这个问题的状态空间；
  解状态：解状态是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组；
  答案状态：答案状态是这样一些解状态S，对于这些解状态，由根到S的那条路径确定了这问题的一个解。
  解空间的树结构即为状态空间树；
  4皇后问题的问题状态一共有65个

• 分治法的三个基本步骤：
  分：将n个输入分成k个不同的可独立求解的子问题；
  治：求出这些问题的解；
  合：通过适当的方法将每个问题的解合并成整个问题的解。

• Q.回溯法和分支限界法的状态空间生成方式有何不同？简述两种方法的基本思想

  1. 回溯法：当前结点的E-结点R一旦生成一个新的儿子结点C,这个C结点就变成新的E-结点，生成下一个儿子结点
  2. 分支-限界法：一个E-结点一直保持到变成死节点为止
  3. 回溯法：加限界的深度优先生成方法称为回溯法。回溯法在包含问题的所有解的解空间树中，按深度优先的策略，从根节点出发搜索解空间树。搜索至解空间树的任一结点时，先判断改结点是否肯定不包含问题的解。如果肯定不包含，就跳过以该结点为根的子树，逐层向其祖先结点回溯。否则就进入该子树，继续按深度优先的策略进行搜索
  4. 分支-限界法：生成当前E-结点的全部儿子后，再生成其他活结点的儿子；使用限界函数帮助避免生成不包含答案结点子树的状态空间。

• P类问题：所有已经找到多项式算法的问题的集合
  NP类问题：所有可在多项式时间内由不确定算法验证的判定问题的集合
  可满足性问题：对于变量的任一一组真值指派确定公式是否为真
  COOK定理：可满足性在P内，当且仅当P=NP
  NP难度：如果可满足性约化为一个问题L，则称此问题是NP难的
  NP完全：如果L是NP难的而且L属于NP，则称问题L是NP完全的

• 最优二分检索树Knuth的优化方法:将k限制在区间R(i,j-1)~R(i+1,j)

证明题

• 证明以比较为基础的分类算法的最坏情况的时间下界为Ω(nlogn)

  • 假设参加分类的n个关键字A(1),A(2),...,A(n),各不相同，因此任意两个关键字A(i)和A(j)的比较必然导致A(i)<A(j) or A(i)>A(j)的结果。在比较树中，一个进入左分支，另一个进入右分支。各外部结点表示算法终止。由于n个关键字共有n!个排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必有至少n!个外节点。
    由根到外节点的路径长度即为生成该分类序列的比较长度。最坏情况的比较次数即为根到外节点的最长路径。设T(n)是为这些算法对应的比较树的最小高度。设一棵二元树的所有内节点的级数均<=k,
    n!<=2^T(n)
    当n>1时有 n!>=n(n-1)(n-2)...(n/2)>=(n/2)^n/2
    对于n>=4有 T(n)>=(n/2)log(n/2)>=(n/4)logn
    因此以比较为基础的分类算法的最坏情况的时间下界为Ω(nlogn)

• 证明FIND(n)>=[log(n+1)]

  • 在比较树中可知，FIND(n)不大于树中根到一个叶子的最长路径的距离。在这所有的树中都必定有n个内节点与x在A中可能得n种出现情况相对应。
    如果一棵二元树的所有内节点所在的级数小于或等于级数k，则最多有2^k-1个内节点。因此 n<=2^k-1，即FIND(n)=k>=[log(n+1)]

• 定理5.3:设J是k个作业的集合，σ=i₁i₂i₃...i_k是J中作业的一种排列，它使得d_i1<=d_i2<=d_i3<=...<=d_ik.J是一种可行解，当且仅当J中的作业可以按照σ的次序而又不违反任何一个期限的情况来处理。

  • 笔记图片

计算题