A*算法改变节点parent

Question

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

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

它说你应该检查这个：

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

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

但在这个实现中： 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 为真).因此，我们需要检查当前路径是否比之前导致邻居节点位于 open/closed 集合中的路径更有效——这就是我们检查是否 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);
}

A*算法改变节点parent

A* algorithm change node parent

java

algorithm

implementation

a-star