A * алгоритм изменения родительского узла

java algorithm implementation a-star

245 просмотра

1 ответ

Я запутался в изменении родителя узла в алгоритме A *. Кажется, есть разные способы выбора нового родителя:

В этом видео: 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 и эвристика.

Может кто-нибудь объяснить мне, какой из них является правильным?, Реализация не так?

Автор: FraK Источник Размещён: 08.11.2019 11:23

Ответы (1)


1 плюс

Решение

Bottom Line Up Front (BLUF):

Видео является точным, но вот ключ: родитель узла должен обновляться только в одном из следующих двух случаев: 1.) при первом обнаружении узла или 2.) когда вы находите более эффективный путь к узел, который был ранее встречен. Также не используйте эвристику при обновлении родительского узла.

Дополнительные детали:

Ниже приведена рабочая реализация, основанная на псевдокоде Википедии ; Я добавил дополнительные комментарии, чтобы разграничить два случая.

Если !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);
}
Автор: Austin D Размещён: 21.08.2016 09:50
Вопросы из категории :
32x32