题目描述
在 3×3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入格式
输入初始状态，一行九个数字，空格用 0 表示。
输出格式
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。
输入输出样例
输入 #1复制
283104765
输出 #1复制
4
说明/提示
样例解释
图中标有 0 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。
并且可以证明，不存在更优的策略。
解析：
1.最短步骤想到使用bfs，用string来记录当前的状态，遍历状态。
注意：string 下角标是从0开始的，x = dx/3 , y = dy%3; 为真实九宫格的坐标。九宫格坐标是从（0，0）开始的。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
unordered_map<string,int> d;
queue<string> q;
int dx[4] ={-1,0,1,0};
int dy[4] = {0,1,0,-1};
int bfs(string str)
{
q.push(str);
string end="123804765";
while(q.size())
{
string s = q.front();
q.pop();
if(s==end) return d[s];
int k = s.find('0');
int x = k/3,y = k%3;
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;
int dis = d[s];
swap(s[k],s[a*3 + b]);
if(!d.count(s))//交换
d[s] = dis+1,q.push(s);
swap(s[k],s[a*3+b]);//还原
}
}
}
int main()
{
string s;
cin >> s;
cout << bfs(s)<<endl;
return 0;
}时间复杂度为：O()
使用A*算法进行优化。
A算法给出了评价函数的定义： f(n) = g(n) + h(n)
其中，n为待评价的节点；g(n)为从初始节点s到节点n的最佳路径耗散值的估计值；h(n)为从节点n到目标节点t的最佳路径耗散值的估计值，称为启发函数；f(n)为从初始节点s经过节点n到达目标节点的最佳路径耗散值的估计值，成为评价函数，我们每次从叶节点选出f(n)最小的节点扩展。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> d;
string goal = "123804765";
int gx[] = {-1,0,0,0,1,2,2,2,1};
int gy[] = {-1,0,1,2,2,2,1,0,0};
int dx[4] ={-1,0,1,0};
int dy[4] = {0,1,0,-1};
int f(string s)
{ // 每个数字到目的地的坐标
int res = 0;
for(int i = 0;i < 9;i++)
{
int t = s[i]-'0';
if(t) res+= abs(i/3 - gx[t]) + abs(i%3-gy[t]);
}
return res;
}
int bfs(string str)
{
unordered_map<string,int> d;
priority_queue<pair<int,string>> q;//默认大根堆 ，我们只需要取负数，小的数就会在上面
q.push({-f(str),str});
d[str] = 0;
while(q.size())
{
auto a = q.top();
q.pop();
string s = a.second;
if(s== goal) return d[s]; // d 记录现实的 状态 f为理想状态下 曼哈顿距离
int k = s.find('0');
int x = k /3,y = k%3;
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;
string t = s;
swap(t[k],t[a*3+b]);
if(!d.count(t))
{
d[t] = d[s]+1,q.push({-(d[t] + f(t)),t});
}
}
}
}
int main()
{
string s;
cin >> s;
cout << bfs(s)<<endl;
return 0;
}
