c++ - 如何检索 vector 中第一个找到的具有最低值的元素

Question

我已经实现了 A*。但是，当它运行时，当 vector 中的所有节点都具有相同的 f 分数时，它作为 BFS 运行。

There are a number of simple optimizations or implementation details that can significantly affect the performance of an A* implementation. The first detail to note is that the way the priority queue handles ties can have a significant effect on performance in some situations. If ties are broken so the queue behaves in a LIFO manner, A* will behave like depth-first search among equal cost paths (avoiding exploring more than one equally optimal solution)
[Wikipedia- A*]

我想知道是否有一种方法可以修改我现有的程序(提供的代码段)以不仅检索最低元素而且检索第一个最低元素。

void Search::aStar()
{
    searchMethod = "ASTAR";
    generateMap();

    // Draw Window and wall
    guiOpen("VisX", 800, 600);
    guiShowWall();

    std::vector<Node> nodeHistory;
    std::vector<std::reference_wrapper<Node>> openSet;

    // Get starting point, add it to the queue and set as visited
    Coord start = getStartPos();
    Node &root = mapMaze[start.x][start.y];
    openSet.push_back(root);
    root.setVisitFlag(true);

    root.setGScore(0);

    while (!openSet.empty())
    {
        // Put the minimium fscore element to the front 
        auto result =  std::min_element(openSet.begin(), openSet.end(), lowestFScore());
        int minElementPos = std::distance(std::begin(openSet), result);
        std::swap(openSet[minElementPos], openSet.front());

        Node &current = openSet.front();

        // Re-assign pending flag to visited
        current.setPendingVisit(false);
        current.setVisitFlag(true);

        // Update the GUI display
        guiRefresh(current);

        openSet.erase(openSet.begin());

        // Add to list of visited nodes 
        nodeHistory.push_back(current);

        if (current.isFinish())
        {
            std::cout << "[Informed] A*: Found Finish"
                      << "\nNote: Speed of search has been slowed down by GUI display."
                      << std::endl;

            // Construct path & update GUI with path
            constructPath(nodeHistory);
            guiShowConstructedPath();

            guiClose();
            break;
        }

        // Add each valid edges node to the queue
        for (int i = 0; i < EDGE_AMOUNT; i++)
        {
            if (current.isValidEdge(i))
            {
                Node &neighbor = mapMaze[current.getEdge(i).x][current.getEdge(i).y];
                // If not a wall and has been visited, ignore
                if (neighbor.isNotWall() && !(neighbor.isNotVisited())) continue;

                // If not in openset, add it and set flag
                if (neighbor.isNotWall() && neighbor.isNotVisited() && neighbor.isNotPendingVisit())
                {
                    // Add to queue and set flag
                    openSet.push_back(neighbor);
                    neighbor.setPendingVisit(true);

                    // Update the GUI display
                    guiRefresh(neighbor);
                }

                // Calculate gScore, and see if it is better than neigbours current score.
                #define MOVEMENT_COST (1)
                int tentativeGScore = current.getGScore() + MOVEMENT_COST;
                if (tentativeGScore >= neighbor.getGScore()) continue;

                // This path is the best until now. Record it!
                neighbor.setParent(current);
                neighbor.setGScore(tentativeGScore);
                int fScore = neighbor.getGScore() + neighbor.getHScore();
                neighbor.setFScore(fScore);
            }
        }
    }
}
struct lowestFScore
{
    bool operator()(const Node& lhs, const Node& rhs) const
    {
        return lhs.getFScore() < rhs.getFScore();
    }
};

Answer 1

std中有一个priority_queue。

这是一个引用:http://en.cppreference.com/w/cpp/container/priority_queue

不知道是不是你需要的:

#include <queue>
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
pq.push(1);
int min_elem = pq.top(); pq.pop();