算法图解笔记
- 分治策略
- 散列函数
- 广度优先搜索
- 狄克斯特拉算法
- 动态规划
算法图解(pdf版) 链接:https://pan.baidu/s/1FJvija2NNmhOSpd7D3yE_g 提取码:bwcm
分治策略
分治策略(分而治之)是一种解决问题的思路,使用递归实现
工作原理:
- 找出简单基线条件(递归中的概念,基线条件指函数不再调用自己;递归条件指函数调用自己)
- 缩小问题规模使接近基线条件(编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素。陷入困境时,请检查基线条件是不是这样的。)
代表算法:二分查找,快排
散列函数
散列表适用场景
- 模拟映射关系
- 防止重复
- 数据缓存
注意的点
- 冲突很糟糕,应使用可以最大限度减少冲突的散列函数(冲突过多会影响数据查找、删除速度;严重时会退化为链表)
- 一旦填装因子超过0.7,就该调整散列表的长度
广度优先搜索
广度优先是一种用于图的查找算法,一般用来帮助解决两类问题:
- 有无路径问题(从节点A出发,有到节点B的路径吗?)
- 最短路径问题(从节点A触发,前往节点B哪条路径最短?)
注意点
- 对于寻找最短路径的问题,可尝试使用图来建立模型,再使用广度优先搜索来解决问题
- 有向图中的边为箭头,箭头的方向指定了关系的方向
- 无向图中的边不带箭头,其中的关系是双向的
- 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必须是队列
- 对于检查过的人,务必不要再去检查,否则可能导致无限循环(节点间的相互引用)
狄克斯特拉算法
在介绍迪克斯特拉算法前,先介绍一些基础概念
每条边都有关联数字的图,这些数字称为权重
带权重的图称为加权图,不带权重的图称为非加权图
图中可能有环
狄克斯特拉算法包含4个步骤。
- 找出“最便宜”的节点,即可在最短时间内到达的节点
- 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销
- 重复这个过程,直到对图中的每个节点都这样做了
- 计算最终路径
注意点
- 狄克斯特拉算法只适用于有向无环图
- 不能将狄克斯特拉算法用于包含负权边的图
小结
- 广度优先搜索用于在非加权图中查找最短路径。
- 狄克斯特拉算法用于在加权图中查找最短路径。
- 仅当权重为正时狄克斯特拉算法才管用。
- 如果图中包含负权边,请使用贝尔曼福德算法。
算法的Java实现
public class MyDijkstra {
private static int NOWAY_SIGN = Integer.MAX_VALUE;
private static String START = "start";
private static String END = "end";
public static void main(String[] args) {
MyDijkstra dijkstra = new MyDijkstra();
dijkstra.getMinStep();
}
private void getMinStep(){
// 初始化
Map<String, Map<String, Integer>> grapth = grapthInit();
Map<String, Integer> costs = costInit();
Map<String, String> parents = parentInit();
// 判断是否检查过
List<String> processed = new ArrayList<>(10);
// 1. 找到start的最小开销节点
String node = this.findLowestCostNode(costs,processed);
// 2. 遍历该节点所有邻居并更新其开销
while (node != null && grapth.get(node) != null){
// 获取相邻节点
Map<String, Integer> xianglinjiedian = grapth.get(node);
int cost = costs.get(node);
for (Map.Entry<String, Integer> entry : xianglinjiedian.entrySet()) {
// 新旧开销的比较,若成功则更新
int newCost = cost + entry.getValue();
if(newCost < costs.get(entry.getKey()) || !costs.containsKey(entry.getKey())){
costs.put(entry.getKey(),newCost);
parents.put(entry.getKey(),node);
}
}
// 加入已处理节点
processed.add(node);
// 找出最小开销节点
node = this.findLowestCostNode(costs,processed);
}
System.out.println(parents);
System.out.println(costs.get(END));
}
private String findLowestCostNode(Map<String, Integer> costs,List<String> processed){
int lowestCost = NOWAY_SIGN;
String lowNode = null;
for (Map.Entry<String, Integer> entry : costs.entrySet()) {
// 未被处理且小于mini
if(!processed.contains(entry.getKey()) && entry.getValue() < lowestCost){
lowestCost = entry.getValue();
lowNode = entry.getKey();
}
}
return lowNode;
}
private Map<String,String> parentInit() {
Map<String,String> parentInit = new HashMap<>(16);
parentInit.put("A",START);
parentInit.put("B",END);
parentInit.put(END,null);
return parentInit;
}
private Map<String,Integer> costInit() {
Map<String,Integer> costsMap = new HashMap<>(16);
costsMap.put("A",6);
costsMap.put("B",2);
costsMap.put(END,Integer.MAX_VALUE);
return costsMap;
}
// 构造有向图
private Map<String, Map<String,Integer>> grapthInit() {
Map<String, Map<String,Integer>> grapth = new HashMap<>(16);
Map<String,Integer> startValue1 = new HashMap<>(2);
startValue1.put("A",6);
startValue1.put("B",2);
grapth.put(START,startValue1);
Map<String,Integer> startValue2 = new HashMap<>(2);
startValue2.put(END,1);
grapth.put("A",startValue2);
Map<String,Integer> startValue3 = new HashMap<>(2);
startValue3.put("A",3);
startValue3.put(END,5);
grapth.put("B",startValue3);
grapth.put(END,null);
return grapth;
}
}
- 贪婪算法
动态规划
学习点
-
学习动态规划,这是一种解决棘手问题的方法,它将问题分成小问题,并先着手解决这些小问题
-
学习如何设计问题的动态规划解决方案
工作原理
- 先解决子问题,再逐渐解决大问题
课后答案
9.1 假设你还可偷另外一件商品——MP3播放器,它重1磅,价值1000美元。你要偷吗?
不要,因为重1磅的吉他价值1500磅,所有偷Mp3播放器在本题中目前没有意义
9.2 假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要:
水(重3磅,价值10)
书(重1磅,价值3)
食物(重2磅,价值9)
夹克(重2磅,价值5)
相机(重1磅,价值6)
请问携带哪些东西时价值最高?
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
水 | 10(水) | 10(水) | 10(水) | 10(水) | ||
书 | 3(书) | 3(书) | 10(水) | 13(水、书) | 13(水、书) | 13(水、书 |
食物 | 3(书) | 9(食物) | 11(书、食物) | 13(水、书) | 19(水、食物) | 22(水、书、食物) |
夹克 | 3(书) | 9(食物) | 11(书、食物) | 14(食物、夹克) | 19(水、食物) | 22(水、书、食物) |
相机 | 6(相机) | 9(书、相机) | 15(食物、相机) | 17(书、食物、相机) | 20(食物、夹克、相机) | 25(水、食物、相机) |
9.3 请绘制并填充用来计算blue和clues最长公共子串的网格
最长公共子串:
b | l | u | e | |
---|---|---|---|---|
c | 0 | 0 | 0 | 0 |
l | 0 | 1 | 0 | 0 |
u | 0 | 0 | 2 | 0 |
e | 0 | 0 | 0 | 3 |
s | 0 | 0 | 0 | 0 |
最长公共子序列:
b | l | u | e | |
---|---|---|---|---|
c | 0 | 0 | 0 | 0 |
l | 0 | 1 | 1 | 1 |
u | 0 | 1 | 2 | 3 |
e | 0 | 1 | 2 | 3 |
s | 0 | 1 | 2 | 3 |
背包问题启示
- 每种动态规划解决方案都涉及网格。
- 单元格中的值通常就是你要优化的值。在前面的背包问题中,单元格的值为商品的价值。
- 每个单元格都是一个子问题,因此你应考虑如何将问题分成子问题,这有助于你找出网格的坐标轴。
小结
- 需要在给定约束条件下优化某种指标时,动态规划很有用。
- 问题可分解为离散子问题时,可使用动态规划来解决。
- 每种动态规划解决方案都涉及网格。
- 单元格中的值通常就是你要优化的值。
- 每个单元格都是一个子问题,因此你需要考虑如何将问题分解为子问题。
- 没有放之四海皆准的计算动态规划解决方案的公式
更多推荐
算法图解笔记(附PDF下载地址)
发布评论