常用算法思想

2020-02-27  本文已影响0人  simplehych

任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关。

以上五种可以理解为一种思想，而不是算法。

  1. 分治法 Divide and Conquer
  2. 动态规划法 Dynamic Programing
  3. 贪心法 Greedy
  4. 回溯法 Back Tracking
  5. 分支限界法 Branch and Bound

先抛出一个对比表格，可以当总结，也可以有一个感性认识。

思想 关键点 示例问题
分治法 将问题划分为一个个子问题

1. 规模缩小到一定程度可以容易解决
2. 具有最优子结构
3. 子问题可以合并得到原问题的解
4.子问题之间是相互独立的		 Fibonacci数列
阶乘
Hanoi塔
二分法搜索
排序算法（快速排序、合并排序）
傅立叶变换（快速傅立叶变换）
棋盘覆盖
最接近点对问题
循环赛日程表
动态规划法 将问题划分为一个个子问题

1. 满足最优化原理
2. 无后效性
3. 子问题之间是不独立的（有重叠能记录复用）		 最优二叉查找树
最长公共子序列
近似串匹配问题
最大连续子序列和（最大m子段和）
贪心法 将问题划分为一个个子问题

1. 局部最优策略能导致全局最优解（适用情况少）
2. 不一定最优		 哈夫曼编码
单源最短路径（Dijkstra算法）
最小生成树（Prim和Kruskal算法）
背包问题
最近邻点问题 最短连接问题
图着色
多极度调度
回溯法 1. 全部解
2. 深度优先遍历		 八皇后问题
哈密顿回路问题
批处理作业调度
分支限界法 1. 某一个解
2. 广度优先遍历		 任务分配问题
多段图的最短路径
批处理作业调度问题
电路布线问题

分治法 Divide and Conquer

适用情况：

  1. 该问题的规模缩小到一定的程序就可以容易解决。
  2. 该问题可以分解成若干个 规模较小的相同问题，即该问题具有最优子结构的性质。
  3. 该问题分解出的子问题的解可以合并为该问题的解。
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

适用情况说明：

  1. 第一条特征，绝大多问题都可以满足，因为问题的计算复杂性一般是追着问题规模的增加而增加。
  2. 第二条特征，是应用分治法的前提，也是大多数问题可以满足的，此特征反应了递归思想的应用。
  3. 第三条特征，是关键，能否使用分治法完全取决于问题是否满足该特征，如果具备第一和第二特征，而不具备第三特征，则可以考虑用 贪心法和动态规划法。
  4. 第四条特征，涉及分治法的效率，如果各个子问题是不独立的，那么分治法要做许多不必要的工作，重复地解决公共子问题，此时虽然可用分治法，但一般用动态规划法较好，可以保存公共问题的解。

基本步骤：

分治法在每一层递归上都有三个步骤：

  1. 分解 Divider，将原问题分解成若干个规模较小，相互独立，与原问题形式相同 的子问题。
  2. 解决 Conquer，若子问题规模较小且容易被解决，则直接解，否则递归地解各个子问题。
  3. 合并 Combine，将子问题的解合并为原问题的解。

设计模式：

Divide-and-Conquer(P)
if |P| <= n0
    then return( ADHOC(P) )
将P分解为较小的子问题 P1, P2,…,Pk
for  i - 1 to k
    do  yi - Divide-and-Conquer(Pi) 递归解决Pi
T - MERGE(y1, y2,…,yk) 合并子问题
return（T)

其中，|P| 表示问题P的规模；n0表示阈值，当问题P规模不超过n0时，问题容易解出，不必再继续分解；ADHOC(P) 表示分治法中的基本子算法，用于直接解小规模的问题P；MERGE (y1, y2,…,yk) 表示分治法中合并子算法。

复杂性分析：

// todo

思维过程：
类似于数学归纳法，找到解决问题的求解方程，根据方程公式设计递归程序。

  1. 先找到最小问题规模时的求解法。
  2. 考虑随着问题规模增大时的求解法
  3. 找到求解的递归函数式后，设计递归程序即可。

动态规划 dynamic programming

基本概念

过程：每次决策依赖于当前（阶段）状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生的，所以这种多阶段最优化决策解决问题的过程就成为动态规划。

基本思想和策略：

与分治法类似，也是将求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

特点：解决重叠子问题，为了减少重复计算，对每一个问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

与分治法的区别：适合于动态规划法求解的问题，经分解后得到的子问题往往不是相互独立的。（即重叠子问题，下一阶段的求解是建立在上一阶段的解的基础上，可利用保存的解）

适用情况：

  1. 最优化原理：该问题的最优解所包含的子问题的解也是最优的，即具有最优子结构
  2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响，只与当前状态有关。
  3. 有重叠子问题：一个子问题在下一阶段决策中可能被多次使用到。子问题的空间要很小，递归算法可反复地解同样的子问题，而不是产生新的子问题。相同且独立。（该性质不是动态规划适用的必要条件，但如果问题没有该性质，那动态规划算法痛其他算法相比就不具备优势）

通常应用于最优问题，即要做出一组选择以达到最优解。

举例：无权最短路径，无权最长简单路径。前者有最优子结构，而后者没有，故不能用动态规划求解。

求解的基本步骤：

动态规划所处理是一个多阶段决策问题，一般由初始状态开始，通过中间阶段决策选择，达到结束状态。
这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线。（通常是最优的活动路线）

初始状态 -> 决策1 -> 决策1 -> … -> 决策n -> 结束状态

动态规划的设计有着一定的模式，要经历以下几个步骤：

  1. 划分阶段：按照问题的时间和空间特征，把问题分成若干个阶段。注意阶段一定要是有序的或者是可排序的，否则问题就无法求解。
  2. 确定状态和状态变量：将问题发展到各个阶段时 所处于的各种客观情况用不同的状态表示出来。当然状态的选择要满足无后效性。
  3. 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程即可写出。但事实上常常反过来做，根据相邻两个阶段的状态之间的关系来确定 决策方法和状态转移方程。
  4. 寻找边界条件：给出状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

实际应用中，可以按以下简化的步骤进行设计：

  1. 分析最优解的性质，并刻画其结构特征。
  2. 递归的定义最优解。
  3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
  4. 根据计算最优值时得到的信息，构造问题的最优解。

贪心算法 greedy

基本概念

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。

必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具有无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

基本思路

  1. 建立数学模型来描述问题。
  2. 把求解的问题分成若干个子问题。
  3. 对每一个子问题进行求解，得到子问题的局部最优解。
  4. 把子问题的局部最优解合成原来问题的一个解。

适用的问题

前提：局部最优策略能产生全局最优解。
实际上，贪心算法的适用情况较少。判断是否适用于贪心算法可以举几个实际数据进行分析。

实现框架

从问题的某一个初始解出发；
while(能朝给定目标前进一步){
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个解；

贪心策略的选择

因为贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

例题分析

  1. 背包问题：有一个背包，容量是 M=150。有7个物品，可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

    物品 A B C D E F G
    重量 35 30 60 50 40 10 25
    价值 10 40 30 50 35 40 30

    贪心策略：

    1. 每次挑选 价值最大 的物品
    2. 每次挑选 重量最小 的物品
    3. 每次挑选 单位重量价值最大 的物品

    以上三种策略都不符合，可能针对本题 3 合适，但不具有统一性，更换了物品个数、背包容量等参数就不满足了。

  1. 钱币问题

    比如有钱币1元、3元、4元，要拿6元。贪心算法的解：先拿 4元，再拿 1 元，再拿 1元。一共三张钱，但实际最优两张3元就够了。

回溯法 backtracking

概念

回溯算法，实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一个选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，满足回溯条件的某个状态的点称为“回溯点”

许多复杂的，规模较大的问题都使用回溯法，有“通用解题方法”的美称。

基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度探索解空间树。当搜索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果不包含，则逐层向其祖先结点回溯。

其实回溯法就是对隐式图的深度优先搜索算法。

求所有解：要回溯到根，且根结点的所有可行的子树都要被搜索遍才能结束。
求任一解：只要搜索到问题的一个解就可以结束。

解题步骤

  1. 针对所给的问题，确定问题的解空间。明确定义问题的解空间，问题的解空间应该至少包含问题的一个（最优）解。
  2. 确定结点的扩展搜索规则
  3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

算法框架

问题框架：
设问题的解是一个 n 维向量(a1, a2, … ,an)，约束条件是 ai (i=1, 2, ... , n) 之间满足某种条件，记为f(ai)。

非递归回溯框架

`int a[n](),i; 初始化数组a[]();
 i = 1;
 while (i\>0(有路可走)   and  (未达到目标))  // 还未回溯到头
 {
     if(i \> n)  {   // 搜索到叶结点
           搜索到一个解，输出；
     } else {          // 处理第i个元素
          a[i]()第一个可能的值；
          while(a[i]()在不满足约束条件且在搜索空间内) {
              a[i]()下一个可能的值；
          }
           if(a[i]()在搜索空间内)  {
              标识占用的资源；
              i = i+1;                              // 扩展下一个结点
          } else {
              清理所占的状态空间；            // 回溯
               i = i –1; 
          }
}

递归回溯框架

try(int i) {
    if ( i \> n){
        输出结果
    } else {
        for( j=下界; j\<= 上界; j++) {
            if (fun(j)){
                a[i][7] = j;
                try( i + 1);
                回溯前的清理工作（如a[i][8]置空等）；
            }
        }
    }
}

分支限界法 Branch and Bound

基本描述

类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。

但是一般情况下，分支限界法与回溯法求解目标不同。

  1. 回溯法的求解目标是：找出T中满足约束条件的所有解。
    1. 分支限界法的求解目标是：找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

分支搜索算法

所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有的相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表，然后从表中选择一个结点作为下一个E-结点，继续搜索。
选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式：

  1. FIFO搜索
  2. LIFO搜索
  3. 优先队列式搜索

分支限界搜索算法

一般过程

由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。

分支限界法的搜索策略是：
问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。
在搜索问题的解空间树时，分支限定法与回溯法对当前扩展结点所使用的拓展方式不同。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
在扩展结点处，一次性生成其所有的儿子结点(分支)，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点会被舍弃，其余儿子结点被加入活结点表中。
然后再从当前的的活结点中选择下一个扩展结点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一伙结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快找出一个最优解。

算法差异

分治法、动态规划法、贪心算法三者的相似之处： 都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。

分治法和动态规划的区别

共同点：

  1. 都要求原问题具有 最优子结构性质。
  2. 都将原问题分成若干个子问题
  3. 然后都将子问题的解合并，形成原问题的解。

不同点：

  1. 分治法是分解成若干个互不相交的子问题；动态规划是将问题分解成若干个相互重叠的子问题；
  2. 分治法求解子问题重叠部分会被重复计算多次；动态规划每个子问题只求解一次并将其保存在一个表中，遇到重叠部分查表得到解，避免重复计算。

动态规划和贪心法的区别

共同点：

  1. 都是递推算法。
  2. 都是对子问题树进行修剪。
  3. 都要求原问题具有 最优子结构性质。

不同点：

  1. 动态规划通常以自底向上的方式解各子问题，采用递归的方式；贪心法通常以自顶向下的方式，用迭代的方式做出相继的贪心选择，每做一次贪心选择就将问题简化为规模更小的问题。
  2. 动态规划用到之前的最优解，贪心算法则不用。贪心无法解决动态规划的问题，但动态规划能解决贪心的问题。
  3. 贪心算法解决的问题一定能用动态规划法，但贪心算法效率高于动态规划。

贪心算法是通过一系列选择来给出某一问题的最优解。每一个决策点，做出当时看起来是最佳的选择。当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。因此，贪心算法通常是自顶向下地做出贪心选择，不断地将给定的问题实例规约为更小的问题。贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。
而动态规划中，每一步要做出选择，但这些选择依赖于子问题的解。因此解动态规划问题一般是自底向上，从小问题处理至大问题。

回溯法和分支限界的区别

共同点：

  1. 一种在问题的解空间树上搜索问题解的算法

不同点：

  1. 求解目标不同。回溯法：找出满足约束条件的所有解；分支限界法：尽快找出满足约束条件的一个解。
  2. 搜索方法不同。回溯法：深度优先方法搜索解空间；分支限界法：广度优先或以最小消耗优先的方式搜索解空间。
  3. 对扩展结点的扩展方式不同。回溯法：如果当前扩展结点不能再纵深方向移动，则当前扩展结点成为死结点，此时回溯到最近的一个活结点使其成为扩展结点；分支限界法：每一次活结点只有一次机会成为扩展结点，一旦成为扩展结点，就一次性产生其所有儿子结点。
  4. 存储空间的要求不同：回溯法：小；分支限界法：大；但内存有限时，回溯法成功可能性更大。

参考资料

感谢以下文章作者

五类常见算法小记 （递归与分治，动态规划，贪心，回溯，分支界限法）
Leetcode常用五大算法思想
分治法，动态规划法，贪心法，回溯法，分支限界法的区别和联系以及适用情况
分支限界法和回溯法的区别

上一篇下一篇

猜你喜欢

热点阅读