c++ - 为什么我的A *搜索算法实现无法正常工作？

Question

我试图找到从N*N网格的左上角到右下角的最短路径。我已经为此编写了广度优先的搜索解决方案，但是我想知道是否可以通过使用A *搜索算法来改善算法的运行时间。
我的A *搜索算法代码如下:

int H(int item, int end, int N){ // heuristic function: euclidean distance from item to exit
    return ((item/N-end/N)*(item/N-end/N) + (item%N-end%N)*(item%N-end%N));
}

int Astar(int start, int end, const vector <vector<int>> &adj, int N){
    vector <bool> visited(adj.size(), false);
    vector <int> dist(adj.size(), INF);
    priority_queue <pi, vector<pi>, greater<pi>> Q;

    Q.push({0, start});
    dist[0] = 0;

    while(!Q.empty()){
        int curr = Q.top().second;
        Q.pop();

        if(visited[curr]){continue;}
        visited[curr] = true;

        if(curr == end){break;}

        for(int item : adj[curr]){
            if(dist[curr] + 1 < dist[item]){
                dist[item] = dist[curr] + 1;
                Q.push({dist[item] + H(item), item});
            }
        }
    }

    print(visited, N);

    return dist[end];
}

但是，我的实现似乎无效。我很困惑，因为A *搜索算法被描述为与Dijkstra的算法几乎完全相同，只是在优先级队列中添加了启发式功能。这是我的上述实现找不到最短路径的情况:

S.........
..........
..........
...#######
...#......
..##.###..
.....#.#..
..####....
.....#....
..####..#E

# are obstacles
S is the start and E is the end
Can move up, down, left, or right only

The answer should be 22 but my function returns 24

请注意，在我的代码中，我通过将每个(x，y)坐标映射到(x * N + y)来将每个正方形表示为单个整数，而不是一对整数，其中N是网格的高度和宽度。
所以，我的问题是，我是否误解了代码中的A *搜索算法？有人可以告诉我如何更改代码，以便产生正确的输出吗？

Answer 1

您的实现不起作用，因为您的试探法与您拥有的移动选项不匹配。具体来说，您的试探法是欧几里德距离试探法，而移动仅限于上，下，左和右。
换句话说，您的试探法是可以接受的，但并不一致。这意味着它不能保证目的地的首次访问会返回最佳路径。为了保证这一点，您需要一致的启发式方法，例如“曼哈顿距离”。
Wikipedia Admissible Heuristics
Wikipedia Consistent Heuristics
上面两篇文章的主要结论是，您的启发式方法应该(A)是可接受的，或者总是低估实际成本(您的欧几里得距离启发式方法确实如此)，并且(B)是一致的，这意味着其估计值始终<=(到邻近顶点的估计距离+到达该顶点的成本)。欧几里得距离启发式不满足(B)。曼哈顿距离(在没有障碍的情况下，仅向上，向下，向左和向右的最小可能到达目标的方式)完全符合这两个要求。