大家好,又见面了,我是你们的朋友全栈君。
【八数码问题】//https://vijos.org/p/1360
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
【分析】
题目读完第一感觉是和求解最短路径问题类似,考虑使用BFS,状态很好找,每次移动空格就会形成一种新的状态,例如:
1.每个状态都用3*3的数组表示,但是BFS中需要入队出队,比较麻烦而且空间占用较大
2.状态压缩,采用一个整数保存状态的数字序列,例如状态1表示为283104765,状态2表示为203184765
1.如果空间允许,开一个876543210大小的bool数组,某个序列出现就将数组值置为1;但是竞赛中一般都是限制128M(大约10000000),这个数组开不下来。
2.虽然状态范围是012345678–876543210,但是中间真正有效的只有9!=362800,因为数字不可能出现重复;因此可以考虑开一个数组大小为9!整型数组A和bool数组B,然后生成0-8这9个数码的全排列并按照升序或者降序存入数组中,要判断某个状态(一种排列方式)是否出现过,直接通过二分查找的方式找到该排列在A中的下标i,然后查看数组B[i]为true还是false;如果为true则出现过,如果为false则将状态入队,并设置B[i]=true;
3.其实从方案2中我们已经看到,判重的实质就是建立状态数字串(一个int数据)和是否出现(一个bool数据)之间的联系,而STL中刚好提供了map<key,value>这样一种容器,我们可以将状态数字串作为key,是否出现作为value直接建立起状态–是否出现的联系。
4.使用hash判重,将状态数字串通过某种映射f(x)从012345678–876543210这样一个大集合,映射到128M范围之内;这里采用简单的hash,取模一个大质数,只要这个质数大于9!即可;当然这里可能出现冲突,也就是key1!=key2但是f(key1)==f(key2),hash算法只能减少冲突不能避免冲突。这里如何减少冲突呢?挂链表,当key1!=key2但是f(key1)==f(key2),则将key2挂到key1后面;当然这里如果使用康托展开可以完美一一映射而不冲突,但是我不会(~^~)。
搜索方法大方向肯定是BFS,只是在对BFS基础上还可以更优化,这里给出三种搜索方式,三种搜索方式和上面的三种判重组合起来就有9种解法了(哈哈哈);
这是最普通的广度优先算法,没啥好说的……
双向广度优先,两个队列,一个从起点开始扩展状态,另一个从终点开始扩展状态;如果两者相遇,则表示找到了一条通路,而且是最短的通路。双向广度优先可以大大提高效果,而且可以减少很多不必要的状态扩展。盗个图来说明一下,其中的阴影部分为减少的扩展状态
启发式搜索,关键是启发策略的制定,一个好的启发式策略可以很快的得到解,如果策略不好可能会导致找不到正确答案。
在BFS搜索算法中,如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表(队列)中的节点进行排序,则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息,因此,A算法又称为启发式搜索算法。
对启发式搜索算法,又可根据搜索过程中选择扩展节点的范围,将其分为全局择优搜索算法和局部择优搜索算法。
• 在全局择优搜索中,每当需要扩展节点时,总是从 Open 表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可能描述如下:
• ( 1 )把初始节点 S0 放入 Open 表中, f(S0)=g(S0)+h(S0) ;
• ( 2 )如果 Open 表为空,则问题无解,失败退出;
• ( 3 )把 Open 表的第一个节点取出放入 Closed 表,并记该节点为 n ;
• ( 4 )考察节点 n 是否为目标节点。若是,则找到了问题的解,成功退出;
• ( 5 )若节点 n 不可扩展,则转到第 (2) 步;
• ( 6 )扩展节点 n ,生成子节点 ni ( i =1,2, …… ) ,计算每一个子节点的估价值 f( ni ) ( i =1,2, …… ) ,并为每一个子节点设置指向父节点的指针,然后将这些子节点放入 Open 表中;
• ( 7 )根据各节点的估价函数值,对 Open 表中的全部节点按从小到大的顺序重新进行排序;
• ( 8 )转第 (2) 步。
这里采用的启发式策略为:f(n) = g(n) + h(n),其中g(n)为从初始节点到当前节点的步数(层数),h(n)为当前节点“不在位”的方块数,例如下图中的h(n)=5,有很多博客中讲解的是不包含空格,我这里是包含了的,经测试只要前后标准一致,包不包含空格都一样。
下来看看启发式策略工作工程:红圈数字表示扩展顺序
以上就是所有思路分析,下面是代码实现,有些代码有瑕疵,欢迎各位大佬指正(-_-)
#include<cstdio>
#include<cstring>
#include<ctime>
char ans[11],start[10];
bool isUsed[11];
int changeId[9][4]={
{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}
};//0出现在0->8的位置后该和哪些位置交换
const int M=400000;//9!=362800,因此数组开40W足够了
int num[M],len=0,des=123804765;//num存储所有排列,len表示排列的个数也就是9!,des为目的状态直接用整数表示便于比较
bool isV[M];//bfs时判断状态是否出现过;isV的下标和num的下标一一对应,表示某种排列是否出现过
//通过isV和num建立起某种排列的组合成的整数int和bool的关系,其实STL中有map实现了key-->value,用排列作为key,value用bool即可
int que[M][3];//0-->排列,1-->排列中0的位置,2-->步数
void swap(char *c,int a,int b){//交换字符串中的两个位置
char t=c[a];
c[a]=c[b];
c[b]=t;
}
void paiLie(int n,int k){//深搜产生0-8的全排列
for(int i=0;i<n;i++){
if(!isUsed[i]){
ans[k]=i+'0';
isUsed[i]=1;
if(k==n){//已经有n个转换存储
ans[k+1]='\0';
sscanf(ans+1,"%d",&num[len++]);
}
else
paiLie(n,k+1);
isUsed[i]=0;//回溯一步
}
}
}
int halfFind(int l,int r,int n){//二分查找
int mid=l+(r-l)/2;
if(num[mid]==n)return mid;
else if(l<r&&num[mid]>n)return halfFind(l,mid-1,n);
else if(l<r&&num[mid]<n) return halfFind(mid+1,r,n);
return -1;
}
int bfs(int n,int p){
int head=0,tail=1,temp;//head队头,tail队尾
que[head][0]=n,que[head][1]=p,que[head][2]=head;//初始状态保存到对头,并设置当前步数为0
while(head!=tail){//队列不为空则继续搜索
char cur[10];//用于保存当前状态的字符串
int pos=que[head][1];//当前状态中0的位置
sprintf(cur,"%09d",que[head][0]);//int-->char*这里的09d至关重要,否则算不出答案
for(int i=0;i<4;i++){//扩展当前的状态,上下左右四个方向
int swapTo=changeId[pos][i];//将要和那个位置交换
if(swapTo!=-1){//-1则不交换
swap(cur,pos,swapTo);//交换0的位置得到新状态
sscanf(cur,"%d",&temp);//新状态转换为int保存到temp
if(temp==des)//如果是目标状态则返回当前状态的步数+1
return que[head][2]+1;
int k=halfFind(0,len,temp);//没有返回就查找当前排列的位置,将查出来的下标作为isV的下标
if(!isV[k]){//如果 没有出现过,则将这个新状态进队
que[tail][0]=temp,que[tail][1]=swapTo,que[tail][2]=que[head][2]+1;
tail++;
isV[k]=1;
}
swap(cur,pos,swapTo);//一个新状态处理完了一定要记得将交换的0交换回来
}
}
head++;
}
}
int main(){
int n,i=-1,count=0;
paiLie(9,1);//先将0-8的全排列按照升序产生出来存入num数组
scanf("%s",start);//输入初始状态
while(start[++i]!='0');//查找初始状态0的位置
sscanf(start,"%d",&n);//字符串转换为整数
//int s=clock();
if(n!=des)//判断输入状态是否就是目的状态
count=bfs(n,i);
printf("%d\n",count);
//printf("%.6lf",double(clock()-s)/CLOCKS_PER_SEC);
return 0;
}
#include<cstdio>
#include<cmath>
using namespace std;
char arr[10];
int changeId[9][4]={
{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}};
const int M=2E+6,N=1000003;//362897;
int hashTable[M];//hashtable中key为hash值,value为被hash的值
int next[M];//next表示如果在某个位置冲突,则冲突位置存到hashtable[next[i]]
int que[N][3],des=123804765;
int hash(int n){
return n%N;
}
bool tryInsert(int n){
int hashValue=hash(n);
while(next[hashValue]){//如果被hash出来的值得next不为0则向下查找
if(hashTable[hashValue]==n)//如果发现已经在hashtable中则返回false
return false;
hashValue=next[hashValue];
}//循环结束hashValue指向最后一个hash值相同的节点
if(hashTable[hashValue]==n)//再判断一遍
return false;
int j=N-1;//在N后面找空余空间,避免占用其他hash值得空间造成冲突
while(hashTable[++j]);//向后找一个没用到的空间
next[hashValue]=j;
hashTable[j]=n;
return true;
}
void swap(char* ch,int a,int b){char c=ch[a];ch[a]=ch[b];ch[b]=c;}
int bfsHash(int start,int zeroPos){
char temp[10];
int head=0,tail=1;
que[head][0]=start,que[head][1]=zeroPos,que[head][2]=0;
while(head!=tail){
sprintf(temp,"%09d",que[head][0]);
int pos=que[head][1],k;
for(int i=0;i<4;i++){
if(changeId[pos][i]!=-1){
swap(temp,pos,changeId[pos][i]);
sscanf(temp,"%d",&k);
if(k==des)return que[head][2]+1;
if(tryInsert(k)){//插入新状态成功,则说明新状态没有被访问过
que[tail][0]=k;
que[tail][1]=changeId[pos][i];
que[tail][2]=que[head][2]+1;
tail++;
}
swap(temp,pos,changeId[pos][i]);
}
}
head++;
}
}
int main(){
int n,k;
scanf("%s",arr);
for(k=0;k<9;k++)
if(arr[k]=='0')break;
sscanf(arr,"%d",&n);
printf("%d",bfsHash(n,k));
return 0;
}
hash判重居然比全排列还慢,一直想不通,
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<int,bool> myMap;
int changeId[9][4]={
{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}
};//0出现在0->8的位置后该和哪些位置交换
const int M=400000;//9!=362800,因此数组开40W足够了
int des=123804765;//num存储所有排列,len表示排列的个数也就是9!,des为目的状态直接用整数表示便于比较
int que[M][3];//0-->排列,1-->排列中0的位置,2-->步数
void swap(char *c,int a,int b){//交换字符串中的两个位置
char t=c[a];
c[a]=c[b];
c[b]=t;
}
int bfs(int n,int p){
int head=0,tail=1,temp;//head队头,tail队尾
myMap[n]=1;
que[head][0]=n,que[head][1]=p,que[head][2]=head;//初始状态保存到对头,并设置当前步数为0
while(head!=tail){//队列不为空则继续搜索
char cur[10];//用于保存当前状态的字符串
int pos=que[head][1];//当前状态中0的位置
sprintf(cur,"%09d",que[head][0]);//int-->char*这里的09d至关重要,否则算不出答案
for(int i=0;i<4;i++){//扩展当前的状态,上下左右四个方向
int swapTo=changeId[pos][i];//将要和那个位置交换
if(swapTo!=-1){//-1则不交换
swap(cur,pos,swapTo);//交换0的位置得到新状态
sscanf(cur,"%d",&temp);//新状态转换为int保存到temp
if(temp==des)//如果是目标状态则返回当前状态的步数+1
return que[head][2]+1;
if(myMap.count(temp)==0){//如果 没有出现过,则将这个新状态进队
que[tail][0]=temp,que[tail][1]=swapTo,que[tail][2]=que[head][2]+1;
tail++;
myMap[temp]=1;
}
swap(cur,pos,swapTo);//一个新状态处理完了一定要记得将交换的0交换回来
}
}
head++;
}
}
int main(){
char start[10];
int n,i=-1,count=0;
scanf("%s",start);//输入初始状态
while(start[++i]!='0');//查找初始状态0的位置
sscanf(start,"%d",&n);//字符串转换为整数
if(n!=des)//判断输入状态是否就是目的状态
count=bfs(n,i);
printf("%d",count);
return 0;
}
STL用好了还是有很大作用的,能够减少代码实现难度的同时提高效果;
#include<cstdio>
#include<cstring>
#include<ctime>
char ans[11],start[10];
bool isUsed[11];
int changeId[9][4]={
{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}
};//0出现在0->8的位置后该和哪些位置交换
const int M=400000;//9!=362800,因此数组开40W足够了
int num[M],len=0,des=123804765;//num存储所有排列,len表示排列的个数也就是9!,des为目的状态直接用整数表示便于比较
int isV[M][2];//bfs时判断状态是否出现过;isV的下标和num的下标一一对应,表示某种排列是否出现过
//通过isV和num建立起某种排列的组合成的整数int和bool的关系,其实STL中有map实现了key-->value,用排列作为key,value用bool即可
int que1[M/2][3],que2[M/2][3];//0-->排列,1-->排列中0的位置,2-->步数
void swap(char *c,int a,int b){//交换字符串中的两个位置
char t=c[a];
c[a]=c[b];
c[b]=t;
}
void paiLie(int n,int k){//深搜产生0-8的全排列
for(int i=0;i<n;i++){
if(!isUsed[i]){
ans[k]=i+'0';
isUsed[i]=1;
if(k==n){//已经有n个转换存储
ans[k+1]='\0';
sscanf(ans+1,"%d",&num[len++]);
}
else
paiLie(n,k+1);
isUsed[i]=0;//回溯一步
}
}
}
int halfFind(int l,int r,int n){//二分查找
int mid=l+(r-l)/2;
if(num[mid]==n)return mid;
else if(l<r&&num[mid]>n)return halfFind(l,mid-1,n);
else if(l<r&&num[mid]<n) return halfFind(mid+1,r,n);
return -1;
}
bool expand(int head,int &tail,int who,int q[][3]){
char cur[10];//用于保存当前状态的字符串
int pos=q[head][1],temp;//当前状态中0的位置
sprintf(cur,"%09d",q[head][0]);//int-->char*这里的09d至关重要,否则算不出答案
for(int i=0;i<4;i++){//扩展当前的状态,上下左右四个方向
int swapTo=changeId[pos][i];//将要和那个位置交换
if(swapTo!=-1){//-1则不交换
swap(cur,pos,swapTo);//交换0的位置得到新状态
sscanf(cur,"%d",&temp);//新状态转换为int保存到temp
int k=halfFind(0,len,temp);//没有返回就查找当前排列的位置,将查出来的下标作为isV的下标
if(isV[k][0]==0){//如果 没有出现过,则将这个新状态进队
q[tail][0]=temp,q[tail][1]=swapTo,q[tail][2]=q[head][2]+1;
isV[k][0]=who;
isV[k][1]=tail;
tail++;
}
else if(isV[k][0]&&isV[k][0]!=who){
if(who==1)
printf("%d", q[head][2]+que2[isV[k][1]][2]+1);
else
printf("%d", q[head][2]+que1[isV[k][1]][2]+1);
return true;
}
swap(cur,pos,swapTo);//一个新状态处理完了一定要记得将交换的0交换回来
}
}
return false;
}
void bfs(int n,int p){
int head1=0,tail1=1,head2=0,tail2=1;//head队头,tail队尾
que1[head1][0]=n,que1[head1][1]=p,que1[head1][2]=head1;//初始状态保存到对头,并设置当前步数为0
que2[head2][0]=des,que2[head2][1]=4,que2[head2][2]=head2;//初始状态保存到对头,并设置当前步数为0
int k=halfFind(0,len,n);
isV[k][0]=1,isV[k][1]=0;
k=halfFind(0,len,des);
isV[k][0]=2,isV[k][1]=0;
while(head1!=tail1||tail2!=head2){//队列不为空则继续搜索
if(tail2-head2>=tail1-head1){//2比1元素多就把1扩展
if(expand(head1,tail1,1,que1))return;
head1++;
}
else{
if(expand(head2,tail2,2,que2))return;
head2++;
}
}
}
int main(){//812340756
int n,i=-1,count=0;
paiLie(9,1);//先将0-8的全排列按照升序产生出来存入num数组
scanf("%s",start);//输入初始状态
while(start[++i]!='0');//查找初始状态0的位置
sscanf(start,"%d",&n);//字符串转换为整数
//int s=clock();
if(n!=des)//判断输入状态是否就是目的状态
bfs(n,i);
else
printf("%d",count);
//printf("\n%.6lf",double(clock()-s)/CLOCKS_PER_SEC);
return 0;
}
乍一看,双向广度优先好像和普通的广度优先时间差不多,其实不然,不信自己去掉注释查看运行时间,那为什么测试出来的时间差不多呢?主要是普通BFS和DBFS中都是先生成了全排列,这个过程需要大量时间,而真正搜索占用时间较少,因此感觉不到太大的优化;这里如果采用hash+DBFS效果应该会比较明显。
#include<cstdio>
#include<cmath>
using namespace std;
char arr[10];
int changeId[9][4]={
{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}};
const int M=2E+6,N=1000003;//362897;
int hashTable[M][3];//hashtable中key为hash值,value为被hash的值
int next[M];//next表示如果在某个位置冲突,则冲突位置存到hashtable[next[i]]
int que1[M/2][3],que2[M/2][3],des=123804765;//0-->排列,1-->排列中0的位置,2-->步数
int hash(int n){
return n%N;
}
bool tryInsert(int n,int who,int &index){
int hashValue=hash(n);
while(next[hashValue]){//如果被hash出来的值得next不为0则向下查找
if(hashTable[hashValue][0]==n){//如果发现已经在hashtable中则返回false
index=hashValue;
return false;
}
hashValue=next[hashValue];
}//循环结束hashValue指向最后一个hash值相同的节点
if(hashTable[hashValue][0]==n){//再判断一遍
index=hashValue;
return false;
}
int j=N-1;//在N后面找空余空间,避免占用其他hash值得空间造成冲突
while(hashTable[++j][0]);//向后找一个没用到的空间
next[hashValue]=j;
hashTable[j][0]=n;
hashTable[j][1]=who;
hashTable[j][2]=index;
return true;
}
void swap(char* ch,int a,int b){char c=ch[a];ch[a]=ch[b];ch[b]=c;}
bool expand(int head,int &tail,int who,int q[][3]){
char cur[10];//用于保存当前状态的字符串
int pos=q[head][1],temp;//当前状态中0的位置
sprintf(cur,"%09d",q[head][0]);//int-->char*这里的09d至关重要,否则算不出答案
for(int i=0;i<4;i++){//扩展当前的状态,上下左右四个方向
int swapTo=changeId[pos][i];//将要和那个位置交换
if(swapTo!=-1){//-1则不交换
swap(cur,pos,swapTo);//交换0的位置得到新状态
sscanf(cur,"%d",&temp);//新状态转换为int保存到temp
int index=tail;//用了一点小技巧,通过引用调用,如果hashTable中已存在则带回下标
if(tryInsert(temp,who,index)){//如果 没有出现过,则将这个新状态进队
q[tail][0]=temp,q[tail][1]=swapTo,q[tail][2]=q[head][2]+1;
tail++;//也是通过应用代用实现该函数中tail改变影响bfs函数中的tail改变
}
else{
if(hashTable[index][1]!=who){
if(who==1)
printf("%d", q[head][2]+que2[hashTable[index][2]][2]+1);
else
printf("%d", q[head][2]+que1[hashTable[index][2]][2]+1);
return true;
}
}
swap(cur,pos,swapTo);//一个新状态处理完了一定要记得将交换的0交换回来
}
}
return false;
}
void dbfsHash(int n,int p){
int head1=0,tail1=1,head2=0,tail2=1;//head队头,tail队尾
que1[head1][0]=n,que1[head1][1]=p,que1[head1][2]=head1;//初始状态保存到对头,并设置当前步数为0
que2[head2][0]=des,que2[head2][1]=4,que2[head2][2]=head2;//初始状态保存到对头,并设置当前步数为0
tryInsert(n,1,head1);
tryInsert(des,2,head2);
while(head1!=tail1||tail2!=head2){//队列不为空则继续搜索
if(tail2-head2>=tail1-head1){//2比1元素多就把1扩展
if(expand(head1,tail1,1,que1))return;
head1++;
}
else{
if(expand(head2,tail2,2,que2))return;
head2++;
}
}
}
int main(){
int n,k;
scanf("%s",arr);
for(k=0;k<9;k++)
if(arr[k]=='0')break;
sscanf(arr,"%d",&n);
dbfsHash(n,k);
return 0;
}
#include<cstdio>
#include<queue>
using namespace std;
char arr[10],brr[10]="123804765";
struct node{
int num,step,cost,zeroPos;
bool operator<(const node &a)const{
return cost>a.cost;
}
node(int n,int s,int p){
num=n,step=s,zeroPos=p;
setCost();
}
void setCost(){
char a[10];
int c=0;
sprintf(a,"%09d",num);
for(int i=0;i<9;i++)
if(a[i]!=brr[i])
c++;
cost=c+step;
}
};
int changeId[9][4]={
{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}};
const int M=2E+6,N=1000003;//362897;
int hashTable[M];//hashtable中key为hash值,value为被hash的值
int Next[M],des=123804765;//next表示如果在某个位置冲突,则冲突位置存到hashtable[next[i]]
priority_queue<node> que;//优先级队列
int Hash(int n){
return n%N;
}
bool tryInsert(int n){
int hashValue=Hash(n);
while(Next[hashValue]){//如果被hash出来的值得next不为0则向下查找
if(hashTable[hashValue]==n)//如果发现已经在hashtable中则返回false
return false;
hashValue=Next[hashValue];
}//循环结束hashValue指向最后一个hash值相同的节点
if(hashTable[hashValue]==n)//再判断一遍
return false;
int j=N-1;//在N后面找空余空间,避免占用其他hash值得空间造成冲突
while(hashTable[++j]);//向后找一个没用到的空间
Next[hashValue]=j;
hashTable[j]=n;
return true;
}
void swap(char* ch,int a,int b){char c=ch[a];ch[a]=ch[b];ch[b]=c;}
int bfsHash(int start,int zeroPos){
char temp[10];
node tempN(start,0,zeroPos);
que.push(tempN);
while(!que.empty()){
tempN=que.top();
que.pop();
sprintf(temp,"%09d",tempN.num);
int pos=tempN.zeroPos,k;
for(int i=0;i<4;i++){
if(changeId[pos][i]!=-1){
swap(temp,pos,changeId[pos][i]);
sscanf(temp,"%d",&k);
if(k==des)return tempN.step+1;
if(tryInsert(k)){//插入新状态成功,则说明新状态没有被访问过
node tempM(k,tempN.step+1,changeId[pos][i]);
que.push(tempM);
}
swap(temp,pos,changeId[pos][i]);
}
}
}
}
int main(){
int n,k,b=0;
scanf("%s",arr);
for(k=0;k<9;k++)
if(arr[k]=='0')break;
sscanf(arr,"%d",&n);
if(n!=des)
b=bfsHash(n,k);
printf("%d",b);
return 0;
}
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
char arr[10],brr[10]="123804765";
struct node{
int num,step,cost,zeroPos;
bool operator<(const node &a)const{
return cost>a.cost;
}
node(int n,int s,int p){
num=n,step=s,zeroPos=p;
setCost();
}
void setCost(){
char a[10];
int c=0;
sprintf(a,"%09d",num);
for(int i=0;i<9;i++)
if(a[i]!=brr[i])
c++;
cost=c+step;
}
};
int des=123804765;
int changeId[9][4]={
{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}};
map<int,bool>mymap;
priority_queue<node> que;//优先级队列
void swap(char* ch,int a,int b){char c=ch[a];ch[a]=ch[b];ch[b]=c;}
int bfsHash(int start,int zeroPos){
char temp[10];
node tempN(start,0,zeroPos);//创建一个节点
que.push(tempN);//压入优先级队列
mymap[start]=1;//标记开始节点被访问过
while(!que.empty()){
tempN=que.top();
que.pop();//弹出一个节点
sprintf(temp,"%09d",tempN.num);
int pos=tempN.zeroPos,k;
for(int i=0;i<4;i++){
if(changeId[pos][i]!=-1){
swap(temp,pos,changeId[pos][i]);
sscanf(temp,"%d",&k);
if(k==des)return tempN.step+1;
if(mymap.count(k)==0){
node tempM(k,tempN.step+1,changeId[pos][i]);
que.push(tempM);//创建一个新节点并压入队列
mymap[k]=1;
}
swap(temp,pos,changeId[pos][i]);
}
}
}
}
int main(){
int n,k,b;
scanf("%s",arr);
for(k=0;k<9;k++)
if(arr[k]=='0')break;
sscanf(arr,"%d",&n);
b=bfsHash(n,k);
printf("%d",b);
return 0;
}
启发搜索中都是直接使用的STL中的priority_queue,这里也可以尝试使用小根堆自己写。启发式搜索效率相当可怕啊,这里只是给出了一种启发式策略,还有很多启发式策略,例如从某个状态到目标状态需要移动多少步。
代码中还有一些问题,比如都没有判断如果输入状态就是目标状态的情况,空间浪费较多
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/125672.html原文链接:https://javaforall.cn