A*搜索算法Java实现

前言

本来是想写一块的，但是为了这个国庆的专属勋章就分开写了，这个侧重还是对作业题目要求的实现。

课题目的

理解 A Star 算法设计流程。

理解 A Star 算法的启发式函数的作用。

掌握 A Start 解决搜索问题的过程，能够应用 A Star 算法解决迷宫问题

A Star 算法理论

A Star 搜索是一种重要的启发式搜索算法，它始终从打开的表中选择估计成本最低的节点作为新状态。对于任何状态，其估价函数由下式定义：

f(s)=g(s)+h(s)

g(s)是从起点到当前状态的实际代价，这是一个已知值。以迷宫问题为例，正是从起始状态移动到的步骤数。称为启发式函数，它估计从到目标状态的最优路径的估算代价。设表示从当前状态到目标状态的最优路径（通常事先未知）。如果满足:

我们说是可采纳性（admissible）（即的下界）。然后我们有一个关于 A Start 的重要定理：具有可采纳性启发式的 A Start 搜索可以保证找到搜索问题的最优路径。请注意，对于本实验中的迷宫问题，基于欧几里得或曼哈顿距离的启发式函数是具有可采纳性

欧几里得距离：

欧氏距离定义：欧氏距离（ Euclidean distance）是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。

两点之间线段最短，所以采用欧几里得距离能够保证找到搜索问题的最优路径。

曼哈顿距离：

曼哈顿距离也叫出租车距离，用来标明两个点在标准坐标系上的绝对轴距总和。

因为这个迷宫问题路径的选择只能从上下左右四个方向移动，不能够斜着移动，故而他的最短距离实际上就是当前节点到终点之间x，y差的绝对值的和，也就是曼哈顿距离，所以采用曼哈顿距离能够保证找到搜索问题的最优路径。

实验结果与分析

使用语言：Java

使用文件：smallMaze.txt

使用软件：IDEA

运行结果如下：

1.曼哈顿距离

2.欧几里得距离

命令行运行：

C:\Users\25496\Desktop\artificial intelligence>javac -encoding utf-8 bigMazeSearch.java

C:\Users\25496\Desktop\artificial intelligence>java bigMazeSearch

由于编码问题，需要采用utf-8编码运行。

获取文本数据

因为地图不是自己定义的，是在文本文件里面的，所以需要我们自己进行读取，把数据拿出来放在二维的字符数组里面，同时还是需要标记他的起点和终点。因为都是字符，所以读取一行字符串，把字符放在字符数组里面就行了。

算法实现

A*搜索算法-CSDN博客https://blog.csdn.net/weixin_64066303/article/details/133325621?spm=1001.2014.3001.5501 A*搜索算法(Java实现)_java a*算法-CSDN博客https://blog.csdn.net/Taylar_where/article/details/90298610 人工智能大作业——A*算法迷宫寻路问题_a*算法实现迷宫寻路功能-CSDN博客https://blog.csdn.net/weixin_46037153/article/details/107136560 机器人路径规划算法（十一）A-star算法 - Mronne's Bloghttps://mronne.github.io/2020/04/03/%E6%9C%BA%E5%99%A8%E4%BA%BA%E8%B7%AF%E5%BE%84%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95-%E5%8D%81%E4%B8%80-A-star-%E7%AE%97%E6%B3%95.html A*搜索算法(A-Star Search)简介及保姆级代码解读 (qq.com)https://mp.weixin.qq.com/s?__biz=MzU1NjEwMTY0Mw==&mid=2247554483&idx=1&sn=c3e6a3259f1b469eded07a5498790186&chksm=fbc86cd7ccbfe5c12f4dddf139f73cb5c2879044867bced71edb0243b155f3d68eda50d0db6a&scene=27

//准备两个链表来储存需要选择的节点以及已经走过的节点
public static LinkedList openList = new LinkedList();
public static LinkedList closedList = new LinkedList();
public static HashMap resultMap = new HashMap();

把需要探索的节点放在openList链表里面，把已经探索过的节点放在closedList链表里面，resultMap用来储存当前节点和邻居节点的关系（如果邻居节点满足要求（没有越界，没有已经在openList和closeList里面），就用邻居节点作为键，当前节点作为值，加入到resultMap里面），目的是为了之后能够根据键值对的关系，能够从终点到达起点。

从endGrid表示终点，因为对应关系已经有了，先将当前节点作为键找到他对应的值，表示在迷宫中的含义就是找到他的上一步，更好将他的上一步作为键，找到他的上上步，重复这个过程直到达到起点。

注：只能从终点往起点找，不能从起点往终点找。你只能知道你的上一步在哪里，但是你无法知道你的下一步在哪里。

while (true) {

Grid grid = resultMap.get(endGrid);

endGrid = grid;

if (endGrid == null) {

break;

}

//到达起点

if (endGrid.x == startGrid.x && endGrid.y == startGrid.y) {

// mazeArray[endGrid.x][endGrid.y] = '#';

break;

}

mazeArray[endGrid.x][endGrid.y] = '@';

//最短路径

shortestPath++;

}

//把方格抽象成一个类
public static class Grid {
    private int x;//横坐标
    private int y;//纵坐标
    //fn=hn+gn
    private int fn;//估计函数
    private int hn;//估计代价
    private int gn;//实际代价

    private Grid present;//当前节点
    //构造方法
    public Grid(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
   public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    //实例化一个方格节点
    public void initGrid(Grid present, Grid end) {
        this.present = present;
        //计算gn
        if (present != null) {
            //实际的代价加一相当于前进了一步
            this.gn = present.gn + 1;
        } else {
            this.gn = 1;
        }
        //计算hn的大小(这里用的估计代价是曼哈顿距离
        //this.hn = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
        //欧几里得距离作为启发函数
        this.hn= (int) Math.sqrt(Math.pow(this.x-end.x,2)+Math.pow(this.y-end.y,2));
        //计算fn的大小
        this.fn = this.gn + this.hn;
    }
    public String toString() {
        return "(" + this.x + "," + this.y + ")" + "fn:" + this.fn + " gn:" + this.gn + " hn:" + this.hn;
    }
    @Override
    public int hashCode() {
        int tmp = (this.y + (this.x + 1) / 2);
        return x + (tmp * tmp);
    }
    //重写equals方法，不然比较的是地址值
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Grid other = (Grid) obj;
        if (this.x == other.x && this.y == other.y) {
            return true;
        }
        return false;
    }
}

首先把起点添加到openList链表里面，表示待探索他，之后把他从openList链表中删除，添加到closedList链表里面，表示他已经被探索过了，之后就是寻找他的邻居节点是否有满足要求的，有满足要求的就将所有满足要求的添加到openList里面，这里不用管他的顺序，所以最后拿出来探索的节点是通过方法查找的，探索的是Fn值最小节点的邻居。

整个结束就是到达终点，或者就是没有答案，openList里面没有元素了，也会跳出。

//A*算法的实现(需要开始位置和结束位置

private static void AStarSearch(Grid start, Grid end, char[][] mazeArray) {
    //将起点加入链表之后开始寻路
    openList.add(start);
    //链表不为空（没有最后没有到达终点也会停止）
    while (openList.size() > 0) {
        //找到在需要选择的节点中最小的那个节点，之后需要用它进行扩展
        Grid nowGrid = findMinGrid(openList);
        //从中删除最小的那个节点
        openList.remove(nowGrid);
        //将这个节点添加到已经走过的路径中
        closedList.add(nowGrid);
        //寻找他的相邻节点，把合法的节点都添加进来
        LinkedList neighbors = findNeighbors(nowGrid, openList, closedList, mazeArray);
        for (Grid grid : neighbors) {
            //判断集合中是否添加了grid节点
            if (!openList.contains(grid)) {
                //进行初始化
                grid.initGrid(nowGrid, end);
                //添加到待搜索集合中
                openList.add(grid);
                if (grid != null && nowGrid != null) {
                    //子节点作为键，父节点作为值
                    resultMap.put(grid, nowGrid);
                }
                //System.out.println(grid + " " + resultMap.get(grid));
            }
        }
        //判断是否可以结束
        for (Grid grid : openList) {
            if ((grid.x == end.x) && (grid.y == end.y)) {
                closedList.add(end);
                return;
            }
        }
    }
}

探索相邻的节点（首先判断四个方向的节点是否合法，合法才能添加）

//把所有符合要求的相邻节点都放置到list集合里面里面
private static LinkedList findNeighbors(Grid grid, LinkedList openList, LinkedList closeedList, char[][] mazeArray) {
    LinkedList list = new LinkedList();
    //判断相邻节点的合法性
    if (legitimacy(grid.x, grid.y - 1, openList, closeedList, mazeArray)) {//下(用数组来看的话他就是往上)
        list.add(new Grid(grid.x, grid.y - 1));
    }
    if (legitimacy(grid.x, grid.y + 1, openList, closeedList, mazeArray)) {//上
        list.add(new Grid(grid.x, grid.y + 1));
    }
    if (legitimacy(grid.x - 1, grid.y, openList, closeedList, mazeArray)) {//左
        list.add(new Grid(grid.x - 1, grid.y));
    }
    if (legitimacy(grid.x + 1, grid.y, openList, closeedList, mazeArray)) {//右
        list.add(new Grid(grid.x + 1, grid.y));
    }
    return list;
}

节点是否合法就是是否越界，以及是否已经探索了，如果探索了就不需要再添加了。

//判断当前节点是否合法
private static boolean legitimacy(int x, int y, LinkedList openList, LinkedList closedList, char[][] mazeArray) {
    //判断坐标是否越界
    if (x < 0 || x >= mazeArray.length || y < 0 || y >= mazeArray[0].length) {
        return false;
    }
    //判断当前节点是否是障碍
    if (mazeArray[x][y] == '%') {
        return false;
    }
    //判断当前节点是否被添加
    if (contains(openList, x, y)) {
        return false;
    }
    //判断当前节点是否已经走过了
    if (contains(closedList, x, y)) {
        return false;
    }
    //所以条件都满足，他就是合法的
    return true;
}

区分不同的节点就是看他的x，y坐标是否都一致，如果都相同就是同一个节点。

//判断当前的节点是否已经添加
private static boolean contains(LinkedList grids, int x, int y) {
    for (Grid grid : grids) {
        //坐标在grids集合中有就是已经被添加了
        if ((grid.x == x) && (grid.y == y)) {
            return true;
        }
    }
    return false;
}

因为没有采用优先队列的数据结构，所以需要自己进行查找，调用这个方法可以返回集合中fn最小的节点。

//返回最小的那个节点
private static Grid findMinGrid(LinkedList selectList) {

    Grid tmpgrid = selectList.get(0);
    for (Grid grid : selectList) {
        //更新最小节点
        if (grid.fn < tmpgrid.fn) {
            tmpgrid = grid;
        }
    }
    return tmpgrid;

计算最短路径：用一个变量去累计，从终点到起点这个过程需要的次数。

扩展节点个数：就是closedList链表里面元素的个数。

算法运行时间：在运行算法运行前放一个时间戳，算法运行后放一个时间戳，两者之间的差值就是算法运行时间花费的毫秒值。

得到最短路径

这里主要就是写一个前面没有提到的。

最短路径我在网上没有看到Java的实现，写的都是伪代码，思路都很简单，就是从终点往前面找，一直到起点就行了，不能从起点往终点直接实现。

举一个例子，假设起点在左上方，终点在右下方，前面一直在右上方找，突然发现代价大于走下方的代价，或者是他往右上方找完之后没路了，那他直接就跳到走下方去寻找，最后呈现出来的路径进行从一边直接跳到另一边这种，这显示和实际不符合，所以需要从终点往起点来寻找。

我这里是用HashMap来实现的，用当前的节点作为值，相邻满足要求的节点作为键，之后就只需要从终点一直把值的结果作为键，就可以得到前一步的结果了，这里我之前是用TreeMap但是失败了，非常诡异，他键和值都有，但是用那个键去查找他的值结果是null，很离谱。

完整代码


import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
 
public class bigMazeSearch {
    public static void main(String[] args) throws IOException {
        //定义文本文件的路径
        File file = new File("C:\\Users\\25496\\Desktop\\artificial intelligence\\bigMaze.txt");
        FileReader fileReader = new FileReader(file);
        BufferedReader bufferedReader = new BufferedReader(fileReader);
        //定义字符二维数组的行数和列数
        int rows = 50;
        int cols = 50;
        //创建字符二维数组
        char[][] mazeArray = new char[rows][cols];
        String line;
 
        //记录起点
        Grid startGrid = new Grid(0, 0);
        //记录终点
        Grid endGrid = new Grid(0, 0);
 
        //记录最短路径和扩展路径的步数
        int shortestPath=0;
        int expandingCrackingPath=0;
 
        int row = 0;
        while ((line = bufferedReader.readLine()) != null && row < rows) {//逐行读取内容
            //System.out.println(line);
            for (int col = 0; col < cols && col < line.length(); col++) {
                //把读取的字符储存到字符数组中
                mazeArray[row][col] = line.charAt(col);
                //更新起点
                if (mazeArray[row][col] == 'S') {
                    startGrid.setX(row);
                    startGrid.setY(col);
                } else if (mazeArray[row][col] == 'E') {
                    //更新终点
                    endGrid.setX(row);
                    endGrid.setY(col);
                }
            }
            row++;
        }
        bufferedReader.close();
        fileReader.close();
        //输出二维字符数组的内容
        System.out.println("原始地图是:");
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(mazeArray[i][j] + " ");
            }
            System.out.println();
        }
        //开始时间(获取当前时间戳的毫秒值)
        long startTime=System.currentTimeMillis();
        //调用A*搜索算法
        AStarSearch(startGrid, endGrid, mazeArray);
        //结束时间
        long endTime= System.currentTimeMillis();
        //System.out.println("算法调用");
        //标记路径
        while (true) {
            Grid grid = resultMap.get(endGrid);
            endGrid = grid;
            if (endGrid == null) {
                break;
            }
            //到达起点
            if (endGrid.x == startGrid.x && endGrid.y == startGrid.y) {
                // mazeArray[endGrid.x][endGrid.y] = '#';
                break;
            }
            mazeArray[endGrid.x][endGrid.y] = '@';
            //最短路径
            shortestPath++;
        }
        System.out.println("\n\n路径是:");
        //路径地图是
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cols; j++) {
            	System.out.print(mazeArray[i][j] + " ");  
            }
            System.out.println();
        }
        expandingCrackingPath=closedList.size();
        long timeElapsed=endTime-startTime;
        System.out.println("最短路径是："+shortestPath+"步");
        System.out.println("扩展节点数是："+expandingCrackingPath);
        System.out.println("算法的运行时间是(毫秒)"+timeElapsed);
    }
 
    //把方格抽象成一个类
    public static class Grid {
        private int x;//横坐标
        private int y;//纵坐标
        //fn=hn+gn
        private int fn;//估计函数
        private int hn;//估计代价
        private int gn;//实际代价
 
        private Grid present;//当前节点
 
        //构造方法
        public Grid(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
 
        public int getX() {
            return x;
        }
 
        public void setX(int x) {
            this.x = x;
        }
 
        public int getY() {
            return y;
        }
 
        public void setY(int y) {
            this.y = y;
        }
 
        //实例化一个方格节点
        public void initGrid(Grid present, Grid end) {
            this.present = present;
 
            //计算gn
            if (present != null) {
                //实际的代价加一相当于前进了一步
                this.gn = present.gn + 1;
            } else {
                this.gn = 1;
            }
 
            //计算hn的大小(这里用的估计代价是曼哈顿距离
            this.hn = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
 
            //计算fn的大小
            this.fn = this.gn + this.hn;
        }
 
        public String toString() {
            return "(" + this.x + "," + this.y + ")" + "fn:" + this.fn + " gn:" + this.gn + " hn:" + this.hn;
        }
 
        @Override
        public int hashCode() {
            int tmp = (this.y + (this.x + 1) / 2);
            return x + (tmp * tmp);
        }
 
        //重写equals方法，不然比较的是地址值
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Grid other = (Grid) obj;
            if (this.x == other.x && this.y == other.y) {
                return true;
            }
            return false;
        }
    }
 
    //准备两个链表来储存需要选择的节点以及已经走过的节点
    public static LinkedList openList = new LinkedList();
    public static LinkedList closedList = new LinkedList();
    public static HashMap resultMap = new HashMap();
 
    //A*算法的实现(需要开始位置和结束位置
    private static void AStarSearch(Grid start, Grid end, char[][] mazeArray) {
 
        //将起点加入链表之后开始寻路
        openList.add(start);
 
        //链表不为空（没有最后没有到达终点也会停止）
        while (openList.size() > 0) {
            //找到在需要选择的节点中最小的那个节点，之后需要用它进行扩展
            Grid nowGrid = findMinGrid(openList);
 
            //从中删除最小的那个节点
            openList.remove(nowGrid);
            //将这个节点添加到已经走过的路径中
            closedList.add(nowGrid);
 
            //寻找他的相邻节点，把合法的节点都添加进来
            LinkedList neighbors = findNeighbors(nowGrid, openList, closedList, mazeArray);
 
            for (Grid grid : neighbors) {
                //判断集合中是否添加了grid节点
                if (!openList.contains(grid)) {
                    //进行初始化
                    grid.initGrid(nowGrid, end);
                    //添加到待搜索集合中
                    openList.add(grid);
                    if (grid != null && nowGrid != null) {
                        //子节点作为键，父节点作为值
                        resultMap.put(grid, nowGrid);
                    }
                    //System.out.println(grid + " " + resultMap.get(grid));
 
                }
            }
            //判断是否可以结束
            for (Grid grid : openList) {
                if ((grid.x == end.x) && (grid.y == end.y)) {
                    closedList.add(end);
                    return;
                }
            }
        }
    }
 
    //把所有符合要求的相邻节点都放置到list集合里面里面
    private static LinkedList findNeighbors(Grid grid, LinkedList openList, LinkedList closeedList, char[][] mazeArray) {
        LinkedList list = new LinkedList();
        //判断相邻节点的合法性
        if (legitimacy(grid.x, grid.y - 1, openList, closeedList, mazeArray)) {//下(用数组来看的话他就是往上)
            list.add(new Grid(grid.x, grid.y - 1));
        }
        if (legitimacy(grid.x, grid.y + 1, openList, closeedList, mazeArray)) {//上
            list.add(new Grid(grid.x, grid.y + 1));
        }
        if (legitimacy(grid.x - 1, grid.y, openList, closeedList, mazeArray)) {//左
            list.add(new Grid(grid.x - 1, grid.y));
        }
        if (legitimacy(grid.x + 1, grid.y, openList, closeedList, mazeArray)) {//右
            list.add(new Grid(grid.x + 1, grid.y));
        }
        return list;
    }
 
    //判断当前节点是否合法
    private static boolean legitimacy(int x, int y, LinkedList openList, LinkedList closedList, char[][] mazeArray) {
        //判断坐标是否越界
        if (x < 0 || x >= mazeArray.length || y < 0 || y >= mazeArray[0].length) {
            return false;
        }
        //判断当前节点是否是障碍
        if (mazeArray[x][y] == '%') {
            return false;
        }
        //判断当前节点是否被添加
        if (contains(openList, x, y)) {
            return false;
        }
        //判断当前节点是否已经走过了
        if (contains(closedList, x, y)) {
            return false;
        }
        //所以条件都满足，他就是合法的
        return true;
    }
 
    //判断当前的节点是否已经添加
    private static boolean contains(LinkedList grids, int x, int y) {
        for (Grid grid : grids) {
            //坐标在grids集合中有就是已经被添加了
            if ((grid.x == x) && (grid.y == y)) {
                return true;
            }
        }
        return false;
    }
 
    //返回最小的那个节点
    private static Grid findMinGrid(LinkedList selectList) {
 
        Grid tmpgrid = selectList.get(0);
        for (Grid grid : selectList) {
            //更新最小节点
            if (grid.fn < tmpgrid.fn) {
                tmpgrid = grid;
            }
        }
        return tmpgrid;
    }
}

扩展

用idea还可以通过ANSI转义码来实现的输出不同的颜色，eclipse的话还需要自己安装插件才行，用颜色的好处就很对比更加明显了。（输出不同颜色的大家可以自己去实现）

代码的启发式函数采用的是曼哈顿，欧几里得的话还需要自己去实现哦。（这个最短路径是一样的，但是扩展节点的数量不一样）

总结

本来还想写一起的，但还是分开的，这个思路网上的都是一样的，就是实现不相同。

相关阅读:
王道3.3 栈的应用
 [附源码]计算机毕业设计JAVA新闻发布和评论管理系统
 RabbitMQ--基础--06--界面说明
 php图片素材网毕业设计源码110907
判断回文数
 基于数据驱动的成本洞察，趣丸科技的FinOps进阶之路~
面向对象的首要特征——封装
 预定义ContentProvider
linux基本操作之gvim
【IC刷卡数据专题】IC刷卡数据分析的技术要点
原文地址：https://blog.csdn.net/weixin_64066303/article/details/133493424