这五个算法是有很多应用场景的,最优化问题大多可以利用这些算法解决。算法的本质就是解决问题。当数据量比较小时,其实根本就不需要什么算法,写一些for循环完全就可以很快速的搞定了,但是当数据量比较大,场景比较复杂的时候,编写for循环就是一个很不明智的方式了。一是耗时,二是写出的代码绝对是天书。当然还有第三点,这点也是最重要的,写代码是一种艺术,而不是搬砖。
0) 穷举法
穷举法简单粗暴,没有什么问题是搞不定的,只要你肯花时间。同时对于小数据量,穷举法就是最优秀的算法。就像太祖长拳,简单,人人都能会,能解决问题,但是与真正的高手过招,就颓了。
1) 贪婪算法
在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 常见的贪心算法有:Prim算法、Kruskal算法(都是求最小生成树的)贪婪算法不一定能获取到全局最优解,同时获取最优解的好坏要看贪婪策略的选择。特点就是简单,能获取到局部最优解。就像打狗棍法,同一套棍法,洪七公和鲁有脚的水平就差太多了,因此同样是贪婪算法,不同的贪婪策略会导致得到差异非常大的结果。
基本思路:将问题分解为若干个小问题,逐渐求得各个子问题的局部最优解,最后合并为原来问题的解
2) 动态规划算法
每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。当最优化问题具有重复子问题和最优子结构。动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果,避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时,动态规划的效果也会很差。如果问题存在大量的重复子问题的话,那么动态规划对于效率的提高是非常恐怖的。就像斗转星移武功,对手强它也会比较强,对手若,他也会比较弱。
3)分治算法
分治算法的逻辑更简单了,就是一个词,分而治之。分治算法就是把一个大的问题分为若干个子问题,然后在子问题继续向下分,一直到base cases,通过base cases的解决,一步步向上,最终解决最初的大问题。分治算法是递归的典型应用。核心就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
4) 回溯算法
回溯算法是深度优先策略的典型应用,回溯算法(选优搜索法)实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径,一直这样递归下去,直到遍历完所有的路径。八皇后问题是回溯算法的一个经典问题,还有一个经典的应用场景就是迷宫问题。
5) 分支限界算法
分支限界法是广度优先的一个经典的例子。回溯法一般来说是遍历整个解空间,获取问题的所有解,而分支限界法则是获取满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。
补充:
分治法
- 基本思想
- 将一个问题,分解为多个子问题,递归的去解决子问题,最终合并为问题的解
- 适用情况
- 问题分解为小问题后容易解决
- 问题可以分解为小问题,即最优子结构
- 分解后的小问题解可以合并为原问题的解
- 小问题之间互相独立
- 实例
- 二分查找
- 快速排序
- 合并排序
- 大整数乘法
- 循环赛日程表
动态划分算法
- 基本思想
- 将问题分解为多个子问题(阶段),按顺序求解,前一个问题的解为后一个问题提供信息
- 适用情况
- 最优化原理:问题的最优解所包含的子问题的解也是最优的,即最优子结构
- 无后效性:某个状态一旦确定,就不受以后决策的影响
- 有重叠子问题
- 说明
- 递推关系是从次小的问题开始到较大问题的转化,往往可以用递归来实现,可以利用之前产生的子问题的解来减少重复的计算
回溯法
- 基本思想
- 选优搜索法,走不通就退回重选,按照深度优先搜索的策略,从根节点出发,深度搜索解空间
- 步骤
- 确定解空间
- 确定节点的扩展搜索规则
- 深度优先方式搜索解空间,用剪枝法避免无效搜索
分支界限法
- 基本思想
- 与回溯法类似,也是在解空间里搜索解得算法,不同点是,回溯法寻找所有解,分支界限法搜索一个解或者最优解
- 分支:广度优先策略或者最小耗费(最大效益)优先
- 分支搜索方式:FIFO、LIFO、优先队列式、分支界限搜索算法
贪心算法
- 基本思想
- 不从总体最优考虑,仅考虑局部最优解,问题必须具备后无效性
- 步骤
- 将问题分解为多个子问题
- 得到问题的局部最优解
- 合并子问题的局部最优解
- 适用情况
- 局部最优策略能导致全局最优解
- 子问题后无效性