java - A* 算法更改节点父节点

Question

我对在 A* 算法中更改节点的父节点感到困惑。选择新 parent 似乎有不同的方式:

在这个视频中: https://www.youtube.com/watch?v=KNXfSOx4eEE

它说你应该检查这个:

 G cost currentNode + movement cost from currentNode <= G cost openListNode 

如果是这样，那么我们应该将 openListNode 的父节点替换为当前节点。

但是在这个实现中: http://www.codebytes.in/2015/02/a-shortest-path-finding-algorithm.html

它有以下代码:

static void checkAndUpdateCost(Cell current, Cell t, int cost){
    if(t == null || closed[t.i][t.j])return;
    int t_final_cost = t.heuristicCost+cost;

    boolean inOpen = open.contains(t);
    if(!inOpen || t_final_cost<t.finalCost){
        t.finalCost = t_final_cost;
        t.parent = current;
        if(!inOpen)open.add(t);
    }
}

它检查最终成本是:G + H，这与其他解释相矛盾，因为它应该只是 G 成本，而不是 G 成本和启发式的总和。

谁能给我解释一下，哪个是正确的？实现是否有误？

Answer 1

前线底线 (BLUF):

视频是准确的，但关键是:只有在以下两种情况之一时才应更新节点的父节点:1.) 第一次遇到该节点时，或 2.) 当您找到更高效的节点时先前遇到的节点的路径。此外，在更新节点的父节点时不要使用启发式。

其他详细信息:

下面是一个基于 Wikipedia's Pseudocode 的工作实现;我添加了额外的评论来区分这两种情况。

如果!isOpen && !isClosed是true那么该节点以前从未见过；因此，它的父节点应该设置为当前节点，并且它应该被添加到开放集中。但是如果!isOpen && !isClosed是false , 那么该节点已经在开放集中(即如果 isOpen 为真)或者如果它之前关闭(即如果 isClosed 为真)。因此，我们需要检查当前路径是否比之前导致邻居节点处于开/闭集中的路径更有效——这就是我们检查是否 costFromStart < g_score[neighborNode.x][neighborNode.y] 的原因。

while (!openList.isEmpty()) {
    Pair node = openList.dequeueMin().getValue();

    if (node.equals(goal)) {
        // construct the path from start to goal
        return reconstruct_path(goal);
    }

    for (Pair neighborNode : getNeighbors(node,goal)) {
        if (neighborNode == null) continue;
        boolean isOpen = openSet.contains(neighborNode);
        boolean isClosed = closedSet.contains(neighborNode);
        double costFromStart = g_score[node.x][node.y]+MOVEMENT_COST;

        // check if the neighbor node has not been
        // traversed or if a shorter path to this
        // neighbor node is found.
        if (
            (!isOpen && !isClosed) // first time node has been encountered
                || //or
            costFromStart < g_score[neighborNode.x][neighborNode.y]) //new path is more efficient
        {
            came_from[neighborNode.x][neighborNode.y] = node;
            g_score[neighborNode.x][neighborNode.y] = costFromStart;
            h_score[neighborNode.x][neighborNode.y] =
                    estimateCost(neighborNode,goal);
            if (isClosed) {
                closedSet.remove(neighborNode);
            }
            if (!isOpen) {
                openList.enqueue(neighborNode,costFromStart);
                openSet.add(neighborNode);
            }
        }
    }
    closedSet.add(node);
}