常用的10种算法（8~10）
一、迪杰斯特拉（Dijkstra）算法
应用场景----最短路径问题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G8rCJ2vk-1645791772844)(C:\Users\luo’xin\AppData\Roaming\Typora\typora-user-images\image-20220223143121774.png)]
这个图和前面两个算法的图一样，前面两个算法是求一个图的最小生成树，而迪杰斯特拉算法是求一个图中一个点到其他顶点的最小路径。
关于迪杰斯特拉算法的思路，推荐博客，简单易懂生动。
从上面的博客我们可以知道迪杰斯特拉算法步骤如下:
- 两个集合 U 和 S ，初始时U存放图中除起始点外的其它点，每个点还有一个值，这个值是该点通过S图和起始点的最小路径，例如A为起始点的话B的权值为5而D的权值为无穷大（由于不可通过S达到），S存放起始点，S中每个点也有一个权值，代表该点到起始点的最小路径，也就是我们需要的。
- 从U中选一个权值最小的点，从U中删除并添加至S集合，权值为原来在U中的权值。
- 更新U集合中其他点的权值，因为S中添加了点，所以U中原来不可达的点也可能能够到达了，或者说有的点能够有更短的到达路径了，所以需要更新。
- 然后一直循环，直到U集合为空，最后S集合中每个点的权值就是该点到起始点的最小路径。
上面的操作都比较简单，除了更新集合权值。我们可以发现所有要更新权值的点其实都是被选中点的直连点，多以对于更新操作，我们只需先获取删除点的直连点，然后一个一个的比较 原来的权值 和 本身到被删除点的权值 + 被删除点的权值，如果本身到被删除点的权值 + 被删除点的权值 小于 原来的权值的话，则更新，否则不用更新。
我自己写的代码如下:
/**
* @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)]
可以看到和我们预想的是一样的。
二、弗洛伊德算法
1 . 佛洛依德(Floyd)算法介绍
和Dijkstra算法一样，Floyd算法也是用于寻找给定的加权图中顶点间的最短路径算法。
Dijkstra算法计算图中一个顶点到其他顶点的最短路径，而Floyd算法计算图中各个顶点之间的最短路径。
2 . 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]);
}
}
}
}
}
没错，就是这么简单。
3 . Floyd算法代码
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));
}
}
}
三、马踏棋盘算法
1 . 马踏棋盘算法介绍
马踏棋盘算法也叫骑士周游问题，讲的是把 马 随机放在 8x8的国际棋盘的某个方格中，马走日字（2x3）进行移动，要求每个棋盘只走一次，走遍棋盘上的全部64个方格。
2 . 马踏棋盘算法思路讲解
我们很容易就能想到用图的深度优先遍历解题。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ggpgz7Ib-1645791772848)(C:\Users\luo’xin\AppData\Roaming\Typora\typora-user-images\image-20220224202846654.png)]
可以看到如果当前位置位（X,Y）的话，下一步能走的地方就是
- （X-2,Y-1）
- （X-1,Y-2）
- （X+1,Y-2）
- （X+2,Y-1）
- （X+2,Y+1）
- （X+1,Y+2）
- （X-1,Y+2）
- （X-2,Y+1）
我们到达一个位置后
- 先把该位置标上对应的步数
- 将对应的位置标记为已访问
- 对其他8个位置进行判断，如果在棋盘内且未访问，则访问（递归）
- 如果8个位置都判断完了，说明无路可走了，此时有两种情况
- 如果步数为棋盘大小，说明全部遍历完了，将标志位finished置为true
- 否则说明未遍历，应该回退。将本格的步数置为0且将对应位置标记为未访问
3 . 马踏棋盘算法代码实现
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));
}
}
}
4 . 马踏棋盘算法效率优化
前面的方式虽然可以达到效果，但是效率非常低。原因是每次递归时都是机械的按照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米，小路的尽头有宝藏，每条小路有宝藏的效率都是一样的，你会怎么么走？很显然了吧，这里也一样，我们要走下一步最少的那个位置。
所以我们就不能像之前一样一个一个的判断遍历了，我们要把所有可能放在一个列表中，然后升序排序。递归式按照从小到大的顺序递归。