LeetCode 1091 二进制矩阵最短路径启发式算法错误排查求助

你当前实现的是贪心最佳优先搜索，不是可保证最短路径的A*算法，且存在多处逻辑错误，具体问题如下：

• 优先级计算逻辑错误：A*算法的优先级应该是f(n) = g(n) + h(n)，其中g(n)是起点到当前节点的已走步数，h(n)是启发值，你只使用了h(n)排序，且比较器逻辑写反，Java的PriorityQueue为小顶堆，你当前的写法会优先取出启发值更大的节点，完全背离了启发搜索的设计目标。
• 路径长度计数错误：你使用全局变量output计数，每弹出一个节点就加1，而优先队列中会同时存在不同路径长度的节点，全局计数无法对应当前节点的实际路径长度，需要把g(n)（当前步数）作为Node的属性存储。
• 已访问标记时机错误：你在节点出队时才标记为已访问，会导致同一个节点被多次加入队列，正确的做法是节点入队时就标记已访问。
• 队列存在性判断失效：Node类没有重写equals()和hashCode()方法，pqueue.contains(successor_point)判断的是对象引用是否相同，而非坐标是否相同，该判断完全无效。
• 启发函数选择可优化：8方向移动的场景下，更适合用切比雪夫距离作为启发函数，比欧氏距离计算更快，且满足可采纳性。

修正后代码 #

Node类 #

public class Node {
    public int x;
    public int y;
    public int g; // 起点到当前节点的已走步数
    public double f; // f = g + h 优先级排序依据

    public Node(int x, int y, int g, double h) {
        this.x = x;
        this.y = y;
        this.g = g;
        this.f = g + h;
    }
}

Solution类 #

class Solution {
    // 8方向移动数组
    private final int[][] directions = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        // 起点或终点阻塞直接返回-1
        if(grid[0][0] == 1 || grid[n-1][n-1] == 1) {
            return -1;
        }
        if(n == 1) {
            return 1;
        }
        // 优先队列按f值升序排列
        PriorityQueue<Node> pqueue = new PriorityQueue<>((a, b) -> Double.compare(a.f, b.f));
        // 起点初始化，g=1（路径长度包含起点）
        double startH = chebyshevDistance(0,0,n-1,n-1);
        pqueue.add(new Node(0,0,1, startH));
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

        while(!pqueue.isEmpty()) {
            Node curr = pqueue.poll();
            int x = curr.x;
            int y = curr.y;
            // 到达终点直接返回当前步数
            if(x == n-1 && y == n-1) {
                return curr.g;
            }
            // 遍历8个方向
            for(int[] dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                // 边界、阻塞、已访问校验
                if(nx <0 || nx >=n || ny <0 || ny >=n || grid[nx][ny] == 1 || visited[nx][ny]) {
                    continue;
                }
                // 到达终点直接返回
                if(nx == n-1 && ny == n-1) {
                    return curr.g + 1;
                }
                // 标记已访问并入队
                visited[nx][ny] = true;
                double h = chebyshevDistance(nx, ny, n-1, n-1);
                pqueue.add(new Node(nx, ny, curr.g + 1, h));
            }
        }
        // 无可达路径
        return -1;
    }

    // 切比雪夫距离，适合8方向移动场景
    private double chebyshevDistance(int x, int y, int tx, int ty) {
        return Math.max(Math.abs(tx - x), Math.abs(ty - y));
    }
}

测试用例验证 #

针对你给出的输入[[0,0,0],[1,1,0],[1,1,0]]，修正后的代码会按照正确的优先级搜索，找到路径(0,0)→(0,1)→(0,2)→(1,2)→(2,2)，总长度为4，符合预期输出。

内容的提问来源于stack exchange，提问作者Zuocheng Wang