算法笔记（二）--- 五大常用算法

2020-04-13 11:48:49 蜻蜓队长

分治，就是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法常常跟递归一起使用，借助递归，我们可以方便地将问题分解再将结果合并。

常见应用场景：

　　二分搜索
　　大整数除法
　　Strassen矩阵乘法
　　棋盘覆盖
　　归并排序
　　快速排序
　　线性时间选择
　　最接近点对问题
　　循环赛日程表
　　汉诺塔

Dynamic programming，缩写：DP

通过将原问题分解为相对简单的子问题的方式来求解复杂问题。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

常见应用场景：

　　斐波那契数列

1）基本概念：

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

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

2）适用前提
　　局部最优策略能导致产生全局最优解。

3）贪心算法基本步骤
　　建立数学模型来描述问题。
　　把求解的问题分成若干个子问题。
　　对每一子问题求解，得到子问题的局部最优解。
　　把子问题的解局部最优解合成原来解问题的一个解。

1）概念
　　在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

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

2）基本思想
　　在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

　　若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

　　而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

3）回溯基本步骤
　　针对所给问题，确定问题的解空间:首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解；
　　确定结点的扩展搜索规则；
　　以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

　　回溯算法是深度优先，那么分支限界法就是广度优先的一个经典的例子。回溯法一般来说是遍历整个解空间，获取问题的所有解，而分支限界法则是获取一个解（一般来说要获取最优解）。

典型适用场景：

以上内容来自于网络,如有侵权联系即删除