四种思想
2020-04-09 17:42:11 0 举报AI智能生成
登录查看完整内容
四种算法思想要点及练习
作者其他创作
大纲/内容
四种思想
贪心算法如何用贪心算法实现Huffman压缩编码？
应用
霍夫曼编码（Huffman Coding）
Prim 和 Kruskal 最小生成树算法
Dijkstra 单源最短路径算法
解决步骤：
1.想到贪心思想
针对一组数据，在满足限制值的情况下，求期望值最大的结果
2.尝试贪心思想是否适合
选择当前，对限制值同等贡献的情况下，对期望值贡献最大的数据
3.举例验证
是否最优
不一定总是最优
当前面的选择影响后面的选择时
实战分析
分糖果
钱币找零
区间覆盖
霍夫曼编码
十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间
使用不等长的编码来提高压缩效率
考察出现的不同字符以及字符出现的频率
根据频率选择编码
频率高的用短编码、频率低的用较长编码
避免解压过程歧义，要求不能一个编码是另一个编码的情况
如何根据频率计算编码？
课后思考
在非负数a中，如何移除k个数字使所剩数字最小？
分治算法谈大数据计算框架MapReduce中的分治思想
核心：分而治之
分治算法是一种处理问题的思想，递归是一种编程技巧。分治算法一般都比较适合用递归来实现
分治算法的递归实现中，每一层递归都会涉及三个操作
分解：将原问题分解成一系列子问题
解决：递归地求解各个子问题，若子问题足够小，则直接求解
合并：将子问题的结果合并成原问题
适合分治算法的场景
原问题与分解成的小问题具有相同的模式
原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别
具有分解终止条件
可以将子问题合并成原问题，且这个合并操作的复杂度不能太高
应用举例
求一组数据的有序对个数或者逆序对个数？
归并排序
二维平面上有 n 个点，如何快速计算出两个距离最近的点对？
有两个 n*n 的矩阵 A，B，如何快速求解两个矩阵的乘积 C=A*B？
分治思想在海量数据处理中的应用
解决数据量大到内存装不下的问题
MapReduce
数据与数据之间存在关系的任务
统计文件中单词出现的频率
数据与数据之间没有关系的任务
网页分析、分词等
回溯算法从《蝴蝶效应》学回溯算法核心思想
深度优先搜索、正则表达式匹配、编译原理中的词法分析
数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等
理解
搜索问题：在一组可能的解中，搜索满足期望的解
处理思想：有点类似枚举搜索
剪枝操作是提高回溯效率的一种技巧
八皇后问题
经典应用
0-1背包
正则表达式
课后思考：对今天讲到的 0-1 背包问题稍加改造，如果每个物品不仅重量不同，价值也不同。如何在不超过背包重量的情况下，让背包中的总价值最大？
动态规划
初识：如何巧妙解决双十一购物凑单问题
0-1背包升级版
理论：搞懂最优子结构、无后效性和重复子问题
实战：如何实现搜索引擎中的拼写纠错功能？
0 条评论
回复 删除
下一页
