A*算法实现原理以及实现步骤（C++）

算法原理：

 A*算法是一种启发式搜索算法，用于在图中寻找最短路径。它结合了Dijkstra算法的确保最短路径的优点和贪心最佳优先搜索的高效性。其核心在于使用一个评估函数：

f(n) = g(n) + h(n)

其中：

- g(n) 表示从起点到节点n的实际代价。

- h(n) 表示从节点n到目标节点的估计代价（启发式函数）。

1. 启发式函数h(n)：必须满足可采纳性（即永远不会高估实际代价）以保证找到最短路径。常见的启发式函数有曼哈顿距离（适用于网格中只能上下左右移动）和欧几里得距离。

2. 开放列表（Open List）：存储待考察的节点，通常用优先队列（小顶堆）实现，按f值排序。

3. 封闭列表（Closed List）：存储已考察过的节点，避免重复处理。

4. 节点数据结构：通常包含：

- 位置信息（坐标）

- g值（从起点到该节点的实际代价）

- h值（启发式估计值）

- f值（f = g + h）

- 父节点指针（用于回溯路径）

 

A* 算法设计原理

A* 算法是一种启发式搜索算法，用于在图中寻找从起点到目标点的最优路径。它结合了 Dijkstra 算法的完备性（保证找到最短路径）和贪心最佳优先搜索的高效性。

核心公式：
f(n) = g(n) + h(n)

• g(n)：从起点到节点 n 的实际代价

• h(n)：从节点 n 到目标的估计代价（启发式函数）

• f(n)：节点 n 的综合优先级

关键要求：

1. 可采纳性：h(n) 必须 ≤ 实际最小代价（不能高估）

2. 一致性：h(n) ≤ c(n, n') + h(n')（三角不等式）

数据结构：

• 开放列表 (Open List)：优先队列，存储待探索节点（按 f(n) 排序）

• 封闭列表 (Closed List)：记录已探索节点

• 节点信息：坐标、g 值、h 值、父节点指针

 

---

算法步骤：

- 初始化：将起点加入开放列表。

- 循环直到找到目标或开放列表为空：

1. 从开放列表中取出f值最小的节点（作为当前节点）。

2. 如果该节点是目标节点，则回溯构建路径并返回。

3. 将该节点移入封闭列表。

4. 遍历当前节点的所有邻居：

- 如果邻居在封闭列表中，则跳过。

- 如果邻居不在开放列表中，则计算其g、h、f值，设置父节点为当前节点，并加入开放列表。

- 如果邻居已在开放列表中，则检查通过当前节点到达该邻居是否具有更小的g值（即更优路径），如果是，则更新其g值和f值，并重新调整优先队列。

该部分可参见---> A*

此时，I节点总代价最小，会以I节点继续作为父节点，继续搜索邻近节点。

---

C++实现A*算法具体流程：

具体实现步骤（C++）

我们将实现一个在二维网格上运行的A*算法。网格中0表示可通行，1表示障碍物。

数据结构

1. 节点（Node）：包含坐标(x,y)，g值，h值，f值，父节点坐标。

2. 比较函数：用于优先队列，按f值从小到大排列（若f值相同，可以按h值排序）。

步骤

1. 创建两个列表：开放列表（优先队列）和封闭列表（可以用二维数组或哈希集合）。

2. 初始化起点的g=0，h=启发式函数计算，f=g+h，并将起点加入开放列表。

3. 循环直到开放列表为空：

- 取出f值最小的节点作为当前节点。

- 若当前节点为目标节点，回溯路径并返回。

- 将当前节点标记为已访问（加入封闭列表）。

- 遍历当前节点的八个邻居（或四个，这里我们实现八个方向的移动）：

- 跳过障碍物和不可达位置。

- 如果邻居不在封闭列表中：

- 计算临时g值（当前节点的g + 移动到邻居的代价，直线为1，斜线为√2，但为了简单，我们假设直线代价10，斜线代价14，这样避免浮点运算）。

- 如果该邻居不在开放列表中，则加入。

- 如果在开放列表中，但新的g值更小，则更新其g值和f值，并调整优先队列（由于标准优先队列不支持更新，我们采用懒惰删除：即当节点被取出时检查是否已被访问，同时允许重复加入节点，但通过封闭列表避免重复处理。或者使用可更新的优先队列，但C++标准库不直接支持，所以我们采用允许重复加入但用封闭列表过滤，并在取出时判断是否已经在封闭列表中。另外，我们也可以在节点进入开放列表时记录状态，当有更优路径时，我们直接更新节点的值，然后重新调整优先队列。然而，由于标准优先队列不支持更新，我们可以使用multiset或者set来手动实现更新，或者使用一个二维数组来记录每个节点的最佳g值，这样当遇到重复节点时，如果新的g值更小，我们就重新加入一个节点（即同一个位置有两个节点，但g值不同），然后旧的节点在取出时会被封闭列表过滤掉。这里我们采用后一种方法：用一个二维数组`gScore`记录每个节点的最佳g值，这样在遇到同一个节点时，如果新的g值更小，我们就重新生成一个节点加入开放列表，而旧节点即使还在队列中，当它被取出时，我们会检查它的g值是否与当前记录的最佳g值一致，如果不一致则跳过（或者用封闭列表，但封闭列表是在节点被处理后才加入，所以我们可以不检查，因为新节点g值更小，会先被处理）。然而，更简单的方法是：每当计算邻居时，如果新的g值小于该邻居之前记录的g值，那么我们就更新这个邻居的g值，并重新加入开放列表（尽管它已经在队列中，但我们允许重复，因为新的f值更小，所以会先被取出）。然后当从开放列表中取出节点时，我们检查它是否已经被处理过（即封闭列表），如果已经处理过则跳过。

优化点

- 使用一个二维数组gScore来存储每个位置的最佳g值，初始为无穷大。

- 当计算临时g值（tentative_g）小于该邻居的gScore时，更新gScore，并将该节点（新的g值）加入开放列表。

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>using namespace std;// 定义节点结构
struct Node {int x, y;       // 节点坐标double g, h, f; // 代价值Node* parent;    // 父节点指针Node(int x, int y, Node* parent = nullptr) : x(x), y(y), g(0), h(0), f(0), parent(parent) {}// 重载比较运算符（用于优先队列）bool operator<(const Node& other) const {return f > other.f; // 注意：优先队列默认最大堆，反向定义实现最小堆}
};// 比较函数对象（用于优先队列）
struct NodeCompare {bool operator()(const Node* a, const Node* b) const {return a->f > b->f; // f值小的优先级高}
};// 移动方向定义（8个方向）
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
const double costStraight = 1.0;  // 直线移动代价
const double costDiagonal = 1.414;// 对角线移动代价（√2）// 启发式函数（欧几里得距离）
double heuristic(int x1, int y1, int x2, int y2) {return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}// A* 算法核心实现
vector<pair<int, int>> aStarSearch(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> goal) {int rows = grid.size();int cols = grid[0].size();// 开放列表（优先队列）priority_queue<Node*, vector<Node*>, NodeCompare> openList;// 封闭列表（二维数组标记）vector<vector<bool>> closedList(rows, vector<bool>(cols, false));// 起点节点初始化Node* startNode = new Node(start.first, start.second);startNode->h = heuristic(start.first, start.second, goal.first, goal.second);startNode->f = startNode->g + startNode->h;openList.push(startNode);while (!openList.empty()) {// 获取f值最小的节点Node* current = openList.top();openList.pop();int x = current->x;int y = current->y;// 到达目标点：回溯生成路径if (x == goal.first && y == goal.second) {vector<pair<int, int>> path;while (current) {path.push_back({current->x, current->y});current = current->parent;}reverse(path.begin(), path.end());return path;}// 当前节点加入封闭列表closedList[x][y] = true;// 遍历所有邻居方向for (int i = 0; i < 8; ++i) {int nx = x + dx[i];int ny = y + dy[i];// 检查邻居是否合法if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == 1 || closedList[nx][ny]) {continue;}// 计算移动代价（判断直线/对角线）double moveCost = (abs(dx[i]) + abs(dy[i]) == 2) ? costDiagonal : costStraight;double newG = current->g + moveCost;// 创建邻居节点Node* neighbor = new Node(nx, ny, current);neighbor->g = newG;neighbor->h = heuristic(nx, ny, goal.first, goal.second);neighbor->f = neighbor->g + neighbor->h;// 加入开放列表openList.push(neighbor);}}return {}; // 未找到路径
}// 打印网格和路径
void printSolution(const vector<vector<int>>& grid, const vector<pair<int, int>>& path) {vector<vector<char>> display = vector<vector<char>>(grid.size(), vector<char>(grid[0].size(), ' '));// 标记障碍物for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {if (grid[i][j] == 1) display[i][j] = '#';}}// 标记路径（起点和终点特殊标记）for (const auto& p : path) {if (p == path.front()) display[p.first][p.second] = 'S';else if (p == path.back()) display[p.first][p.second] = 'G';else display[p.first][p.second] = '*';}// 打印结果for (const auto& row : display) {for (char c : row) {cout << '[' << c << ']';}cout << endl;}
}int main() {// 示例网格：0=空地, 1=障碍物vector<vector<int>> grid = {{0, 0, 0, 0, 0, 0},{0, 1, 1, 0, 1, 0},{0, 0, 0, 0, 1, 0},{0, 1, 1, 1, 1, 0},{0, 0, 0, 0, 0, 0}};pair<int, int> start = {0, 0};pair<int, int> goal = {4, 5};// 执行A*搜索vector<pair<int, int>> path = aStarSearch(grid, start, goal);// 输出结果if (path.empty()) {cout << "No path found!" << endl;} else {cout << "Path found (" << path.size() << " steps):" << endl;for (const auto& p : path) {cout << "-> (" << p.first << "," << p.second << ") ";}cout << "\n\nVisualization:\n";printSolution(grid, path);}return 0;
}

执行结果示例：

 此实现完整展示了A*算法的核心机制，包含启发式函数设计、开放/封闭列表管理、路径回溯等关键环节，适合用于网格地图中的路径规划问题。

---

关键实现说明：

1. 节点表示：

   • 存储坐标、g/h/f 值、父节点指针

   • 重载 < 运算符实现优先队列排序

2. 启发式函数：

   • 使用欧几里得距离（满足可采纳性）

   • 替代方案：曼哈顿距离（仅限4方向）

3. 邻居探索：

   • 支持8方向移动（含对角线）

   • 直线代价1.0，对角线代价1.414（√2）

   • 边界检查和障碍物检查

4. 路径回溯：

   • 通过父节点指针反向追溯路径

   • 使用 reverse() 获得正向路径

5. 内存管理：

   • 简化版未处理内存释放（实际应用需优化）

   • 建议使用智能指针或对象池

注意事项和改进：

 注意事项

1. 内存管理：上述代码存在内存泄漏，因为创建的节点在加入开放列表后，如果没有被及时删除，会导致内存泄漏。在实际应用中，应该使用智能指针（如`unique_ptr`）或者用一个容器管理所有节点，在函数返回前统一释放。

2. 启发式函数：这里实现了对角线距离的启发式函数，确保可采纳性。

3. 移动代价：直线移动代价为10，斜线为14（即10的倍数，避免浮点数）。

4. 节点更新：由于标准优先队列不支持更新节点值，我们采用每次有更优路径时重新加入节点（允许重复），并在取出节点时检查是否已被访问（封闭列表）来跳过旧节点。

5. 封闭列表：用于记录已处理的节点，避免重复处理。

6. 性能：在网格较大时，优先队列的操作（O(logN)）和节点数量（最多网格大小）会影响性能。

 改进方向

- 内存管理：使用智能指针或节点池。

- 数据结构：使用更高效的优先队列（如Fibonacci堆）来支持节点值的更新，但C++标准库中没有提供。

- 启发式函数：可以根据实际需求调整，但必须确保可采纳性（如使用欧几里得距离）。

- 路径平滑：A*找到的路径可能不是最平滑的，可以后处理进行平滑。

终极目标：