A*路径规划算法是否保证找到最短路径？

Question

A*路径规划算法是否保证找到最短路径？

4

如果实现正确，A*算法是否保证在所有情况下都能找到最短路径？

int Graph::FindPath(Node *start, Node *finish, list< vec2f > &path)
{
    list<NodeRecord*> open;
    list<NodeRecord*> closed;
    list<NodeRecord*>::iterator openIt;
    list<NodeRecord*>::iterator closedIt;

    // add the starting node to the open list
    open.push_back( new NodeRecord(start, NULL, 0.0f, 0.0f + start->pos.DistanceSq(finish->pos) ) );
  // NodeRecord(Node *node, Node *from, float cost, float totalCost)

    while(!open.empty())
    {
        // find the node record with the lowest cost
        NodeRecord *currentRecord = open.front();
        openIt = ++open.begin();

        while(openIt != open.end())
        {
            if((*openIt)->total < currentRecord->total)
                currentRecord = (*openIt);

            openIt++;
        }

        // get a pointer to the current node
        Node *currentNode = currentRecord->node;

        // if the current node is the finish point
        if(currentNode == finish)
        {
            // add the finish node
            path.push_front(currentNode->pos);

            // add all the from nodes
            Node *from = currentRecord->from;

            while(!closed.empty())
            {
                // if this node record is where the path came from,
                if(closed.back()->node == from) //&& closed.back()->from != NULL
                {
                    // add it to the path
                    path.push_front( from->pos );

                    // get the next 'from' node
                    from = closed.back()->from;
                }

                // delete the node record
                delete closed.back();
                closed.pop_back();
            }

            while(! open.empty() )
            {
                delete open.back();
                open.pop_back();
            }

            // a path was found
            return 0;
        }

        // cycle through all neighbours of the current node

        bool isClosed, isOpen;

        for(int i = 0; i < (int)currentNode->neighbours.size(); i++)
        {
            // check if neigbour is on the closed list
            isClosed = false;
            closedIt = closed.begin();
            while(closedIt != closed.end())
            {
                if(currentNode->neighbours[i] == (*closedIt)->node)
                {
                    isClosed = true;
                    break;
                }

                closedIt++;
            }

            // skip if already on the closed list
            if(isClosed == true)
                continue;

            float cost = currentRecord->cost + currentNode->distance[i];
            float totalCost = cost + currentNode->neighbours[i]->pos.DistanceSq(finish->pos);

            // check if this neighbour is already on the open list
            isOpen = false;
            openIt = open.begin();
            while(openIt != open.end())
            {
                if(currentNode->neighbours[i] == (*openIt)->node)
                {
                    // node was found on the open list
                    if(totalCost < (*openIt)->total)
                    {
                        // node on open list was updated
                        (*openIt)->cost = cost;
                        (*openIt)->total = totalCost;
                        (*openIt)->from = currentNode;
                    }

                    isOpen = true;
                    break;
                }

                openIt++;

            }

            // skip if already on the open list
            if(isOpen == true)
                continue;

            // add to the open list
            open.push_back( new NodeRecord(currentNode->neighbours[i], currentNode, cost, totalCost) );
        }

        // move the current node to the closed list after it has been evaluated
        closed.push_back( currentRecord );
        open.remove( currentRecord );
    }

    // free any nodes left on the closed list
    while(! closed.empty() )
    {
        delete closed.back();
        closed.pop_back();
    }

    // no path was found
    return -1;
}

- CuriousGeorge

3个回答

5

根据维基百科，A*算法使用启发式方法以更快地找到最短路径，但实际上它是Dijkstra最短路径算法的一种改进。如果启发式方法不够好，A*算法实际上与Dijkstra算法没有太大区别。

因此，确保A*算法能够找到最短路径。

- Archie

1

有趣的是，尽管可接受的启发式算法在100%的情况下提供最优解，但在某些情况下它们可能会很慢。如果有几条路径的总距离大致相同，则不可接受的启发式算法将在这些相对等价的路径之间提供更快的“决策”，请注意，为使其起作用，您必须使用一个封闭列表（您已经这样做了）。

事实上，Pearl在他的书《启发式》中证明，如果您的启发式算法高估了一小部分，那么所提供的解决方案只会比最优解多出同样的一小部分（最多）！

对于某些快速/实时应用程序，这可以真正帮助提高速度，代价是解决方案质量稍微降低。

- BenjyCook

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Travis Gockel · Accepted Answer

是的（但我还没有深入研究您的实现）。

大多数人忽略的事情是，启发式算法必须低估到达最终解决方案的遍历成本。同时，启发式算法单调逼近解决方案也很好（但不是绝对必需的）。

无论如何，从我看到你的代码来看，你可能应该使用std::set作为你的封闭列表，使用std::deque作为你的开放列表，这样在这两个列表中进行搜索和插入时就不会是O(n)了。同时，你也不应该使用new NodeRecords，因为它只会增加一个没有好处的间接层（并且如果出现异常，你的算法将泄漏内存）。