

首页  思维导图  详情



四种思想

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-1背包升级版

理论：搞懂最优子结构、无后效性和重复子问题

实战：如何实现搜索引擎中的拼写纠错功能？

 Collect

Get Started

Linux系统bash的四种模式与jenkins执行shel

 Collect

Get Started

Exchange四种路由策略

 Collect

Get Started

四种意见

 Collect

Get Started

如何获得四种大脑“快乐激素





0 条评论

下一页