A*算法通过f(n)=g(n)+h(n)评估函数在c++中实现路径搜索，使用优先队列维护开放列表，结合曼哈顿距离等启发式函数，在二维网格中寻找从起点到终点的最优路径。
A*（A星）寻路算法是一种广泛使用的路径搜索算法，结合了Dijkstra算法的精确性和启发式搜索的高效性。它常用于游戏开发、地图导航等领域。C++实现A*算法的关键在于维护一个开放列表（Open List）和关闭列表（Closed List），通过评估函数 f(n) = g(n) + h(n) 来选择最优路径。
一、A*算法基本原理
A*算法从起点开始，逐步探索周围节点，直到找到目标点。每个节点的评估值由两部分组成：
- g(n)：从起点到当前节点的实际代价
- h(n)：从当前节点到终点的预估代价（启发函数）
- f(n) = g(n) + h(n)：总评估值，决定搜索优先级
常用启发函数包括曼哈顿距离、欧几里得距离等。算法每次从开放列表中取出 f 值最小的节点进行扩展，并将其移入关闭列表，避免重复处理。
二、C++实现步骤
以下是基于二维网格地图的A*算法实现：
立即学习“C++免费学习笔记（深入）”；
#include <iostream> #include <vector> #include <queue> #include <cmath> #include <algorithm> <p>using namespace std;</p> <div class="aritcle_card"> <a class="aritcle_card_img" href="/ai/2128"> <img src="https://img.php.cn/upload/ai_manual/000/000/000/175679969239968.png" alt="算家云"> </a> <div class="aritcle_card_info"> <a href="/ai/2128">算家云</a> <p>高效、便捷的人工智能算力服务平台</p> <div class=""> <img src="/static/images/card_xiazai.png" alt="算家云"> <span>37</span> </div> </div> <a href="/ai/2128" class="aritcle_card_btn"> <span>查看详情</span> <img src="/static/images/cardxiayige-3.png" alt="算家云"> </a> </div> <p>// 网格大小 const int ROW = 5; const int COL = 5;</p><p>// 节点结构 Struct node { int x, y; double g, h, f; Node* parent;</p><pre class='brush:php;toolbar:false;'>Node(int x, int y) : x(x), y(y), g(0), h(0), f(0), parent(nullptr) {}
};
// 比较函数，用于优先队列 struct CompareNode { bool operator()(Node a, Node b) { return a->f > b->f; } };
// 启发函数：曼哈顿距离 double heuristic(int x1, int y1, int x2, int y2) { return abs(x1 – x2) + abs(y1 – y2); }
// 检查是否在地图范围内且可通过 bool isValid(int x, int y, const vector<vector<int>>& grid) { return x >= 0 && x < ROW && y >= 0 && y < COL && grid[x][y] == 0; }
// 打印路径 void printPath(Node* node) { if (node == nullptr) return; printPath(node->parent); cout << “(” << node->x << “,” << node->y <<) “; }
// A* 主算法 void aStar(const vector<vector<int>>& grid, pair<int, int> start, pair<int, int> end) { if (!isValid(start.first, start.second, grid) || !isValid(end.first, end.second, grid)) { cout << “起点或终点无效！n”; return; }
// 方向数组：上下左右 int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; vector<vector<bool>> closed(ROW, vector<bool>(COL, false)); vector<vector<Node*>> nodeMap(ROW, vector<Node*>(COL, nullptr)); // 初始化起点 Node* startNode = new Node(start.first, start.second); startNode->g = 0; startNode->h = heuristic(start.first, start.second, end.first, end.second); startNode->f = startNode->g + startNode->h; priority_queue<Node*, vector<Node*>, CompareNode> openList; openList.push(startNode); nodeMap[start.first][start.second] = startNode; while (!openList.empty()) { Node* current = openList.top(); openList.pop(); int x = current->x; int y = current->y; // 标记为已处理 closed[x][y] = true; // 到达终点 if (x == end.first && y == end.second) { cout << "找到路径："; printPath(current); cout << endl; return; } // 探索邻居 for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (isValid(nx, ny, grid) && !closed[nx][ny]) { double tentativeG = current->g + 1; // 假设移动代价为1 Node* neighbor = nodeMap[nx][ny]; if (neighbor == nullptr) { neighbor = new Node(nx, ny); neighbor->g = tentativeG; neighbor->h = heuristic(nx, ny, end.first, end.second); neighbor->f = neighbor->g + neighbor->h; neighbor->parent = current; nodeMap[nx][ny] = neighbor; openList.push(neighbor); } else if (tentativeG < neighbor->g) { // 发现更短路径，更新 neighbor->g = tentativeG; neighbor->f = neighbor->g + neighbor->h; neighbor->parent = current; // 实际中可能需要重新排序openList，这里简化处理 } } } } cout << "未找到路径！n";
}
三、使用示例
主函数调用示例：
int main() { // 0表示可通过，1表示障碍 vector<vector<int>> grid = { {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 0, 0}, {0, 0, 0, 1, 0} }; <pre class='brush:php;toolbar:false;'>pair<int, int> start = {0, 0}; pair<int, int> end = {4, 4}; aStar(grid, start, end); return 0;
}
四、注意事项与优化建议
- 内存管理：本例未释放动态分配的Node内存，实际项目中应使用智能指针或手动delete
- 性能优化：可用哈希表代替二维nodeMap加速查找；openList可用更高效的堆结构
- 启发函数选择：根据场景选择合适的h(n)，如八方向移动可用对角线距离
- 地图表示：大地图可考虑分块加载或使用稀疏矩阵
基本上就这些。A*算法核心清晰，实现时注意数据结构的选择和边界条件处理即可。