常用的十种算法

五、贪心算法

5.1 贪心算法介绍

1. 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法

2. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

5.2 贪心算法最佳应用-集合覆盖

广播台	覆盖地区
K1	“北京”, “上海”, “天津”
K2	“广州”, “北京”, “深圳”
K3	“成都”, “上海”, “杭州”
K4	“上海”, “天津”
K5	“杭州”, “大连”

2. 思路分析:

• 如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有 n 个广播台，则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算 10 个子集， 如图:

广播台数量n	子集总数2ⁿ	需要的时间
5	32	3.2秒
10	1024	102.4秒
32	4294967296	13.6年
100	1.26*100³º	4x10²³年

• 使用贪婪算法，效率高:

1. 目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:
2. 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
3. 将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
4. 重复第 1 步直到覆盖了全部的地区

• 代码实现

public class GreedyAlgorithm {public static void main(String[] args) {//创建广播电台,放入到MapHashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();//将各个电台放入到broadcastsHashSet<String> hashSet1 = new HashSet<String>();hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");HashSet<String> hashSet2 = new HashSet<String>();hashSet2.add("广州");hashSet2.add("北京");hashSet2.add("深圳");HashSet<String> hashSet3 = new HashSet<String>();hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");HashSet<String> hashSet4 = new HashSet<String>();hashSet4.add("上海");hashSet4.add("天津");HashSet<String> hashSet5 = new HashSet<String>();hashSet5.add("杭州");hashSet5.add("大连");//加入到mapbroadcasts.put("K1", hashSet1);broadcasts.put("K2", hashSet2);broadcasts.put("K3", hashSet3);broadcasts.put("K4", hashSet4);broadcasts.put("K5", hashSet5);//allAreas 存放所有的地区HashSet<String> allAreas = new HashSet<String>();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大连");//创建ArrayList, 存放选择的电台集合ArrayList<String> selects = new ArrayList<String>();//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集HashSet<String> tempSet = new HashSet<String>();//定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key//如果maxKey 不为null , 则会加入到 selectsString maxKey = null;while(allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区//每进行一次while,需要maxKey = null;//遍历 broadcasts, 取出对应keyfor(String key : broadcasts.keySet()) {//每进行一次fortempSet.clear();//当前这个key能够覆盖的地区HashSet<String> areas = broadcasts.get(key);tempSet.addAll(areas);//求出tempSet 和   allAreas 集合的交集, 交集会赋给 tempSettempSet.retainAll(allAreas);//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多//就需要重置maxKey// tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的if(tempSet.size() > 0 && (maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){maxKey = key;}}//maxKey != null, 就应该将maxKey 加入selectsif(maxKey != null) {selects.add(maxKey);//将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉allAreas.removeAll(broadcasts.get(maxKey));}}System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]}}

5.3 贪心算法注意事项和细节

1. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
2. 比如上题的算法选出的是 K1, K2, K3, K5，符合覆盖了全部的地区
3. 但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果 K4 的使用成本低于 K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的

六、普里姆算法

6.1 最小生成树

最小生成树(Minimum Cost Spanning Tree)，简称 MST。给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树

1. N 个顶点，一定有 N-1 条边
2. 包含全部顶点
3. N-1 条边都在图中
4. 举例说明(如图:)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l6ZdiCBT-1642651327417)(C:\Users\asus\AppData\Roaming\Typora\typora-user-images\image-20220120100732646.png)]

5. 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法

6.2 普里姆算法介绍

普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的连通子图，也就是所谓的极小连通子图

普利姆的算法如下:

1. 设 G=(V,E)是连通网（V是非空集合，称为顶点集。E是V中元素构成的无序二元组的集合，称为边集），T=(U,D)（U,D同V,E）是最小生成树，V,U 是顶点集合，E,D 是边的集合
2. 若从顶点 u 开始构造最小生成树，则从集合 V 中取出顶点 u 放入集合 U 中，标记顶点 v 的 visited[u]=1
3. 若集合 U 中顶点 ui 与集合 V-U 中的顶点 vj 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点 vj 加入集合 U 中，将边（ui,vj）加入集合 D 中，标记 visited[vj]=1
4. 重复步骤②，直到 U 与 V 相等，即所有顶点都被标记为访问过，此时 D 中有 n-1 条边
5. 图解普利姆算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3hjiEA14-1642651327418)(C:\Users\asus\AppData\Roaming\Typora\typora-user-images\image-20220120101433162.png)]

6.3 普里姆算法最佳实践(修路问题)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y7zvAlhb-1642651327418)(C:\Users\asus\AppData\Roaming\Typora\typora-user-images\image-20220120101455049.png)]

1. 有胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把 7 个村庄连通
2. 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
3. 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
4. 代码演示:

public class PrimAlgorithm {public static void main(String[] args) {//测试看看图是否创建okchar[] data = new char[]{'A','B','C','D','E','F','G'};int verxs = data.length;//邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通int [][]weight=new int[][]{{10000,5,7,10000,10000,10000,2},{5,10000,10000,9,10000,10000,3},{7,10000,10000,10000,8,10000,10000},{10000,9,10000,10000,10000,4,10000},{10000,10000,8,10000,10000,5,4},{10000,10000,10000,4,5,10000,6},{2,3,10000,10000,4,6,10000},};//创建MGraph对象MGraph graph = new MGraph(verxs);//创建一个MinTree对象MinTree minTree = new MinTree();minTree.createGraph(graph, verxs, data, weight);//输出minTree.showGraph(graph);//测试普利姆算法minTree.prim(graph, 1);// }}//创建最小生成树->村庄的图
class MinTree {//创建图的邻接矩阵/*** * @param graph 图对象* @param verxs 图对应的顶点个数* @param data 图的各个顶点的值* @param weight 图的邻接矩阵*/public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {int i, j;for(i = 0; i < verxs; i++) {//顶点graph.data[i] = data[i];for(j = 0; j < verxs; j++) {graph.weight[i][j] = weight[i][j];}}}//显示图的邻接矩阵public void showGraph(MGraph graph) {for(int[] link: graph.weight) {System.out.println(Arrays.toString(link));}}//编写prim算法，得到最小生成树/*** * @param graph 图* @param v 表示从图的第几个顶点开始生成'A'->0 'B'->1...*/public void prim(MGraph graph, int v) {//visited[] 标记结点(顶点)是否被访问过int visited[] = new int[graph.verxs];//visited[] 默认元素的值都是0, 表示没有访问过
//		for(int i =0; i <graph.verxs; i++) {
//			visited[i] = 0;
//		}//把当前这个结点标记为已访问visited[v] = 1;//h1 和 h2 记录两个顶点的下标int h1 = -1;int h2 = -1;int minWeight = 10000; //将 minWeight 初始成一个大数，后面在遍历过程中，会被替换for(int k = 1; k < graph.verxs; k++) {//因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边//这个是确定每一次生成的子图 ，和哪个结点的距离最近for(int i = 0; i < graph.verxs; i++) {// i结点表示被访问过的结点for(int j = 0; j< graph.verxs;j++) {//j结点表示还没有访问过的结点if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {//替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)minWeight = graph.weight[i][j];h1 = i;h2 = j;}}}//找到一条边是最小System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);//将当前这个结点标记为已经访问visited[h2] = 1;//minWeight 重新设置为最大值 10000minWeight = 10000;}}
}class MGraph {int verxs; //表示图的节点个数char[] data;//存放结点数据int[][] weight; //存放边，就是我们的邻接矩阵public MGraph(int verxs) {this.verxs = verxs;data = new char[verxs];weight = new int[verxs][verxs];}
}

七、克鲁斯卡尔算法

7.1 克鲁斯卡尔算法介绍

1. 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
2. 基本思想：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路
3. 具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

7.2 克鲁斯卡尔算法的原理和步骤

以城市公交站问题来图解说明 克鲁斯卡尔算法的原理和步骤：

在含有 n 个顶点的连通图中选择 n-1 条边，构成一棵极小连通子图，并使该连通子图中 n-1 条边上权值之和达到最小，则称其为连通网的最小生成树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8oEylMtJ-1642651327418)(C:\Users\asus\AppData\Roaming\Typora\typora-user-images\image-20220120104552931.png)]

例如，对于如上图 G4 所示的连通网可以有多棵权值总和不相同的生成树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YpTKiT2l-1642651327419)(C:\Users\asus\AppData\Roaming\Typora\typora-user-images\image-20220120104614185.png)]

7.2.1 克 鲁 斯 卡 尔 算 法 图 解

以上图 G4 为例，来对克鲁斯卡尔进行演示(假设，用数组 R 保存最小生成树结果)。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6NyK5o89-1642651327420)(C:\Users\asus\AppData\Roaming\Typora\typora-user-images\image-20220120104715997.png)]

• 第 1 步：将边<E,F>加入 R 中。
  边<E,F>的权值最小，因此将它加入到最小生成树结果 R 中。
• 第 2 步：将边<C,D>加入 R 中。
  上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果 R 中。
• 第 3 步：将边<D,E>加入 R 中。
  上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果 R 中。
• 第 4 步：将边<B,F>加入 R 中。
  上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果 R 中。
• 第 5 步：将边<E,G>加入 R 中。
  上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果 R 中。
• 第 6 步：将边<A,B>加入 R 中。
  上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果 R 中。
  此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。

7.2.2 克 鲁 斯 卡 尔 算 法 分 析

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一很好解决，采用排序算法进行排序即可。
问题二，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

7.2.3 如 何 判 断 是 否 构 成 回 路 -举 例 说 明 (如 图 )

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6EqracPi-1642651327420)(C:\Users\asus\AppData\Roaming\Typora\typora-user-images\image-20220120105003030.png)]

在将<E,F> <C,D> <D,E>加入到最小生成树 R 中之后，这几条边的顶点就都有了终点：

(01) C 的终点是 F。
(02) D 的终点是 F。
(03) E 的终点是 F。
(04) F 的终点是 F。

关于终点的说明：

1. 就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。
2. 因此，接下来，虽然<C,E>是权值最小的边。但是 C 和 E 的终点都是 F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。也就是说，我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路。【后面有代码说明】

7.3 克鲁斯卡尔最佳实践-公交站问题

看一个公交站问题：

1. 有北京有新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通
2. 各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里
3. 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
4. 代码实现和注解

public class KruskalCase {private int edgeNum; //边的个数private char[] vertexs; //顶点数组private int[][] matrix; //邻接矩阵//使用 INF 表示两个顶点不能连通private static final int INF = Integer.MAX_VALUE;public static void main(String[] args) {char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};//克鲁斯卡尔算法的邻接矩阵  int matrix[][] = {/*A*//*B*//*C*//*D*//*E*//*F*//*G*//*A*/ {   0,  12, INF, INF, INF,  16,  14},/*B*/ {  12,   0,  10, INF, INF,   7, INF},/*C*/ { INF,  10,   0,   3,   5,   6, INF},/*D*/ { INF, INF,   3,   0,   4, INF, INF},/*E*/ { INF, INF,   5,   4,   0,   2,   8},/*F*/ {  16,   7,   6, INF,   2,   0,   9},/*G*/ {  14, INF, INF, INF,   8,   9,   0}}; //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.//创建KruskalCase 对象实例KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);//输出构建的kruskalCase.print();kruskalCase.kruskal();}//构造器public KruskalCase(char[] vertexs, int[][] matrix) {//初始化顶点数和边的个数int vlen = vertexs.length;//初始化顶点, 复制拷贝的方式this.vertexs = new char[vlen];for(int i = 0; i < vertexs.length; i++) {this.vertexs[i] = vertexs[i];}//初始化边, 使用的是复制拷贝的方式this.matrix = new int[vlen][vlen];for(int i = 0; i < vlen; i++) {for(int j= 0; j < vlen; j++) {this.matrix[i][j] = matrix[i][j];}}//统计边的条数for(int i =0; i < vlen; i++) {for(int j = i+1; j < vlen; j++) {if(this.matrix[i][j] != INF) {edgeNum++;}}}}public void kruskal() {int index = 0; //表示最后结果数组的索引int[] ends = new int[edgeNum]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点//创建结果数组, 保存最后的最小生成树EData[] rets = new EData[edgeNum];//获取图中 所有的边的集合 ， 一共有12边EData[] edges = getEdges();System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12//按照边的权值大小进行排序(从小到大)sortEdges(edges);//遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入for(int i=0; i < edgeNum; i++) {//获取到第i条边的第一个顶点(起点)int p1 = getPosition(edges[i].start); //p1=4//获取到第i条边的第2个顶点int p2 = getPosition(edges[i].end); //p2 = 5//获取p1这个顶点在已有最小生成树中的终点int m = getEnd(ends, p1); //m = 4//获取p2这个顶点在已有最小生成树中的终点int n = getEnd(ends, p2); // n = 5//是否构成回路if(m != n) { //没有构成回路ends[m] = n; // 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]rets[index++] = edges[i]; //有一条边加入到rets数组}}//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。//统计并打印 "最小生成树", 输出  retsSystem.out.println("最小生成树为");for(int i = 0; i < index; i++) {System.out.println(rets[i]);}}//打印邻接矩阵public void print() {System.out.println("邻接矩阵为: \n");for(int i = 0; i < vertexs.length; i++) {for(int j=0; j < vertexs.length; j++) {System.out.printf("%12d", matrix[i][j]);}System.out.println();//换行}}/*** 功能：对边进行排序处理, 冒泡排序* @param edges 边的集合*/private void sortEdges(EData[] edges) {for(int i = 0; i < edges.length - 1; i++) {for(int j = 0; j < edges.length - 1 - i; j++) {if(edges[j].weight > edges[j+1].weight) {//交换EData tmp = edges[j];edges[j] = edges[j+1];edges[j+1] = tmp;}}}}/*** * @param ch 顶点的值，比如'A','B'* @return 返回ch顶点对应的下标，如果找不到，返回-1*/private int getPosition(char ch) {for(int i = 0; i < vertexs.length; i++) {if(vertexs[i] == ch) {//找到return i;}}//找不到,返回-1return -1;}/*** 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组* 是通过matrix 邻接矩阵来获取* EData[] 形式 [['A','B', 12], ['B','F',7], .....]* @return*/private EData[] getEdges() {int index = 0;EData[] edges = new EData[edgeNum];for(int i = 0; i < vertexs.length; i++) {for(int j=i+1; j <vertexs.length; j++) {if(matrix[i][j] != INF) {edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);}}}return edges;}/*** 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同* @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成* @param i : 表示传入的顶点对应的下标* @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解*/private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]while(ends[i] != 0) {i = ends[i];}return i;}}//创建一个类EData ，它的对象实例就表示一条边
class EData {char start; //边的一个点char end; //边的另外一个点int weight; //边的权值//构造器public EData(char start, char end, int weight) {this.start = start;this.end = end;this.weight = weight;}//重写toString, 便于输出边信息@Overridepublic String toString() {return "EData [<" + start + ", " + end + ">= " + weight + "]";}}

---

另外几种算法：

常用的十种算法：二分查找，分治，动态规划，KMP

参考视频：尚硅谷Java数据结构与java算法（Java数据结构与算法）