Java编程实现A*算法完整代码

下面我将为您详细讲解如何实现A*算法的完整代码：

A*算法简介

A算法，也称A星算法，是一种常用于寻路问题的启发式算法。它利用启发式的方式，在搜索时跳过无关的节点，从而提高了搜索效率。A算法基于广度优先搜索和最短路径算法，可以找到一条从起点到目标节点的最佳路径。

A*算法实现步骤

A*算法的实现步骤主要包含以下几个部分：

定义一个节点类（包含节点坐标、节点的父节点、起始节点到该节点的路径长度、起始节点到该节点的估价函数等属性）；
定义一个openList和一个closeList，分别用于记录还未被扩展的节点和已经被扩展的节点；
将起点加入openList中；
重复如下操作：

a. 从openList中选取F值最小的节点进行扩展，如果该节点是目标节点，搜索结束；

b. 将该节点从openList中移到closeList中，表示该节点已经被扩展；

c. 对于该节点的所有邻居节点，计算起始节点到该邻居节点的路径长度G和该邻居节点到目标节点的估价函数H，然后计算F = G + H。如果该邻居节点不在openList或closeList中，将其加入openList中，并把该节点作为邻居节点的父节点；如果该邻居节点已经在openList中并且新的F值比之前计算的F值小，更新该邻居节点的F值与父节点。

如果openList为空，表示搜索失败。

A*算法完整代码

下面是使用Java语言实现A*算法的完整代码：

import java.util.ArrayList;
import java.util.List;

public class AStar {
    private static final int INF = Integer.MAX_VALUE;
    private int map[][];
    private int n; // 地图大小
    private boolean[][] closed; // 是否已经走过标志
    private List<Node> openList = new ArrayList<Node>(); // 可行的方格
    private Node[][] nodeMap; // 节点地图
    private Node startNode; // 起点
    private Node endNode; // 终点
    private int[] dx = new int[]{0, 1, 0, -1};
    private int[] dy = new int[]{1, 0, -1, 0};

    public AStar(int[][] map) {
        this.map = map;
        n = map.length;
        closed = new boolean[n][n];
        nodeMap = new Node[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                nodeMap[i][j] = new Node(i + 1, j + 1);
    }

    public List<Node> search(Node start, Node end) {
        startNode = start;
        endNode = end;
        startNode.setG(0);
        startNode.setF(startNode.getH(endNode));
        addOpenList(startNode);
        while (openList.size() > 0) {
            Node node = (Node) openList.get(0);
            if (node.equals(endNode)) {
                return getPath(node);
            }
            openList.remove(node);
            addClosed(node);
            for (int i = 0; i < 4; i++) {
                int x = node.getX() + dx[i];
                int y = node.getY() + dy[i];
                if (!isValid(x, y) || isWall(x, y)) {
                    continue;
                }
                Node neighbor = nodeMap[x - 1][y - 1];
                if (isClosed(neighbor)) {
                    continue;
                }
                int g = node.getG() + 1;
                if (!isOpen(neighbor)) {
                    neighbor.setG(g);
                    neighbor.setH(neighbor.getH(endNode) + g);
                    neighbor.setF(neighbor.getG() + neighbor.getH());
                    neighbor.setParent(node);
                    addOpenList(neighbor);
                } else if (g < neighbor.getG()) {
                    neighbor.setG(g);
                    neighbor.setH(neighbor.getH(endNode) + g);
                    neighbor.setF(neighbor.getG() + neighbor.getH());
                    neighbor.setParent(node);
                    adjustOpenList(neighbor);
                }
            }
        }

        return null;
    }

    private List<Node> getPath(Node node) {
        List<Node> path = new ArrayList<Node>();
        while (node.getParent() != null) {
            path.add(0, node);
            node = node.getParent();
        }
        path.add(0, startNode);

        return path;
    }

    private boolean isWall(int x, int y) {
        return map[x - 1][y - 1] == 1;
    }

    private boolean isValid(int x, int y) {
        return x > 0 && x <= n && y > 0 && y <= n;
    }

    private boolean isOpen(Node node) {
        return node.getState() == Node.IN_OPEN;
    }

    private boolean isClosed(Node node) {
        return closed[node.getX() - 1][node.getY() - 1];
    }

    private void addClosed(Node node) {
        closed[node.getX() - 1][node.getY() - 1] = true;
    }

    private void addOpenList(Node node) {
        node.setState(Node.IN_OPEN);
        int i = 0;
        for (; i < openList.size(); i++) {
            if (node.getF() < ((Node) openList.get(i)).getF()) {
                break;
            }
        }
        openList.add(i, node);
    }

    private void adjustOpenList(Node node) {
        int index = openList.indexOf(node);
        openList.remove(index);
        addOpenList(node);
    }
}

其中，Node类为节点类，表示一个地图上的节点信息，包括节点坐标、节点的父节点、起始节点到该节点的路径长度、起始节点到该节点的估价函数等属性。

示例代码：

int map[][] = {
    {0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 1, 0},
    {1, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 1, 1}
};

AStar aStar = new AStar(map);
Node start = new Node(1, 1);
Node end = new Node(6, 6);
List<Node> path = aStar.search(start, end);
System.out.println(path);

输出结果为：

[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]

另一个示例，地图如下所示：

其中，0表示空地，1表示障碍物。

int map[][] = {
    {0, 0, 0, 0, 0},
    {1, 1, 0, 1, 1},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0},
};

AStar aStar = new AStar(map);
Node start = new Node(1, 1);
Node end = new Node(5, 5);
List<Node> path = aStar.search(start, end);
System.out.println(path);

输出结果为：

null

因为起点和终点之间没有可行路径。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java编程实现A*算法完整代码 - Python技术站

Java编程实现A*算法完整代码

A*算法简介

A*算法实现步骤

A*算法完整代码

相关文章