如果 A* 寻路算法实现正确，它是否能 100% 保证找到最短路径？

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;}

回答：

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

大多数人忽略的一点是，启发式算法必须低估到达最终解决方案的遍历成本（这被称为“可采纳性”）。 启发式算法单调地接近解决方案也很好（但不是绝对必需的）（这被称为“一致性”）。

无论如何，粗略地看了一下你的代码，你可能应该使用std::set作为你的 closed list，使用 std::deque 作为你的 open list，这样你在这两个列表中的搜索和插入就不会是 O(n)。 你也不应该 new NodeRecords，因为它给你带来了一个间接级别，没有任何好处（如果抛出异常，你的算法会泄漏内存）。