Java教程

常用的10种算法(8~10)

本文主要是介绍常用的10种算法(8~10),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

常用的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. 两个点之间是直连的
  2. 两个点之间不是直连的,需要通过其他点连接

而初始的矩阵就列举了所有直连顶点之间的距离,当然这个距离未必是最短距离,因为有可能通过通过其他点的距离会比直连点之间的距离更短。

所以我们需要是不是通过直连点之后的距离会比现在的距离更短。通过直连点的个数也有很多可能,我们先考虑一个直连点的情况。我们不妨设这个直连点是 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米,小路的尽头有宝藏,每条小路有宝藏的效率都是一样的,你会怎么么走?很显然了吧,这里也一样,我们要走下一步最少的那个位置。

所以我们就不能像之前一样一个一个的判断遍历了,我们要把所有可能放在一个列表中,然后升序排序。递归式按照从小到大的顺序递归。
这篇关于常用的10种算法(8~10)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!