A * поиск пути гарантированно найдет кратчайший путь?

Question

Гарантируется ли алгоритм поиска пути 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;
}

Answer 1

Да (но я не очень внимательно изучил вашу реализацию).

Единственное, что упускает большинство людей, - это то, что эвристический алгоритм ДОЛЖЕН недооценивать стоимость обхода окончательного решения.(это называется " допустимый ").Также хорошо (но не обязательно), чтобы эвристика монотонно приближалась к решению (это называется " непротиворечиво ")

---

В любом случае, на мой взгляд на ваш код,вам, вероятно, следует использовать std::set для своего закрытого списка и std::deque для своего открытого, чтобы ваши поиски и вставки в эти два списка не были O (n).Вы также не должны делать new NodeRecords, так как это дает вам уровень косвенности без пользы (и ваш алгоритм будет пропускать память при возникновении исключения).

Answer 2

Согласно Википедии , A * использует эвристику для более быстрого поиска кратчайшего пути, но на самом деле это модификация алгоритма кратчайшего пути Дейкстры, и если эвристика не достаточно хороша, A * делает практически то же самоекак Дейкстра.

Так что да, гарантируется, что A * найдет кратчайший путь.

Answer 3

Интересно, что хотя допустимые эвристики обеспечивают оптимальное решение в 100% случаев, в некоторых ситуациях они могут быть медленными. Если есть несколько путей, которые примерно одинаковы по общему расстоянию, недопустимая эвристика обеспечит более быстрое «принятие решения» между относительно эквивалентными путями. Обратите внимание, что вы должны использовать закрытый список (который вы сделали), чтобы это работало.

Фактически, Перл в своей книге «Эвристика» доказывает, что если ваша эвристика переоценивает небольшую величину, то предоставленное решение будет только дольше, чем оптимальное на ту же величину (максимум)!

Для некоторых приложений, работающих в режиме реального времени / в режиме реального времени, это может быть реальной помощью для повышения скорости при небольших затратах на качество решения.