五大经典算法思想及对生活的小启发

[xingbofeng]

近期在工作之余大部分时间投入到设计模式、算法、操作系统原理的学习中，这里算是一些小小的体会吧。

第一点小小的体会是自己在看Linux的过程中发现自己对底层原理还是有那么一些兴趣的(为啥以前就没发现呢，所以还是继续茫茫前端的搬砖路吧，哈哈~😆)

枚举法

与其说有五大经典算法思想其实还有一点更为原始的思想就是枚举法，或者说叫暴力(🤓)枚举法？

穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。穷举法也称为枚举法。

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

• 基本思想
  • 不从总体最优考虑，仅考虑局部最优解，问题必须具备后无效性
• 过程
  • 建立数学模型来描述问题；
  • 把求解的问题分成若干个子问题；
  • 对每一子问题求解，得到子问题的局部最优解；
  • 把子问题的解局部最优解合成原来解问题的一个解。
• 适用情况
  • 局部最优策略能导致全局最优解
  • 子问题后无效性
• 常见实例
  • 0-1背包问题
  • 均分纸牌
  • 马踏棋盘

对生活的一点小启示：贪心算法不适用于生活，作为一般人的你永远无法找到每个阶段的整体最优解。

动态规划

贪心算法（又称贪婪算法）是指，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

• 基本思想
  • 将问题分解为多个子问题（阶段），按顺序求解，前一个问题的解为后一个问题提供信息
• 适用情况
  • 最优化原理：问题的最优解所包含的子问题的解也是最优的，即最优子结构
  • 无后效性：某个状态一旦确定，就不受以后决策的影响
  • 有重叠子问题
• 常见实例
  • 菲波那切数列
  • 多重背包问题
• 说明
  • 递推关系是从次小的问题开始到较大问题的转化，往往可以用递归来实现，可以利用之前产生的子问题的解来减少重复的计算

对生活的一点小启示：把若干问题分解成小问题进行解决，会获得更大的成就感。

回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

• 基本思想
  • 选优搜索法，走不通就退回重选，按照深度优先搜索的策略，从根节点出发，深度搜索解空间
• 过程
  • 确定解空间
  • 确定节点的扩展搜索规则
  • 深度优先方式搜索解空间，用剪枝法避免无效搜索
• 常见实例
  • 树的深度优先遍历(先中后序遍历)
  • 八皇后问题

对生活的一点小启示：不要畏惧失败，记下失败的原因，回到起点重新开始，最终总会成功。

分支限界算法

分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。 该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。

• 基本思想
  • 与回溯法类似，也是在解空间里搜索解得算法，不同点是，回溯法寻找所有解，分支界限法搜索一个解或者最优解
• 过程
  • 如果问题的目标为最小化，则设定目前最优解的值Z=∞
  • 根据分枝法则（Branching rule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。
  • 计算每一个新分枝出来的节点的下限值（Lower bound，LB）
  • 对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑：
• 常见实例
  • 广度优先策略
  • 最小耗费（最大效益）优先

分治法

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础。

• 基本思想
  • 将一个问题，分解为多个子问题，递归的去解决子问题，最终合并为问题的解
• 适用情况
  • 问题分解为小问题后容易解决
  • 问题可以分解为小问题，即最优子结构
  • 分解后的小问题解可以合并为原问题的解
  • 小问题之间互相独立
• 常见实例
  • 二分查找
  • 快速排序
  • 合并排序
  • 大整数乘法
  • 循环赛日程表

对生活的一点小启示：有些问题由多个问题组成，问题间又相互独立，不妨把它们分成小问题试试。说不定这样会更快呢？