背景:
一般bfs只能看到起点到当前点的距离,但这样可能遇到一些情况前面的状态距离小,后面的状态距离大,先搜这样的显然不是最好的选择,考虑当前点到终点的预估距离就可以解决这种问题
A*算法:
用A*来做
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;
typedef pair<int, string> PIS; //起名找规律,P对应pair,I对应int,S对应string
int f(string state) //估计函数,以当前位置上的点到它本该在的位置的曼哈顿距离
{
int res = 0;
for(int i = 0; i < state.size(); i ++)
if(state[i] != 'x')
{
int t = state[i] - '1'; //转换为数字,便于求矩阵中坐标
res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3); //求出曼哈顿距离
}
return res;
}
string bfs(string start)
{
string end = "12345678x";
unordered_map<string, int> dist; //每种状态对应的距离
unordered_map<string, pair<char, string>> prev; //记录每种状态是由谁转移过来的,并且操作是什么
priority_queue<PIS, vector<PIS>, greater<PIS>> heap; //小根堆
//堆中存的是估计距离和状态
heap.push({f(start), start});
dist[start] = 0;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
char op[] = {'r', 'd', 'l', 'u'}; //操作数组,最后要输出
while(heap.size())
{
auto t = heap.top();
heap.pop();
string state = t.second;
if(state == end) break;
//接下来就是普通的八数码做法,交换
int k = state.find('x'); //先找到在字符串中的下标
int x = k / 3, y = k % 3;//找到在矩阵中的下标
string source = state;
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= 3 || b < 0 || b >= 3 ) continue;
swap(state[k], state[a * 3 + b]); //交换位置
if(!dist.count(state) || dist[state] > dist[source] + 1)
{
dist[state] = dist[source] + 1;
prev[state] = {op[i], source}; //记录每种状态是由谁转移过来的,并且操作是什么
//堆中维护的距离是起点到当前点的实际距离加上当前点到终点的估计距离
heap.push({dist[state] + f(state), state});
}
swap(state[k], state[a * 3 + b]); //恢复原状态,不干扰后面遍历
}
}
string res = ""; //记录答案
while(start != end) //从终点往前推
{
res += prev[end].first;
end = prev[end].second;
}