[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G8rCJ2vk-1645791772844)(C:\Users\luo’xin\AppData\Roaming\Typora\typora-user-images\image-20220223143121774.png)]
这个图和前面两个算法的图一样,前面两个算法是求一个图的最小生成树,而迪杰斯特拉算法是求一个图中一个点到其他顶点的最小路径。
关于迪杰斯特拉算法的思路,推荐博客,简单易懂生动。
从上面的博客我们可以知道迪杰斯特拉算法步骤如下:
上面的操作都比较简单,除了更新集合权值。我们可以发现所有要更新权值的点其实都是被选中点的直连点,多以对于更新操作,我们只需先获取删除点的直连点,然后一个一个的比较 原来的权值 和 本身到被删除点的权值 + 被删除点的权值,如果本身到被删除点的权值 + 被删除点的权值 小于 原来的权值的话,则更新,否则不用更新。
我自己写的代码如下:
/** * @author: luoxin * @create: 2022-02-23 11:39 **/ package cn.luoxin88.algorithm.dijkstra; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; public class DijkstraAlgorithm { public static void main(String[] args) { char[] data = {'A','B','C','D','E','F','G'}; int[][] weight = {{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}}; MGragh gragh = new MGragh(data, weight); DijkstraAlgorithm dijkstraAlgorithm = new DijkstraAlgorithm(); HashSet<Verx> set = dijkstraAlgorithm.dijkstra(gragh,0); System.out.println(set); } public HashSet<Verx> dijkstra(MGragh gragh, int index) { //两个集合 HashSet<Verx> oldSet = new HashSet<>(); HashSet<Verx> newSet = new HashSet<>(); //集合初始化 for(int i=0;i< gragh.verx;i++) { if(i!=index) { oldSet.add(new Verx(i,gragh.weight[i][index])); } } newSet.add(new Verx(index,0)); System.out.println("原始old : "+oldSet); System.out.println("原始new : "+newSet); //不断地循环取值,直到原集合为空 Verx temp, object = null; while(!oldSet.isEmpty()) { //从原集合选取一个权值最小的顶点 int minValue = 10000; Iterator<Verx> iterator = oldSet.iterator(); //获取当前集合最小点 while(iterator.hasNext()) { temp = iterator.next(); if(temp.value<minValue) { minValue = temp.value; object = temp; } } //从原集合删除,添加至新集合 oldSet.remove(object); newSet.add(object); //更新原集合各顶点权值 fresh(oldSet, gragh, object); System.out.println("old : "+oldSet); System.out.println("new:"+newSet); } return newSet; } public void fresh(HashSet<Verx> set, MGragh gragh, Verx verx) { //找到和verx直连的各个顶点,然后比较 原权值 与 (到verx的距离 + verx权值) Iterator<Verx> iterator = set.iterator(); Verx temp = null; while(iterator.hasNext()) { temp = iterator.next(); //如果是直连 if(gragh.weight[temp.index][verx.index] != 10000) { //如果(到verx的距离 + verx权值) 《 原权值,更新 if(( gragh.weight[temp.index][verx.index]+ verx.value) < temp.value) { //注意不能用下面的方法,在迭代器迭代的时候不允许直接对原集合进行增删操作 //否则会报ConcurrentModificationException的错 //set.remove(temp); //set.add(new Verx(temp.index, ( gragh.weight[temp.index][verx.index]+ verx.value))); temp.value = ( gragh.weight[temp.index][verx.index]+ verx.value); } } } } } class Verx { int index; int value; public Verx(int index,int value) { this.index = index; this.value = value; } char[] arr = {'A','B','C','D','E','F','G'}; @Override public String toString() { return "[" + "index=" + arr[index] + ", value=" + value + ']'; } } class MGragh { int verx;//表示图的节点个数 char[] data ;//存放节点数据 int[][] weight;//存放边,就是我们的邻接矩阵 public MGragh(int verx) { data = new char[verx]; weight = new int[verx][verx]; } public MGragh(char[] data, int[][] weight) { this.verx = data.length; this.data = new char[this.verx]; this.weight = new int[this.verx][this.verx]; int i,j; for (i=0;i<this.verx;i++) { this.data[i] = data[i]; for(j=0;j<verx;j++) { this.weight[i][j] = weight[i][j]; } } } public static void showGragh(MGragh gragh) { for(int[] row : gragh.weight) { System.out.println(Arrays.toString(row)); } } }
过程如下:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XWfM72d0-1645791772846)(C:\Users\luo’xin\AppData\Roaming\Typora\typora-user-images\image-20220224083212478.png)]
可以看到和我们预想的是一样的。
和Dijkstra算法一样,Floyd算法也是用于寻找给定的加权图中顶点间的最短路径算法。
Dijkstra算法计算图中一个顶点到其他顶点的最短路径,而Floyd算法计算图中各个顶点之间的最短路径。
Floyd算法的解题思路推荐博客,耐心看,很容易懂。
我也简单的说一下吧,初始的时候用一个二维矩阵存储各个点之间的距离,不可直接达的为无穷大。
我们需要不断地更新这个矩阵,致使最后的矩阵中M【i】【j】就是i和j之间的最短距离。
怎么更新 ?
我们知道,两个点之间的最短路径无非两种情况:
而初始的矩阵就列举了所有直连顶点之间的距离,当然这个距离未必是最短距离,因为有可能通过通过其他点的距离会比直连点之间的距离更短。
所以我们需要是不是通过直连点之后的距离会比现在的距离更短。通过直连点的个数也有很多可能,我们先考虑一个直连点的情况。我们不妨设这个直连点是 1 (下标)。我们需要对任意的i,j进行判断,是否 weight[i][j] > weigh[i]][1] + weigh[1]][j]。如果经过顶点后的值更小,则更新。
for(i=0;i<verx;i++) { for(j=0;j<verx;j++) { if(gragh.weight[i][j] > (gragh.weight[i][1] + gragh.weight[1][j])) { gragh.weight[i][j] = (gragh.weight[i][1] + gragh.weight[1][j]); } } }
更新完后我们就该考虑经过两个顶点的情况了,怎样看两个顶点?很简单,在原来的基础上再加一个顶点就行了,因为前面已经判断过1了,我们再判断一个2,
for(i=0;i<verx;i++) { for(j=0;j<verx;j++) { if(gragh.weight[i][j] > (gragh.weight[i][2] + gragh.weight[2][j])) { gragh.weight[i][j] = (gragh.weight[i][2] + gragh.weight[2][j]); } } }
其实这个过程和前面的Dijkstra算法也有点相似。
如果能够理解从1 到 2 这里,整个算法就很好说了 ,看下面。
public void floyd(MGragh gragh) { int verx = gragh.verx; int i,j,k; for(k=0;k<verx;k++) { for(i=0;i<verx;i++) { for(j=0;j<verx;j++) { if(gragh.weight[i][j] > (gragh.weight[i][k] + gragh.weight[k][j])) { gragh.weight[i][j] = (gragh.weight[i][k] + gragh.weight[k][j]); } } } } }
没错,就是这么简单。
import java.util.Arrays; public class FloydAlgorithm { public static void main(String[] args) { char[] data = {'A','B','C','D','E','F','G'}; int[][] weight = {{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}}; MGragh gragh = new MGragh(data, weight); gragh.showGragh(gragh); FloydAlgorithm floydAlgorithm = new FloydAlgorithm(); floydAlgorithm.floyd(gragh); MGragh.showGragh(gragh); } public void floyd(MGragh gragh) { int verx = gragh.verx; int i,j,k; for(k=0;k<verx;k++) { for(i=0;i<verx;i++) { for(j=0;j<verx;j++) { if(gragh.weight[i][j] > (gragh.weight[i][k] + gragh.weight[k][j])) { gragh.weight[i][j] = (gragh.weight[i][k] + gragh.weight[k][j]); } } } } } } class MGragh { int verx;//表示图的节点个数 char[] data ;//存放节点数据 int[][] weight;//存放边,就是我们的邻接矩阵 public MGragh(int verx) { data = new char[verx]; weight = new int[verx][verx]; } public MGragh(char[] data, int[][] weight) { this.verx = data.length; this.data = new char[this.verx]; this.weight = new int[this.verx][this.verx]; int i,j; for (i=0;i<this.verx;i++) { this.data[i] = data[i]; for(j=0;j<verx;j++) { this.weight[i][j] = weight[i][j]; } } } public static void showGragh(MGragh gragh) { for(int[] row : gragh.weight) { System.out.println(Arrays.toString(row)); } } }
马踏棋盘算法也叫骑士周游问题,讲的是把 马 随机放在 8x8的国际棋盘的某个方格中,马走日字(2x3)进行移动,要求每个棋盘只走一次,走遍棋盘上的全部64个方格。
我们很容易就能想到用图的深度优先遍历解题。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ggpgz7Ib-1645791772848)(C:\Users\luo’xin\AppData\Roaming\Typora\typora-user-images\image-20220224202846654.png)]
可以看到如果当前位置位(X,Y)的话,下一步能走的地方就是
我们到达一个位置后
import java.util.Arrays; public class Mataqp { public static final int LENGTH = 8; //标志位,标识是否遍历完成 private static boolean finished = false; //标识棋盘中哪些位置被访问了 private int[][] visited = new int[LENGTH][LENGTH]; public static void main(String[] args) { Mataqp mataqp = new Mataqp(); mataqp.mataqp(0,0); System.out.println(1); } public void mataqp(int x, int y) { MGragh gragh = new MGragh(LENGTH); for(int[] rows : gragh.weight) { System.out.println(Arrays.toString(rows)); } int count = 1; System.out.println("-------------------------------"); resoulv(x,y, gragh.weight,count); for(int[] rows : gragh.weight) { System.out.println(Arrays.toString(rows)); } } public void resoulv(int x, int y, int[][] weight, int count) { //将当前位置的值置为步数值 weight[x][y] = count; visited[x][y] = 1; //System.out.println("weight["+x+"]["+y+"] = "+count); //对八个位置进行合理性判断并递归 //如果点在棋盘内且未遍历,则递归 if(inner(x-2,y-1, LENGTH) && weight[x-2][y-1]==0) { resoulv(x-2, y-1, weight, count+1); } if(inner(x-1,y-2, LENGTH) && weight[x-1][y-2]==0) { resoulv(x-1, y-2, weight, count+1); } if(inner(x+1,y-2, LENGTH) && weight[x+1][y-2]==0) { resoulv(x+1, y-2, weight, count+1); } if(inner(x+2,y-1, LENGTH) && weight[x+2][y-1]==0) { resoulv(x+2, y-1, weight, count+1); } if(inner(x+2,y+1, LENGTH) && weight[x+2][y+1]==0) { resoulv(x+2, y+1, weight, count+1); } if(inner(x+1,y+2, LENGTH) && weight[x+1][y+2]==0) { resoulv(x+1, y+2, weight, count+1); } if(inner(x-1,y+2, LENGTH) && weight[x-1][y+2]==0) { resoulv(x-1, y+2, weight, count+1); } if(inner(x-2,y+1, LENGTH) && weight[x-2][y+1]==0) { resoulv(x-2, y+1, weight, count+1); } //所有的都不行,撤销,返回上一级 //八个都走完了且未完成,说明此路不通,回退一步 if(count != LENGTH * LENGTH && !finished) { weight[x][y] = 0; visited[x][y]=0; } else { finished = true; } } public boolean inner(int x, int y, int size) { if(x<size && x>=0 && y <size && y>=0) return true; return false; } } class Point { int x,y; public Point() { } public Point(int x, int y) { this.x = x; this.y = y; } @Override public String toString() { return "<"+x+", "+y+">"; } } class MGragh { int verx;//表示图的节点个数 char[] data ;//存放节点数据 int[][] weight;//存放边,就是我们的邻接矩阵 public MGragh(int verx) { this.verx = verx; data = new char[verx]; weight = new int[verx][verx]; } public MGragh(char[] data, int[][] weight) { this.verx = data.length; this.data = new char[this.verx]; this.weight = new int[this.verx][this.verx]; int i,j; for (i=0;i<this.verx;i++) { this.data[i] = data[i]; for(j=0;j<verx;j++) { this.weight[i][j] = weight[i][j]; } } } public static void showGragh(MGragh gragh) { for(int[] row : gragh.weight) { System.out.println(Arrays.toString(row)); } } }
前面的方式虽然可以达到效果,但是效率非常低。原因是每次递归时都是机械的按照8个位置的顺序进行递归的,这样就像蒙着眼睛一个方向一个方向的撞 一样 ,我们能不能有选择性的递归呢?每次递归都从最可能走完全程的位置开始呢。
假如在一个位置,它的下一步可以有5种走法。我们能知道这5种走法中那种走法走完的可能性高一些吗?显然是不能的,所以我们认为每种走法都有1/5的可能性走完。那我们怎么优化呢?假如现在有5条小路,告诉你长度分别为100.200.300.400.500米,小路的尽头有宝藏,每条小路有宝藏的效率都是一样的,你会怎么么走?很显然了吧,这里也一样,我们要走下一步最少的那个位置。
所以我们就不能像之前一样一个一个的判断遍历了,我们要把所有可能放在一个列表中,然后升序排序。递归式按照从小到大的顺序递归。
System.out.println(Arrays.toString(row));
}
}
}
### 4 . 马踏棋盘算法效率优化 前面的方式虽然可以达到效果,但是效率非常低。原因是每次递归时都是机械的按照8个位置的顺序进行递归的,这样就像蒙着眼睛一个方向一个方向的撞 一样 ,我们能不能有选择性的递归呢?每次递归都从最可能走完全程的位置开始呢。 假如在一个位置,它的下一步可以有5种走法。我们能知道这5种走法中那种走法走完的可能性高一些吗?显然是不能的,所以我们认为每种走法都有1/5的可能性走完。那我们怎么优化呢?假如现在有5条小路,告诉你长度分别为100.200.300.400.500米,小路的尽头有宝藏,每条小路有宝藏的效率都是一样的,你会怎么么走?很显然了吧,这里也一样,我们要走下一步最少的那个位置。 所以我们就不能像之前一样一个一个的判断遍历了,我们要把所有可能放在一个列表中,然后升序排序。递归式按照从小到大的顺序递归。