算法基础概念

• 递归
  • 直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。
  • 每个递归函数都要有非递归定义的初始值，如阶乘函数，斐波那契，汉诺塔。
• 分治策略
  • 基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
  • 例如：二分查找、大整数乘法、strassen矩阵乘法、归并排序、快速排序、棋盘覆盖
• 动态规划（自底向上）
  • 和分治法类似，都是将待求问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
  • 动态规划从最小的问题开始，逐层向上求解，通过子问题之间的依赖关系，有效利用前面已经得到的结果，最大限度减少重复工作，以提高算法效率。
  • 要素
    • 最优子结构性质（优化原则）
      • 当问题的最优解包含了其子问题的最优解时，则称该问题具有最优子结构性质。这个性质是动态规划算法求解的重要线索。
    • 子问题重叠性质
      • 在运用递归算法自顶向下解题时，每次产生的子问题并不总是新问题，动态规划将计算过的子问题保存在一个表格中，当再次使用时直接搜索到它拿过来用就行了。
  • 例如：大矩阵乘法、最长公共子序列、流水作业调度、0-1背包
• 贪心法
  • 贪心算法并不从整体的最优解考虑，而是做出当前的局部最优的选择。
  • 要素
    • 最优子结构（组合优化）
    • 贪心选择性质
      • 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。
  • 例如：活动安排问题、哈夫曼编码($O(nlogn)$)
• 动态规划算法与贪心算法的异同:
  • 共同点：
    • 都需要最优子结构性质。
    • 都用来求有优化问题。
    • 不同点：
      • 动态规划：
        • 每一步作一个选择——依赖于子问题的解。
      • 贪心方法：
        • 每一步作一个选择——不依赖于子问题的解。
        • 动态规划方法的条件：最优子结构性质；子问题的重叠性质。
        • 可用贪心方法的条件：最优子结构性质；贪心选择性质。
  • 动态规划：自底向上求解（动态规划方法是自底向上计算各个子问 题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构）
  • 贪心法：自顶向下求解。
  • 可用贪心法时，动态规划方法可能不适用；
  • 可用动态规划方法时，贪心法可能不适用。
• 回溯法
  • 为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。
  • 具有限界函数的深度优先生成法称为回溯法。
  • 两种解空间树：
    • 子集树
      • 当我们求解的结果是集合的某一子集的时候，其对应的解空间是子集树。
      • 例如：八皇后问题、0-1背包问题
    • 排列树
      • 当我们求解的结果是集合元素的某一种排列的时候，其对应的解空间就是排列树。
      • 例如：货郎问题（$O(n!)$）
• 分支限界法（回溯法的改进）
  • 队列式(FIFO)分支限界法—将活结点表组织成一个队列，按照先进先出(FIFO)原则选取下一个结点为扩展结点;
  • 优先队列式分支限界法—将活结点表组织 成一个优先队列，按照规定的优先级选取优先级最高的结点成为当前扩展结点。