A*搜索算法详解（Java语言实现路径规划与启发式搜索）

Java实现A*算法步骤

我们将用一个二维网格地图来演示 A* 算法。每个格子可以是空地（可通行）或障碍物（不可通行）。

1. 定义节点类 Node

class Node {    int x, y;           // 坐标    double gCost;       // 起点到当前点的实际代价    double hCost;       // 当前点到终点的预估代价    double fCost;       // f = g + h    Node parent;        // 父节点，用于回溯路径    public Node(int x, int y) {        this.x = x;        this.y = y;    }    // 计算 fCost    public void calculateFCost() {        this.fCost = this.gCost + this.hCost;    }    @Override    public boolean equals(Object obj) {        if (this == obj) return true;        if (obj == null || getClass() != obj.getClass()) return false;        Node node = (Node) obj;        return x == node.x && y == node.y;    }}

2. 实现A*核心逻辑

import java.util.*;public class AStar {    private static final int[][] DIRECTIONS = {{0,1},{1,0},{0,-1},{-1,0}}; // 上下左右    public List<Node> findPath(char[][] grid, int startX, int startY, int endX, int endY) {        int rows = grid.length;        int cols = grid[0].length;        // 开放列表（待探索）和关闭列表（已探索）        PriorityQueue<Node> openList = new PriorityQueue<>(            Comparator.comparingDouble(n -> n.fCost)        );        Set<String> closedSet = new HashSet<>();        Node start = new Node(startX, startY);        Node end = new Node(endX, endY);        start.gCost = 0;        start.hCost = heuristic(start, end);        start.calculateFCost();        openList.offer(start);        while (!openList.isEmpty()) {            Node current = openList.poll();            String key = current.x + "," + current.y;            closedSet.add(key);            // 找到终点            if (current.x == endX && current.y == endY) {                return reconstructPath(current);            }            // 探索邻居            for (int[] dir : DIRECTIONS) {                int nx = current.x + dir[0];                int ny = current.y + dir[1];                // 边界检查和障碍物检查                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == '#') {                    continue;                }                String neighborKey = nx + "," + ny;                if (closedSet.contains(neighborKey)) {                    continue;                }                double tentativeG = current.gCost + 1; // 假设每步代价为1                Node neighbor = new Node(nx, ny);                neighbor.gCost = tentativeG;                neighbor.hCost = heuristic(neighbor, end);                neighbor.calculateFCost();                neighbor.parent = current;                openList.removeIf(n -> n.x == nx && n.y == ny && n.fCost <= neighbor.fCost);                openList.offer(neighbor);            }        }        return new ArrayList<>(); // 无路径    }    // 启发函数：曼哈顿距离    private double heuristic(Node a, Node b) {        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);    }    // 回溯路径    private List<Node> reconstructPath(Node node) {        List<Node> path = new ArrayList<>();        while (node != null) {            path.add(node);            node = node.parent;        }        Collections.reverse(path);        return path;    }}

如何使用这个A*算法？

假设你有一个如下地图（'.' 表示空地，'#' 表示障碍物）：

char[][] map = {    {'.', '.', '.', '#', '.'},    {'.', '#', '.', '#', '.'},    {'.', '.', '.', '.', '.'},    {'#', '#', '.', '#', '.'},    {'.', '.', '.', '.', '.'}};

你可以这样调用：

AStar astar = new AStar();List<Node> path = astar.findPath(map, 0, 0, 4, 4);if (!path.isEmpty()) {    System.out.println("找到路径！长度：" + path.size());    for (Node n : path) {        System.out.println("(" + n.x + ", " + n.y + ")");    }} else {    System.out.println("无法到达终点！");}

总结

通过本教程，你已经掌握了使用Java语言实现A*搜索算法的核心思想和代码编写方法。A* 是一种强大的启发式搜索技术，在路径规划算法中具有广泛应用。只要理解了 g(n)、h(n) 和 f(n) 的含义，并合理选择启发函数，你就能在各种场景中高效地找到最优路径。

记住：A* 的性能高度依赖于启发函数的设计。曼哈顿距离适用于只能上下左右移动的网格；如果允许对角线移动，可以考虑切比雪夫距离或欧几里得距离。

希望这篇关于 A*搜索算法 的 Java 教程对你有帮助！动手试试吧，你会发现路径规划其实没那么难！