优先级队列c++实现Astar

优先级队列在A*算法（一种启发式搜索算法）中扮演了关键角色，它用于存储待处理的节点，按照每个节点的"f值"（通常是通过路径长度加启发函数估算的目标距离）进行排序。在C++中，我们可以选择多种数据结构来实现优先队列，如`std::priority_queue`或使用自定义的数据结构配合`std::pair`或`std::optional`。

以下是使用`std::priority_queue`和`std::pair`作为结点结构体的一个简单示例：

#include <queue>
#include <functional>

// 定义节点结构体，包含位置(x, y)、已走的距离(g)和目标距离(h)
struct Node {
    int x, y;
    int g, h; // g = 实际步数, h = 启发函数估计值

    std::pair<int, int> getKey() const { return std::make_pair(g + h, y); } // f值排序
};

// 使用优先队列实现A*搜索
void aStarSearch(const std::vector<std::vector<int>>& grid, int start_x, int start_y, int end_x, int end_y) {
    std::priority_queue<Node, std::vector<Node>, decltype(&Node::getKey)> pq;
    pq.push({start_x, start_y, 0, heuristic(start_x, start_y, end_x, end_y)}); // 初始化起始点

    Node current;
    while (!pq.empty()) {
        current = pq.top(); // 取出当前最优节点
        pq.pop();

        // 检查是否到达终点
        if (current.x == end_x && current.y == end_y) {
            break;
        }

        // 探索邻居并更新优先级队列
        for (const auto& neighbor : adjacent(grid, current)) {
            int new_g = current.g + 1; // 计算新节点的g值
            if (pq.contains(neighbor)) {
                if (new_g < pq.top().g) {
                    pq.update(neighbor, std::make_pair(new_g, neighbor.h));
                }
            } else {
                pq.push(neighbor);
            }
        }
    }
}

// 辅助函数：获取相邻节点，可以根据实际地图规则编写
std::vector<Node> adjacent(const std::vector<std::vector<int>>& grid, const Node& node) {
    // ...
}

// 假设heuristic是一个计算启发函数的函数
int heuristic(int x1, int y1, int x2, int y2) {
    // 返回两点间的曼哈顿距离或其他合适的启发函数
    return abs(x1 - x2) + abs(y1 - y2);
}