算法

前言

• 算法作为一门学问有两条几乎平行的线索。同一个数据对象上有不同的问题，就可用到不同的算法策略。不同数据对象上的问题也能用到相同的算法策略。
  • 数据结构（数据对象）：数、矩阵、集合、串、排列、图、表达式、分布等。
  • 算法策略：贪心、分治、动态规划、搜索等。
• 时间复杂度排序
  O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) <O(2ⁿ) < O(!n) < O(nⁿ)

1. 贪心算法

一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。

• 需要注意以下问题：
  1. 没有后悔药。
  2. 得到的可能是最优解的近似解。
  3. 贪心策略直接决定算法的好坏。
• 满足以下两种情况时可以使用贪心算法
  1. 贪心选择：指原问题的整体最优解可以通过一些列局部最优的选择得到。
  2. 最优子结构：当一个问题的最优解包含其子问题的最优解时，称具有最优子结构性质。
• 使用步骤
  • 选取贪心策略
  • 局部最优解：根据贪心策略，一步一步得到局部最优解。
• 相关算法：冒泡排序（贪心策略是每次从剩下序列中选一个最大的）、Dijkstra算法（图的最短路径问题）

2. 分治法

• 使用条件
  • 原问题可分解为若干个规模较小的相同子问题。
  • 子问题相互独立。
  • 子问题的解可以合并为原问题的解。
• 解法步骤：
  • 分解：将要解决的问题分解成若干个规模较小、相互独立、与原问题形式相同的子问题。
  • 治理：求解各个子问题。
  • 合并：将子问题的解追层合并构成原问题的解。
• 递归是体现分治法优势的利器。
• 相关算法：二分搜索、快速排序、归并排序等。

3. 动态规划

• 动态规划也是一种分治思想，但分治算法与不同的是：
  • 分治算法是把原问题分解成若干个子问题，自顶向下求解个子问题，合并子问题的解，从而得到原问题的解。
  • 动态规划也是把原问题分解成若干个子问题，然后自底向上，先求最小的子问题，把结果存储在表格中，再求大问题时，直接从表格中查询小问题的解，避免重复计算，从而提高效率。
• 使用条件
  • 最优子结构：问题的最优解包含其子问题的最优解。
  • 子问题重复（非必要）：求解子问题中，有大量子问题是重复的。求一次后放进表格，后面使用直接查询。
• 解法步骤：
  • 分析最优解的结构特征
  • 建立最优值递归式
  • 自底向上计算最优值，并记录。
  • 构造最优解。
• 相关算法：最长公共子序列、0-1背包问题等。

4. 回溯法

是一种选优搜索法，按照选优条件深度优先搜索，以达到目标。

• 回溯法是一种“能进则进，进不了则换，换不了则退”的搜索方法。
• 算法要素：
  • 解空间：由所有可能解组成的空间。解空间越小，搜索效率越高。
  • 解空间树：对解空间按照树的组织结构搜索最优解，是解空间的形象表示，提高搜索效率。
  • 隐约束，也称剪枝函数，指对能否得到问题的最优解或可行解作出的约束，包括约束函数和限界函数。
• 解空间的大小和剪枝函数（隐约束）的好坏都直接影响搜索效率。
• 解法步骤：
  • 定义解空间：解的组织形式一般都规范为一个n元组；显约束，是对解分量的取值范围的限定，可以控制解空间大小。
  • 确定解的组织结构，通常用解空间树形象的表达。有子集树、排列树、m叉树等。
  • 搜索解空间：按深度优先搜索策略，根据隐约束（约束函数和限界函数），在解空间搜索可行解或最优解，当不满足就回溯尝试其他路径。
    • 若只要求可行解，则只需要约束函数；如果要求最优解，则要约束函数和限界函数。
• 显约束控制解空间大小，约束函数决定剪枝效率，限界函数决定是否得到最优解。
• 回溯法的关键是设计有效的显约束和隐约束。
• 相关算法：0-1背包、地图上色、n皇后问题等。

• 0-1背包举例，每个物品有重量和价格，求购物车能装的最大价值。
  • 解空间{x1,x2,...,xn},显约束为x_i=0或x_i=1,表示装不装入购物车。解空间有2ⁿ中可能解。
  • 解空间树为子集树，树的深度为n。
  • 约束条件为装入购物车总重量小于购物车承重。
  • 限界条件，已装价值加上剩余全部物品价值能否大于当前记录的最大价值。