常见算法思想
简介
几种常见的算法思想, 用来指导我们设计具体的算法和编码, 有
贪心算法, 分治算法, 回溯算法, 动态规划
贪心算法(greedy algorithm)
经典应用, 霍夫曼编码, Prim和Kruskal最小生成树算法, Dijkstra单源最短路径算法
经典问题, 背包问题, 固定容量下, 让背包里装的物品总价值最大, 贪心算法用法则是计算物品单价, 单价从高到低依次放入包中
使用贪心算法解决问题的步骤
- 第一步, 看到这类问题, 首先联想到贪心算法
- 尝试看下这个问题是否能用贪心算法解决
- 举例看下贪心算法产生的结果是否是最优解
大部分能用贪心算法的问题, 结果都是正确的, 但也有解决不掉的问题, 比如前面的选择会影响后面的选择, 局部最优未必全局最优
类似能用贪心算法解决的问题, 分糖果, 钱币找零, 区间覆盖等
贪心算法最难的是如何将要解决的问题抽象成贪心算法模型, 后续的编码一般都很简单
贪心算法解决问题的正确性虽然很多时候都很高, 但要严谨的证明算法能得到最优解, 并不容易
分治算法
分治算法核心思想就是四个字, 分而治之, 将原问题划分为n个规模较小, 并且结构与原问题相似的子问题, 递归的解决这些子问题, 然后再合并其结果, 就得到原问题的解
有点类似递归, 分治算法是一种处理问题的思想, 递归是一种编程技巧, 分治算法一般都比较适合用递归来实现
分治算法能解决的问题, 一般需要满足下面几个条件
- 原问题与分解成的小问题具有相同的模式
- 原问题分解成的子问题可以独立求解, 子问题之前没有相关性(和动态规划的明显区别)
- 具有分解终止条件, 当问题足够小时, 可以直接求解
- 可以将子问题合并成原问题, 且合并操作复杂度不太高, 否则起不到减小算法总体复杂度的效果
分治算法两种典型的应用场景 - 用来指导编码, 降低问题求解的时间复杂度
- 解决海量数据处理问题, 比如MapReduce
回溯算法
之前的深度优先搜索算法利用的就是回溯思想, 这个算法思想简单却应用广泛
比如正则表达式, 编译原理中的语法分析, 很多经典数学问题比如数独, 八皇后, 0-1背包, 图的着色, 旅行商问题, 全排列等等
回溯的处理思想有点类似枚举搜索, 枚举出所有的解, 然后找到满足期望的解, 为了枚举所有可能的解, 避免遗漏和重复, 我们把问题求解的过程分为多个阶段
每个阶段面对一个岔路口, 先随意选一条路走, 当发现这条路走不通, 就退回上一个岔路口, 选另一种走法继续走
示例: 八皇后问题(todo), 0-1背包(todo)
大部分情况下, 回溯算法都可以用来解决广义的搜索问题, 即从一组可能的解中, 选择一个满足要求的解
回溯算法非常适合用递归来实现, 在实现的过程中, 剪枝操作是提高回溯效率的一种技巧
动态规划
单开一篇文章
|