下面是一个**完整的、可直接运行的 A\* 算法 C 实现**专门为面试笔试场景设计。代码包含了核心数据结构、启发式函数曼哈顿距离、路径回溯、以及一个简单的控制台演示在 5x5 网格上从起点到终点寻找路径。你可以直接复制这段代码在本地编译运行或者根据笔试题目要求比如改为 8 方向、加入障碍物动态输入、改为三维空间等进行修改。---cpp#include iostream#include vector#include queue#include cmath#include unordered_map#include algorithmusing namespace std;// 坐标点struct Point {int x, y;Point(int _x 0, int _y 0) : x(_x), y(_y) {}bool operator(const Point other) const {return x other.x y other.y;}};// 哈希函数用于 unordered_mapstruct PointHash {size_t operator()(const Point p) const {return hashint()(p.x) ^ (hashint()(p.y) 1);}};// A* 节点struct AStarNode {Point pos;double g; // 从起点到当前点的实际代价double h; // 启发式估计代价double f; // f g hPoint parent;AStarNode(Point _pos, double _g, double _h, Point _parent): pos(_pos), g(_g), h(_h), f(_g _h), parent(_parent) {}// 优先队列默认是大顶堆这里重载 使其成为小顶堆按 f 值排序bool operator(const AStarNode other) const {return f other.f;}};class AStar {private:vectorvectorint grid; // 0: 可通行, 1: 障碍物int rows, cols;Point start, goal;// 方向4 邻域上、下、左、右vectorPoint directions {{-1,0}, {1,0}, {0,-1}, {0,1}};// 检查点是否在网格内且不是障碍物bool isValid(int x, int y) {return x 0 x rows y 0 y cols grid[x][y] 0;}// 曼哈顿距离作为启发式double heuristic(const Point a, const Point b) {return abs(a.x - b.x) abs(a.y - b.y);}public:AStar(const vectorvectorint _grid, Point _start, Point _goal): grid(_grid), start(_start), goal(_goal) {rows grid.size();cols grid[0].size();}// 核心 A* 算法vectorPoint findPath() {// 边界检查if (!isValid(start.x, start.y) || !isValid(goal.x, goal.y)) {cout 起点或终点不可达 endl;return {};}// 优先队列open setpriority_queueAStarNode openSet;// 记录每个节点的最佳 g 值unordered_mapPoint, double, PointHash gScore;// 记录父节点用于回溯路径unordered_mapPoint, Point, PointHash cameFrom;// 初始化起点openSet.push(AStarNode(start, 0, heuristic(start, goal), start));gScore[start] 0;while (!openSet.empty()) {AStarNode current openSet.top();openSet.pop();Point curPos current.pos;// 到达终点if (curPos goal) {return reconstructPath(cameFrom, curPos);}// 遍历邻居for (auto dir : directions) {int nx curPos.x dir.x;int ny curPos.y dir.y;Point neighbor(nx, ny);if (!isValid(nx, ny)) continue;// 计算新的 g 值假设移动代价为 1double tentative_g gScore[curPos] 1;// 如果该节点未访问过或找到了更优路径if (gScore.find(neighbor) gScore.end() || tentative_g gScore[neighbor]) {gScore[neighbor] tentative_g;double h heuristic(neighbor, goal);openSet.push(AStarNode(neighbor, tentative_g, h, curPos));cameFrom[neighbor] curPos;}}}cout 未找到路径 endl;return {};}// 回溯路径vectorPoint reconstructPath(unordered_mapPoint, Point, PointHash cameFrom, Point current) {vectorPoint path;while (!(current start)) {path.push_back(current);current cameFrom[current];}path.push_back(start);reverse(path.begin(), path.end());return path;}// 打印路径可视化void printPath(const vectorPoint path) {if (path.empty()) {cout 无路径可打印 endl;return;}// 创建网格副本用于显示vectorvectorchar display(rows, vectorchar(cols, .));for (int i 0; i rows; i) {for (int j 0; j cols; j) {if (grid[i][j] 1) display[i][j] #;else display[i][j] .;}}// 标记路径不覆盖起点和终点for (size_t i 1; i path.size() - 1; i) {display[path[i].x][path[i].y] *;}display[start.x][start.y] S;display[goal.x][goal.y] G;// 打印cout \n路径可视化S起点, G终点, *路径, #障碍物, .空地:\n;for (int i 0; i rows; i) {for (int j 0; j cols; j) {cout display[i][j] ;}cout endl;}cout \n路径坐标: ;for (auto p : path) {cout ( p.x , p.y ) ;}cout \n路径长度: path.size() - 1 步 endl;}};// ---------- 测试主函数 ----------int main() {// 定义 5x5 网格0可通行, 1障碍物vectorvectorint grid {{0, 0, 0, 1, 0},{0, 1, 0, 1, 0},{0, 1, 0, 0, 0},{0, 0, 0, 1, 0},{0, 0, 0, 0, 0}};Point start(0, 0);Point goal(4, 4);AStar astar(grid, start, goal);vectorPoint path astar.findPath();astar.printPath(path);return 0;}---### 面试官可能追问的问题建议提前准备| 问题 | 参考回答 ||------|----------|| **启发式函数为什么选曼哈顿距离** | 因为网格地图只允许上下左右移动曼哈顿距离是**可采纳的**不大于真实代价保证 A* 最优。如果允许 8 方向则改用**对角距离**或欧几里得距离。 || **如何改成 8 方向** | 在 directions 里增加 4 个对角方向 {-1,-1}, {-1,1}, {1,-1}, {1,1}并且对角移动代价设为 √2或 1.4同时启发式改为对角距离。 || **openSet 用 priority_queue 的缺点** | 无法直接更新节点只能 push 新副本可能导致同一个节点在堆中存在多个旧副本。笔试题一般可接受工业级可用 std::set 或 unordered_set 手动更新。 || **如何防止重复扩展** | 这里通过 gScore 判断如果 tentative_g gScore[neighbor] 则跳过。实际上可以再加一个 unordered_set 记录已关闭节点。 || **如果地图非常大怎么办** | 使用**跳点搜索JPS** 或**双向 A***或改用**网格分层**、**路标**等工程方法。 |---### ✅ 代码亮点适合写在笔试答案里- **模块化设计**AStar 类封装了核心逻辑易于扩展。- **使用 unordered_map 存储父节点和 g 值**适合稀疏图。- **重载 operator** 使优先队列按 f 值升序排列。- **路径回溯与可视化**方便验证结果。如果你需要我针对特定题型比如三维空间、动态障碍物、多目标点修改代码随时告诉我我可以再给你一版。祝你笔试顺利你提到的“缔结斯特拉算法”应该是 **迪杰斯特拉算法Dijkstra** 的笔误或音译。下面把 **Dijkstra 算法**和 **BFS广度优先搜索** 做一个系统对比。---## 1. 一句话概括- **BFS**在**无权图**或**边权相同**的图中按“层”逐层扩展第一次到达某节点时的路径就是最短路径。- **Dijkstra**在**带非负权边**的图中每次从“未确定节点”里选出当前距离最小的节点逐步确定到所有节点的最短路径。---## 2. 核心区别对比| 维度 | BFS | Dijkstra ||------|-----|----------|| 适用图类型 | 无权图 / 边权全相同 | 带权图且边权非负 || 数据结构 | 队列FIFO | 优先队列 / 最小堆 || 扩展顺序 | 按层扩展先进先出 | 按当前最短距离从小到大扩展 || 边权处理 | 不处理默认每步代价为 1 | 累加边权比较路径总代价 || 最短路径保证 | 无权图下保证最短 | 非负权图下保证最短 || 时间复杂度 | \(O(VE)\) | 二叉堆\(O((VE)\log V)\)斐波那契堆\(O(EV\log V)\) || 空间复杂度 | \(O(V)\) | \(O(V)\) || 是否支持负权边 | 不涉及 | 不支持负权边 || 典型用途 | 迷宫最短步数、社交网络层数、无权图连通性 | 地图导航、网络路由、带权路径规划 |---## 3. 算法思想差异### BFS 的思想BFS 把图看成一层一层的1. 从起点出发先访问所有距离为 1 的节点2. 再访问所有距离为 2 的节点3. 以此类推。因为每走一步代价都一样所以**第一次访问到某个节点时走过的步数一定最少**。伪代码textqueue.push(start)visited[start] truewhile queue 非空:u queue.pop_front()for v in neighbors(u):if not visited[v]:visited[v] truedist[v] dist[u] 1queue.push_back(v)### Dijkstra 的思想Dijkstra 把图看成带权网络1. 维护一个“当前已知最短距离”数组2. 每次从未确定的节点中选出距离最小的那个把它标记为“已确定”3. 用这个节点去松弛它的邻居如果经过它能让邻居更近就更新邻居距离4. 重复直到所有节点确定。伪代码textdist[start] 0pq.push((0, start))while pq 非空:d, u pq.pop_min()if d dist[u]: continuefor (v, w) in neighbors(u):if dist[u] w dist[v]:dist[v] dist[u] wpq.push((dist[v], v))---## 4. 为什么 BFS 不能直接处理带权图举个例子textA --1-- B --1-- CA --3-- C- BFS 会先访问 B再访问 C认为 A→C 的距离是 2 步- 但实际上 A→C 的直接边权是 3而 A→B→C 的总权是 2。- 如果边权不是 1BFS 的“层数”就不等于“路径代价”。所以 BFS 只适合**边权相同**的情况。若边权都是正整数但不同可以用 **0-1 BFS** 或 **Dijkstra**。---## 5. 为什么 Dijkstra 不能处理负权边Dijkstra 的核心假设是**一旦某个节点被选出为当前最小距离它的最短路径就已经确定不会再被更新。**但如果存在负权边这个假设就不成立textA --2-- BA --5-- CC --(-4)-- B- Dijkstra 先确定 B 的距离为 2- 但实际 A→C→B 5 (-4) 1更短。- 因为 B 已经被“确定”Dijkstra 不会再更新它导致错误。带负权边要用 **Bellman-Ford** 或 **SPFA**。---## 6. 两者的联系其实 **BFS 可以看作 Dijkstra 在边权全为 1 时的特例**- 当所有边权都是 1 时优先队列中取出的最小距离节点正好就是队列最前面的节点- 此时优先队列退化成普通队列Dijkstra 就变成了 BFS。所以 **BFS 无权图上的最短路算法Dijkstra 非负权图上的最短路算法。**---## 7. 实际选择建议| 场景 | 推荐算法 ||------|----------|| 迷宫走格子每步代价相同 | BFS || 社交网络找最少跳数 | BFS || 地图导航道路有不同长度/时间 | Dijkstra || 网络路由链路代价不同 | Dijkstra || 边权只有 0 和 1 | 0-1 BFS双端队列 || 边权有负数 | Bellman-Ford / SPFA || 需要所有点对最短路 | Floyd-Warshall |---## 总结- **BFS**队列实现按层扩展适合无权图复杂度 \(O(VE)\)。- **Dijkstra**优先队列实现按距离最小扩展适合非负权图复杂度约 \(O((VE)\log V)\)。- 两者本质都是“从起点向外扩展”区别在于**是否考虑边权**以及**扩展顺序由谁决定**。- 边权全为 1 时Dijkstra 退化为 BFS。