用Java实现膨胀启发式A*算法

膨胀启发式A*算法是一种基于A*算法的改进算法，它通过膨胀操作来减小搜索空间，从而提高搜索效率。下面是用Java实现膨胀启发式A*算法的代码：

public class InflatedAStar {
    private PriorityQueue<Node> openList;
    private HashSet<Node> closedList;
    private int[][] map;  //地图
    private int startRow, startCol;
    private int endRow, endCol;
    private int rows, cols;
    private int inflationRadius;  //膨胀半径

    public InflatedAStar(int[][] map, int startRow, int startCol, int endRow, int endCol, int inflationRadius) {
        this.map = map;
        this.startRow = startRow;
        this.startCol = startCol;
        this.endRow = endRow;
        this.endCol = endCol;
        this.rows = map.length;
        this.cols = map[0].length;
        this.inflationRadius = inflationRadius;
        openList = new PriorityQueue<>(new NodeComparator());
        closedList = new HashSet<>();
    }

    public List<Node> findPath() {
        Node startNode = new Node(startRow, startCol, 0, getHeuristic(startRow, startCol));
        openList.offer(startNode);
        while (!openList.isEmpty()) {
            Node currNode = openList.poll();
            if (currNode.row == endRow && currNode.col == endCol) {
                return getPath(currNode);
            }
            closedList.add(currNode);
            for (Node neighbor : getNeighbors(currNode)) {
                if (closedList.contains(neighbor)) {
                    continue;
                }
                int newG = currNode.g + getCost(currNode, neighbor);
                if (!openList.contains(neighbor) || newG < neighbor.g) {
                    neighbor.g = newG;
                    neighbor.h = getHeuristic(neighbor.row, neighbor.col);
                    neighbor.f = neighbor.g + neighbor.h;
                    neighbor.parent = currNode;
                    if (!openList.contains(neighbor)) {
                        openList.offer(neighbor);
                    }
                }
            }
        }
        return null;
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<>();
        int row = node.row;
        int col = node.col;
        for (int i = row - 1; i <= row + 1; i++) {
            for (int j = col - 1; j <= col + 1; j++) {
                if (i < 0 || i >= rows || j < 0 || j >= cols || (i == row && j == col)) {
                    continue;
                }
                if (isObstacle(i, j)) {
                    continue;
                }
                Node neighbor = new Node(i, j);
                int cost = getCost(node, neighbor);
                int inflatedCost = inflateCost(cost, node, neighbor);
                neighbor.g = node.g + inflatedCost;
                neighbors.add(neighbor);
            }
        }
        return neighbors;
    }

    private int getCost(Node a, Node b) {
        if (a.row == b.row || a.col == b.col) {
            return 1;
        }
        return 2;
    }

    private boolean isObstacle(int row, int col) {
        return map[row][col] == 1;
    }

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

    private int inflateCost(int cost, Node a, Node b) {
        int dx = Math.abs(a.row - b.row);
        int dy = Math.abs(a.col - b.col);
        int diagonalSteps = Math.min(dx, dy);
        int straightSteps = Math.abs(dx - dy);
        int steps = diagonalSteps * 14 + straightSteps * 10;
        if (cost == 1) {  //直线路径
            if (steps <= inflationRadius) {
                return cost + 1;
            }
        } else {  //斜线路径
            int inflatedSteps = 0;
            int remainder = steps;
            while (remainder > 0) {
                if (inflatedSteps % 2 == 0) {  //膨胀
                    remainder -= Math.min(remainder, inflationRadius);
                } else {  //不膨胀
                    remainder -= Math.min(remainder, cost);
                }
                inflatedSteps++;
            }
            if (inflatedSteps % 2 == 0) {  //最后一步膨胀
                return cost + 1;
            }
        }
        return cost;
    }

    private List<Node> getPath(Node node) {
        List<Node> path = new ArrayList<>();
        while (node != null) {
            path.add(node);
            node = node.parent;
        }
        Collections.reverse(path);
        return path;
    }

    private class Node {
        int row;
        int col;
        int g;
        int h;
        int f;
        Node parent;

        Node(int row, int col) {
            this.row = row;
            this.col = col;
            this.g = Integer.MAX_VALUE;
            this.h = Integer.MAX_VALUE;
            this.f = Integer.MAX_VALUE;
            this.parent = null;
        }

        Node(int row, int col, int g, int h) {
            this.row = row;
            this.col = col;
            this.g = g;
            this.h = h;
            this.f = g + h;
            this.parent = null;
        }
    }

    private class NodeComparator implements Comparator<Node> {
        @Override
        public int compare(Node n1, Node n2) {
            return n1.f - n2.f;
        }
    }
}

在这个实现中，我们定义了一个Node类来表示搜索中的节点，每个节点包含其在地图上的位置、从起点到该节点的实际代价g、从该节点到终点的估计代价h、总代价f，以及该节点的父节点。我们使用Java内置的优先队列来实现搜索队列，使用HashSet来记录已经搜索过的节点。

在findPath方法中，我们首先将起点加入到openList中，然后重复以下步骤直到openList为空或者找到终点为止：

1. 取出openList中f值最小的节点currNode。

2. 如果currNode是终点，返回从起点到终点的路径。

3. 将currNode加入到closedList中。

4. 对currNode的所有邻居节点进行处理，对于每个邻居节点neighbor，如果neighbor不在closedList中，计算从起点到neighbor的实际代价newG和从neighbor到终点的估计代价newH，如果openList中不包含neighbor或者newG比neighbor的g值更小，更新neighbor的g、h、f值和父节点为currNode，将neighbor加入到openList中。

在getNeighbors方法中，我们先获取当前节点的所有邻居节点，然后对于每个邻居节点，计算从当前节点到邻居节点的代价cost和经过膨胀后的代价inflatedCost，将邻居节点的实际代价g设置为当前节点的实际代价g加上经过膨胀后的代价inflatedCost，然后将邻居节点加入到列表中。

在inflateCost方法中，我们根据从a到b的步数steps，计算出经过膨胀后的步数inflatedSteps，然后根据inflatedSteps和cost来判断是否需要膨胀。如果是直线路径且inflatedSteps小于等于膨胀半径，则返回原始代价cost加1；如果是斜线路径，我们需要分别计算每一步经过膨胀和不经过膨胀的代价，直到到达目标节点。最后根据最后一步是否膨胀来判断整条路径的代价。

最后，在getPath方法中，我们从终点开始沿着每个节点的父节点一直走到起点，记录下这些节点，然后将节点列表翻转得到从起点到终点的路径。

使用该算法需要传入地图、起点、终点和膨胀半径，可以通过调用findPath方法来获得从起点到终点的路径。