文章字数：918,阅读全文大约需要3分钟
五个常用的算法思想
贪婪算法
- 特性
- 局部最优解，总是找出当前看来最好的选择，而不是从整体考虑
- 局部最优解通常不是全局最优
- 想要通过贪婪算法找到最优解，通常需要严谨的数学证明
- 计算过程
- 将问题拆解成若干个子问题
- 选择子问题的最优解
- 将子问题的解合并成问题的解
- 例子
- 背包问题： 有若干个重量、价值不同的物体，在背包承重固定的情况下找出能拿走加个最高的组合。
- 策略1: 找最贵的拿，直到再拿就超重
- 策略2: 拿最重的
- 策略3: 拿最轻的
- 策略4: 拿性价比最高的
最后可以比较所有策略的结果，去出最优的
结果只是接近最优，但是性能大幅提升
动态规划算法
- 动态规划法能解决具有以下特点的问题
- 最优子结构: 可以把局部问题结合起来得出全局最优解
- 重复子问题: 计算最优解的过程中会处理很多相同的问题
- 原理
- 一个问题是另一个问题状态转移后的到的，所以计算每一步的状态转移过程即可的到最终答案
- 例子
- 斐波那契数列的计算
- 斐波那契数列第二项之后的元素都是前两个元素之和
- 如果每次都从头计算，会有很多重复的运算
- 直接将每次的结果都保存下来，接下来计算每项都直接从结果集中取前两项的值
分治算法
- 将大问题分成若干小问题，再把小问题划分下去。直到
base cases，解决之后一步步向上，最终解决大问题 - 例子: 快速排序
回溯算法
- 回溯算法和暴力破解很像，但是优点在于排除了很多不可能的步骤
- 原理
- 遍历元素时如果得出此方法不通，则直接返回。
- 例子: N皇后问题
- 加入有N*N的棋盘，要在上面放上N个皇后，并保证N个都无法吃掉对方
- 即不在一行，不在一列，不在对角线上
- 每一个棋子都是一个循环
- 当最后一个棋子确定此路不同时，结束循环
- 父循环进入下一次循环
- 其它例子: 深度优先遍历
分支限界算法
- 和回溯法类似，但是分支限界算法是从广度上进行排除不可能的步骤的
- 回溯法是找到一个解就深入下去，直到判断无解，然后放弃一整条路径，进入下一个
- 分支限界算法是先把所有的最外层问题解出来，然后再去除不可能的。
- 然后再从可能的中进入下一次子问题