使用C++写出A算法

A*算法是一种启发式搜索算法，用于在图形或地图上寻找路径。它使用估价函数（启发式函数）来估计从当前节点到目标节点的最短距离，以帮助选择下一个要扩展的节点。

下面是使用C++实现A*算法的代码：

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <unordered_map>

using namespace std;

//定义节点结构体
struct Node {
    int x, y; //节点位置
    int g, h; //g：从起点到当前节点的距离，h：从当前节点到终点的估价距离
    Node* parent; //指向父节点
    Node(int x, int y, int g, int h, Node* parent = nullptr) {
        this->x = x;
        this->y = y;
        this->g = g;
        this->h = h;
        this->parent = parent;
    }
    int f() const { //计算f值
        return g + h;
    }
};

//定义哈希函数和相等函数
struct NodeHash {
    size_t operator()(const Node* node) const {
        return hash<int>()(node->x) ^ hash<int>()(node->y);
    }
};
struct NodeEqual {
    bool operator()(const Node* n1, const Node* n2) const {
        return n1->x == n2->x && n1->y == n2->y;
    }
};

//定义比较函数
struct NodeCompare {
    bool operator()(const Node* n1, const Node* n2) const {
        return n1->f() > n2->f();
    }
};

//定义A*算法函数
vector<Node*> aStar(Node* start, Node* end, unordered_map<Node*, vector<Node*>>& graph) {
    priority_queue<Node*, vector<Node*>, NodeCompare> openList; //用于存储未扩展的节点
    unordered_map<Node*, int, NodeHash, NodeEqual> gScore; //用于存储从起点到各个节点的距离
    unordered_map<Node*, Node*, NodeHash, NodeEqual> cameFrom; //用于存储每个节点的父节点
    openList.push(start);
    gScore[start] = 0;
    while (!openList.empty()) {
        Node* current = openList.top();
        openList.pop();
        if (current == end) { //找到终点，返回路径
            vector<Node*> path;
            while (current != nullptr) {
                path.push_back(current);
                current = current->parent;
            }
            reverse(path.begin(), path.end());
            return path;
        }
        for (Node* neighbor : graph[current]) { //遍历当前节点的邻居节点
            int tentativeGScore = gScore[current] + 1; //从起点到邻居节点的距离
            if (gScore.find(neighbor) == gScore.end() || tentativeGScore < gScore[neighbor]) {
                //如果该节点没有被访问过或发现更短的路径，则更新节点信息
                gScore[neighbor] = tentativeGScore;
                neighbor->parent = current;
                openList.push(neighbor);
            }
        }
    }
    return vector<Node*>(); //无法到达终点，返回空路径
}

//定义估价函数，这里使用曼哈顿距离
int heuristic(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

int main() {
    int startX = 0, startY = 0;
    int endX = 5, endY = 5;
    unordered_map<Node*, vector<Node*>> graph;
    //定义节点，并构建节点间的连接关系
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            Node* node = new Node(i, j, INT_MAX, heuristic(i, j, endX, endY));
            if (i > 0) graph[node].push_back(new Node(i - 1, j, INT_MAX, heuristic(i - 1, j, endX, endY)));
            if (i < 5) graph[node].push_back(new Node(i + 1, j, INT_MAX, heuristic(i + 1, j, endX, endY)));
            if (j > 0) graph[node].push_back(new Node(i, j - 1, INT_MAX, heuristic(i, j - 1, endX, endY)));
            if (j < 5) graph[node].push_back(new Node(i, j + 1, INT_MAX, heuristic(i, j + 1, endX, endY)));
        }
    }
    Node* start = new Node(startX, startY, 0, heuristic(startX, startY, endX, endY));
    Node* end = new Node(endX, endY, INT_MAX, 0);
    vector<Node*> path = aStar(start, end, graph);
    for (Node* node : path) {
        cout << "(" << node->x << ", " << node->y << ")" << endl;
    }
    return 0;
}

该代码实现了一个6x6的网格地图上的A*算法，起点为(0,0)，终点为(5,5)。使用曼哈顿距离作为估价函数，构建节点间的连接关系，然后调用aStar函数寻找最短路径。最后输出路径上的节点。

需要注意的是，该代码只是一个简单的示例，实际应用中需要根据具体情况进行修改和优化，例如使用更快的哈希函数和相等函数、选择合适的估价函数等。