A*(一)
2026-08-21 11:38:14
发布于：广东
#include <bits/stdc++.h>
using namespace std;
// 计算启发函数（曼哈顿距离）
int heuristic(string& state) {
int distance = 0; // 初始化曼哈顿距离总和为0
// 遍历状态字符串中的每个位置（0-8，对应3×3网格的9个格子）
for (int i = 0; i < 9; i++) {
if (state[i] == 'x') continue; // 如果是空格'x'，跳过不计算
int num = state[i] - '0'; // 将字符数字转换为整数（'1'->1, '2'->2, ...）
int target_x = (num - 1) / 3; // 计算该数字在目标状态中的行号（0,1,2）
int target_y = (num - 1) % 3; // 计算该数字在目标状态中的列号（0,1,2）
int current_x = i / 3; // 计算该数字当前位置的行号
int current_y = i % 3; // 计算该数字当前位置的列号
// 累加曼哈顿距离：行距离 + 列距离
distance += abs(target_x - current_x) + abs(target_y - current_y);
}
return distance; // 返回总曼哈顿距离作为启发值
}
int astar(string start) {
string target = "12345678x"; // 目标状态：正确排列
if (start == target) return 0; // 如果初始状态就是目标状态，直接返回0步
// 优先队列（最小堆），存储pair<f值, 状态字符串>
// f(n) = g(n) + h(n)，其中g是实际代价，h是启发值
// greater<pair<int, string>> 使队列按f值从小到大排序
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
unordered_map<string, int> dist; // 记录到达每个状态的实际代价g(n)
unordered_map<string, bool> visited; // 记录每个状态是否已经访问过
// 初始化：起点状态的实际代价为0
dist[start] = 0;
// 将起点加入优先队列，f值 = g(0) + h(start)
pq.push({heuristic(start), start});
// 移动方向数组：上、右、下、左（对应行和列的偏移）
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
// A*算法主循环
while (!pq.empty()) {
// 取出优先队列中f值最小的状态（结构化绑定，C++17特性）
auto [f, state] = pq.top();
pq.pop(); // 弹出队顶元素
if (state == target) return dist[state]; // 如果到达目标状态，返回实际步数
if (visited[state]) continue; // 如果已经访问过该状态，跳过（避免重复处理）
visited[state] = true; // 标记当前状态为已访问
int k = state.find('x'); // 找到空格'x'在字符串中的位置（0-8）
int x = k / 3, y = k % 3; // 将一维位置转换为二维坐标（行x，列y）
int g = dist[state]; // 当前状态的实际代价g
// 尝试四个方向的移动：上、右、下、左
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i]; // 计算移动后空格的新位置
// 检查移动后的位置是否在3×3网格范围内
if (a >= 0 && a < 3 && b >= 0 && b < 3) {
string next_state = state; // 复制当前状态
// 交换空格与相邻位置的数字
swap(next_state[k], next_state[a * 3 + b]);
// 如果新状态未被访问过，或者找到更短的路径到达该状态
if (!dist.count(next_state) || g + 1 < dist[next_state]) {
dist[next_state] = g + 1; // 更新到达新状态的实际代价
int h = heuristic(next_state); // 计算新状态的启发值h
// 将新状态加入优先队列，f = g + h
pq.push({dist[next_state] + h, next_state});
}
}
}
}
return -1; // 如果队列为空仍未找到目标状态，返回-1表示无解
}
int main() {
string state; // 定义字符串变量，用于存储输入的初始状态
cin >> state; // 从标准输入读取初始状态（如"12345678x"）
cout << astar(state) << endl; // 调用A*算法求解并输出最少交换次数
return 0; // 程序正常结束
}
这里空空如也
有帮助，赞一个