A*问题及Java代码

A*（A星）是一种基于启发式搜索的算法，用于解决图形路径规划的问题。它在搜索图中尝试找到从起点到目标节点的最短路径。A*算法使用估价函数（heuristic function）来评估路径的优劣。估价函数是一个启发式函数，它会根据当前节点到目标节点的距离估计出从起点到目标节点的最短距离。A* 算法会同时考虑路径长度和估价函数，以找到一条最优路径。

以下是一个简单的 A* 算法的 Java 代码：

import java.util.*;

public class AStarAlgorithm {
    private final List<Node> openList;
    private final List<Node> closedList;
    private final int[][] map;
    private final int startX;
    private final int startY;
    private final int endX;
    private final int endY;
    private final int mapHeight;
    private final int mapWidth;

    public AStarAlgorithm(int[][] map, int startX, int startY, int endX, int endY) {
        this.map = map;
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
        this.mapHeight = map.length;
        this.mapWidth = map[0].length;
        this.openList = new ArrayList<>();
        this.closedList = new ArrayList<>();
    }

    public List<Node> findPath() {
        openList.add(new Node(startX, startY));
        while (!openList.isEmpty()) {
            Node current = getLowestCostNode();
            if (current.getX() == endX && current.getY() == endY) {
                return reconstructPath(current);
            }
            openList.remove(current);
            closedList.add(current);

            for (Node neighbor : getNeighbors(current)) {
                if (closedList.contains(neighbor)) {
                    continue;
                }
                int tentativeGScore = current.getGScore() + getDistanceBetween(current, neighbor);
                if (!openList.contains(neighbor) || tentativeGScore < neighbor.getGScore()) {
                    neighbor.setCameFrom(current);
                    neighbor.setGScore(tentativeGScore);
                    neighbor.setFScore(tentativeGScore + getDistanceBetween(neighbor, new Node(endX, endY)));
                    if (!openList.contains(neighbor)) {
                        openList.add(neighbor);
                    }
                }
            }
        }
        return new ArrayList<>();
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<>();
        int x = node.getX();
        int y = node.getY();

        if (x > 0 && map[x - 1][y] == 0) {
            neighbors.add(new Node(x - 1, y)); // left
        }
        if (x < mapHeight - 1 && map[x + 1][y] == 0) {
            neighbors.add(new Node(x + 1, y)); // right
        }
        if (y > 0 && map[x][y - 1] == 0) {
            neighbors.add(new Node(x, y - 1)); // up
        }
        if (y < mapWidth - 1 && map[x][y + 1] == 0) {
            neighbors.add(new Node(x, y + 1)); // down
        }

        return neighbors;
    }

    private int getDistanceBetween(Node node1, Node node2) {
        return Math.abs(node1.getX() - node2.getX()) + Math.abs(node1.getY() - node2.getY());
    }

    private Node getLowestCostNode() {
        Node lowestCostNode = openList.get(0);
        for (Node node : openList) {
            if (node.getFScore() < lowestCostNode.getFScore()) {
                lowestCostNode = node;
            }
        }
        return lowestCostNode;
    }

    private List<Node> reconstructPath(Node node) {
        List<Node> path = new ArrayList<>();
        path.add(node);
        while (node.getCameFrom() != null) {
            node = node.getCameFrom();
            path.add(0, node);
        }
        return path;
    }
}

class Node {
    private final int x;
    private final int y;
    private Node cameFrom;
    private int gScore;
    private int fScore;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
        this.gScore = Integer.MAX_VALUE;
        this.fScore = Integer.MAX_VALUE;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public Node getCameFrom() {
        return cameFrom;
    }

    public void setCameFrom(Node cameFrom) {
        this.cameFrom = cameFrom;
    }

    public int getGScore() {
        return gScore;
    }

    public void setGScore(int gScore) {
        this.gScore = gScore;
    }

    public int getFScore() {
        return fScore;
    }

    public void setFScore(int fScore) {
        this.fScore = fScore;
    }
}

假设我们的地图是一个二维数组，其中0表示可以通过的区域，1表示障碍物。我们可以通过以下代码来调用A*算法：

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

AStarAlgorithm astar = new AStarAlgorithm(map, 0, 0, 4, 3);
List<Node> path = astar.findPath();

这将在地图上从左上角到右下角寻找一条路径。路径将返回一个包含节点的列表，每个节点表示路径上的一个点。