c – A *寻路保证找到最短路径？

概述如果正确实施,A *路径查找算法是否可以保证找到100％的最短路径或时间？ int Graph::FindPath(Node *start, Node *finish, list< vec2f > &path){ list<NodeRecord*> open; list<NodeRecord*> closed; list<NodeRecord*>::iterator op 如果正确实施,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;}

解决方法 Yes(但我没有深入研究你的实施).

大多数人都想念的是启发式算法必须低估最终解决方案的遍历成本(这称为“admissible”).启发式单调处理解决方案也很好(但并非绝对必要)(这称为“consistent”)

无论如何,在我看一下你的代码时,你可能应该使用std :: set作为你的封闭列表,使用std :: deque作为你的开放代码,这样你在这两个列表中的搜索和插入就不是O(n).您也不应该创建新的NodeRecords,因为它为您提供了一个没有任何好处的间接级别(如果抛出异常,您的算法将泄漏内存).

总结

以上是内存溢出为你收集整理的c – A *寻路保证找到最短路径？全部内容，希望文章能够帮你解决c – A *寻路保证找到最短路径？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。