数据结构学习笔记 - 常见算法思想

今天药忘吃喽~ 2022-09-02 05:19 136阅读 0赞

## 常见算法思想 ##

### 简介 ###

几种常见的算法思想, 用来指导我们设计具体的算法和编码, 有  
贪心算法, 分治算法, 回溯算法, 动态规划

### 贪心算法(greedy algorithm) ###

经典应用, 霍夫曼编码, Prim和Kruskal最小生成树算法, Dijkstra单源最短路径算法  
经典问题, 背包问题, 固定容量下, 让背包里装的物品总价值最大, 贪心算法用法则是计算物品单价, 单价从高到低依次放入包中  
使用贪心算法解决问题的步骤

*  第一步, 看到这类问题, 首先联想到贪心算法
 *  尝试看下这个问题是否能用贪心算法解决
 *  举例看下贪心算法产生的结果是否是最优解  
    大部分能用贪心算法的问题, 结果都是正确的, 但也有解决不掉的问题, 比如前面的选择会影响后面的选择, 局部最优未必全局最优  
    类似能用贪心算法解决的问题, 分糖果, 钱币找零, 区间覆盖等  
    贪心算法最难的是如何将要解决的问题抽象成贪心算法模型, 后续的编码一般都很简单  
    贪心算法解决问题的正确性虽然很多时候都很高, 但要严谨的证明算法能得到最优解, 并不容易

### 分治算法 ###

分治算法核心思想就是四个字, 分而治之, 将原问题划分为n个规模较小, 并且结构与原问题相似的子问题, 递归的解决这些子问题, 然后再合并其结果, 就得到原问题的解  
有点类似递归, 分治算法是一种处理问题的思想, 递归是一种编程技巧, 分治算法一般都比较适合用递归来实现  
分治算法能解决的问题, 一般需要满足下面几个条件

*  原问题与分解成的小问题具有相同的模式
 *  原问题分解成的子问题可以独立求解, 子问题之前没有相关性(和动态规划的明显区别)
 *  具有分解终止条件, 当问题足够小时, 可以直接求解
 *  可以将子问题合并成原问题, 且合并操作复杂度不太高, 否则起不到减小算法总体复杂度的效果  
    分治算法两种典型的应用场景
 *  用来指导编码, 降低问题求解的时间复杂度
 *  解决海量数据处理问题, 比如MapReduce

### 回溯算法 ###

之前的深度优先搜索算法利用的就是回溯思想, 这个算法思想简单却应用广泛  
比如正则表达式, 编译原理中的语法分析, 很多经典数学问题比如数独, 八皇后, 0-1背包, 图的着色, 旅行商问题, 全排列等等  
回溯的处理思想有点类似枚举搜索, 枚举出所有的解, 然后找到满足期望的解, 为了枚举所有可能的解, 避免遗漏和重复, 我们把问题求解的过程分为多个阶段  
每个阶段面对一个岔路口, 先随意选一条路走, 当发现这条路走不通, 就退回上一个岔路口, 选另一种走法继续走  
示例: 八皇后问题(todo), 0-1背包(todo)  
大部分情况下, 回溯算法都可以用来解决广义的搜索问题, 即从一组可能的解中, 选择一个满足要求的解  
回溯算法非常适合用递归来实现, 在实现的过程中, 剪枝操作是提高回溯效率的一种技巧

### 动态规划 ###

[单开一篇文章][Link 1]

[Link 1]: https://blog.csdn.net/u012355401/article/details/119254678