如何检索向量中第一个找到的具有最低值的元素

Question

我已经实现了 A*。但是，当它运行时，当向量中的所有节点都具有相同的 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();

Answer 2

将您的 Node 包装成这样的结构：

struct OpenNode
{
    const Node &node;
    const unsigned int order;
};

并定义你的 openSet 如：

std::vector<OpenNode> openSet;

在 while 循环之前将 unsigned int counter 初始化为 0 并进行以下更改：

// Add before while loop
unsigned int counter = 0;
// ...
Node &current = openSet.front().node;
// ...
openSet.push_back({neighbor, counter++});

最后适应lowestScore:

struct lowestFScore
{
    bool operator()(const OpenNode& lhs, const OpenNode& rhs) const
    {
        auto lScore = lhs.node.getFScore();
        auto rScore = rhs.node.getFScore();
        if (lScore == rScore)
        {
            // Bigger order goes first
            return lhs.order > rhs.order;
        }
        return lScore < rScore;
    }
};

根据建议，您可能希望将 openSet 切换为 std::priority_queue，这样可以更快地检索最少的元素。您应该能够使用相同的比较逻辑。

如何检索向量中第一个找到的具有最低值的元素

How do I retrieve the first found element with the lowest value within a vector

c++

search

vector

a-star