淮安阿里云代理商：a*算法java源码

下面是使用 Java 实现 A* 算法的示例代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

class Node implements Comparable<Node> {
    private int x;
    private int y;
    private int f; // f(n) = g(n) + h(n)
    private int g; // 到起点的实际代价
    private int h; // 到目标点的估计代价
    private Node parent;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getF() {
        return f;
    }

    public void setF(int f) {
        this.f = f;
    }

    public int getG() {
        return g;
    }

    public void setG(int g) {
        this.g = g;
    }

    public int getH() {
        return h;
    }

    public void setH(int h) {
        this.h = h;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.f, other.f);
    }
}

public class AStarAlgorithm {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int[][] grid;
    private int numRows;
    private int numCols;
    private Node startNode;
    private Node endNode;

    public AStarAlgorithm(int[][] grid) {
        this.grid = grid;
        this.numRows = grid.length;
        this.numCols = grid[0].length;
    }

    public List<Node> findPath(int startX, int startY, int endX, int endY) {
        startNode = new Node(startX, startY);
        endNode = new Node(endX, endY);

        PriorityQueue<Node> openSet = new PriorityQueue<>();
        Set<Node> closedSet = new HashSet<>();

        startNode.setG(0);
        startNode.setH(manhattanDistance(startNode, endNode));
        startNode.setF(startNode.getG() + startNode.getH());

        openSet.add(startNode);

        while (!openSet.isEmpty()) {
            Node currNode = openSet.poll();

            if (currNode.equals(endNode)) {
                return reconstructPath(currNode);
            }

            closedSet.add(currNode);

            for (int[] direction : DIRECTIONS) {
                int newX = currNode.getX() + direction[0];
                int newY = currNode.getY() + direction[1];

                if (isValid(newX, newY) && !closedSet.contains(new Node(newX, newY))) {
                    Node neighbor = new Node(newX, newY);

                    int tentativeG = currNode.getG() + 1;

                    if (!openSet.contains(neighbor) || tentativeG < neighbor.getG()) {
                        neighbor.setParent(currNode);
                        neighbor.setG(tentativeG);
                        neighbor.setH(manhattanDistance(neighbor, endNode));
                        neighbor.setF(neighbor.getG() + neighbor.getH());

                        if (!openSet.contains(neighbor)) {
                            openSet.add(neighbor);
                        }
                    }
                }
            }
        }

        return null;
    }

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

    private boolean isValid(int x, int y) {
        return x >= 0 && x < numRows && y >= 0 && y < numCols && grid[x][y] != 1;
    }

    private List<Node> reconstructPath(Node node) {
        List<Node> path = new ArrayList<>();

        while (node != null) {
            path.add(node);
            node = node.getParent();
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 0, 1, 0},
            {1, 1, 0, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };

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

        if (path != null) {
            for (Node node : path) {
                System.out.println("(" + node.getX() + ", " + node.getY() + ")");
            }
        } else {
            System.out.println("No path found!");
        }
    }
}

这个示例代码使用 A* 算法实现了从起点到终点的路径搜索。在 findPath 方法中，使用优先队列 openSet 存储待探索的节点，使用集合 closedSet 存储已经探索过的节点。通过计算节点的 f(n) 值（f(n) = g(n) + h(n)）来评估节点的优先级，优先探索具有较小 f(n) 值的节点。

注意：此示例代码中的 grid 是一个二维数组，其中 0 表示可以通过的路径，1 表示障碍物。将起点和终点的坐标传递给 findPath 方法，将返回路径上的所有节点。如果找不到路径，返回 null。

请注意，这只是 A* 算法的一种实现方式，还有其他的实现方式可供选择。

下面是一个使用A*算法的Java源码示例：

import java.util.*;

class Node implements Comparable<Node> {
    int x, y; // 节点的坐标
    int g, h; // g值为起点到当前节点的实际距离，h值为当前节点到终点的估计距离
    Node parent; // 父节点

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int f() {
        return g + h;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.f(), o.f());
    }
}

class AStar {
    private int[][] grid;
    private int rows, cols;
    private Node startNode, endNode;

    public AStar(int[][] grid, int rows, int cols, int startX, int startY, int endX, int endY) {
        this.grid = grid;
        this.rows = rows;
        this.cols = cols;
        startNode = new Node(startX, startY);
        endNode = new Node(endX, endY);
    }

    public List<Node> findPath() {
        List<Node> openSet = new ArrayList<>();
        Set<Node> closedSet = new HashSet<>();
        openSet.add(startNode);

        while (!openSet.isEmpty()) {
            Node currentNode = openSet.get(0);

            // 寻找f值最小的节点
            for (int i = 1; i < openSet.size(); i++) {
                if (openSet.get(i).f() < currentNode.f()) {
                    currentNode = openSet.get(i);
                }
            }

            openSet.remove(currentNode);
            closedSet.add(currentNode);

            if (currentNode.x == endNode.x && currentNode.y == endNode.y) {
                return buildPath(currentNode);
            }

            List<Node> neighbors = getNeighbors(currentNode);

            for (Node neighbor : neighbors) {
                if (closedSet.contains(neighbor)) {
                    continue;
                }

                int newG = currentNode.g + 1;
                boolean isOpenSetContainsNeighbor = openSet.contains(neighbor);

                if (!isOpenSetContainsNeighbor || newG < neighbor.g) {
                    neighbor.g = newG;
                    neighbor.h = manhattanDistance(neighbor, endNode);
                    neighbor.parent = currentNode;

                    if (!isOpenSetContainsNeighbor) {
                        openSet.add(neighbor);
                    }
                }
            }
        }

        return null;
    }

    private int manhattanDistance(Node node1, Node node2) {
        return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);
    }

    private boolean isValidPosition(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0;
    }

    private List<Node> getNeighbors(Node node) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        List<Node> neighbors = new ArrayList<>();

        for (int i = 0; i < 4; i++) {
            int newX = node.x + dx[i];
            int newY = node.y + dy[i];

            if (isValidPosition(newX, newY)) {
                neighbors.add(new Node(newX, newY));
            }
        }

        return neighbors;
    }

    private List<Node> buildPath(Node endNode) {
        List<Node> path = new ArrayList<>();
        Node currentNode = endNode;

        while (currentNode != null) {
            path.add(0, currentNode);
            currentNode = currentNode.parent;
        }

        return path;
    }
}

public class Main {
    public static void main(String[] args) {
        int rows = 5;
        int cols = 5;
        int[][] grid = {
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 1},
            {0, 0, 0, 0, 0}
        };

        int startX = 0;
        int startY = 0;
        int endX = 4;
        int endY = 4;

        AStar aStar = new AStar(grid, rows, cols, startX, startY, endX, endY);
        List<Node> path = aStar.findPath();

        if (path != null) {
            for (Node node : path) {
                System.out.println("(" + node.x + ", " + node.y + ")");
            }
        } else {
            System.out.println("No path found.");
        }
    }
}

这个示例代码实现了一个迷宫路径查找的问题。grid数组表示迷宫地图，0表示可以通过的通路，1表示障碍物。startX和startY是起点的坐标，endX和endY是终点的坐标。程序会使用A*算法查找从起点到终点的最短路径，并将路径上的节点打印出来。如果没有找到路径，输出”No path found.”。