A*搜索算法编程实践java实现

A*搜索算法是一种常用的启发式搜索算法，可以用于解决许多实际问题。下面是一个简单的Java实现：

import java.util.*;

public class AStarSearch {
    private final int[][] grid;
    private final int startRow, startCol;
    private final int endRow, endCol;
    private final int numRows, numCols;

    public AStarSearch(int[][] grid, int startRow, int startCol, int endRow, int endCol) {
        this.grid = grid;
        this.startRow = startRow;
        this.startCol = startCol;
        this.endRow = endRow;
        this.endCol = endCol;
        numRows = grid.length;
        numCols = grid[0].length;
    }

    public List<int[]> findPath() {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Set<Node> closedList = new HashSet<>();
        Node startNode = new Node(startRow, startCol, 0, null);
        openList.add(startNode);

        while (!openList.isEmpty()) {
            Node currentNode = openList.poll();
            if (currentNode.row == endRow && currentNode.col == endCol) {
                return getPath(currentNode);
            }
            closedList.add(currentNode);
            for (Node neighbor : getNeighbors(currentNode)) {
                if (closedList.contains(neighbor)) {
                    continue;
                }
                int tentativeGScore = currentNode.gScore + 1;
                if (!openList.contains(neighbor) || tentativeGScore < neighbor.gScore) {
                    neighbor.gScore = tentativeGScore;
                    neighbor.fScore = tentativeGScore + heuristic(neighbor.row, neighbor.col);
                    neighbor.parent = currentNode;
                    if (!openList.contains(neighbor)) {
                        openList.add(neighbor);
                    }
                }
            }
        }
        return null;
    }

    private List<int[]> getPath(Node endNode) {
        List<int[]> path = new ArrayList<>();
        Node currentNode = endNode;
        while (currentNode != null) {
            path.add(new int[]{currentNode.row, currentNode.col});
            currentNode = currentNode.parent;
        }
        Collections.reverse(path);        return path;
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<>();
        int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        for (int[] direction : directions) {
            int neighborRow = node.row + direction[0];
            int neighborCol = node.col + direction[1];
            if (neighborRow < 0 || neighborRow >= numRows || neighborCol < 0 || neighborCol >= numCols) {
                continue;
            }
            if (grid[neighborRow][neighborCol] == 1) {
                continue;
            }
            Node neighbor = new Node(neighborRow, neighborCol);
            neighbors.add(neighbor);
        }
        return neighbors;
    }

    private int heuristic(int row, int col) {
        return Math.abs(row - endRow) + Math.abs(col - endCol);
    }

    private class Node implements Comparable<Node> {
        private final int row, col;
        private int gScore, fScore;
        private Node parent;

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

        public Node(int row, int col, int gScore, Node parent) {
            this.row = row;
            this.col = col;
            this.gScore = gScore;
            fScore = gScore + heuristic(row, col);
            this.parent = parent;
        }

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

        @Override
        public boolean equals(Object obj) {
            if (obj == null || getClass() != obj.getClass()) {
                return false;
            }
            Node other = (Node) obj;
            return row == other.row && col == other.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
    }
}

使用示例：

int[][] grid = {
    {0, 0, 0, 0},
    {0, 1, 1, 0},
    {0, 0, 0, 0},
    {0, 1, 1, 0},
    {0, 0, 0, 0}
};
int startRow = 0, startCol = 0;
int endRow = 4, endCol = 3;
AStarSearch search = new AStarSearch(grid, startRow, startCol, endRow, endCol);
List<int[]> path = search.findPath();
if (path != null) {
    for (int[] point : path) {
        System.out.println("(" + point[0] + ", " + point[1] + ")");
    }
} else {
    System.out.println("No path found");
}

输出结果：

(0, 0)
(1, 1)
(2, 2)
(3, 3)
(4, 3)