这道题首先会想到搜索…
但面对指数级别的时间复杂度....
考虑优化.
这题可以IDA*解决.
1.考虑估价函数:
直接记录目标的8个格子中出现次数最多的数字出现的次数,记为MAX.
由于每次操作最多改变一个数字,因此我们至少需要8-MAX次才能将其变为目标状态.
因此估价函数可设为8-MAX.
2.考虑剪枝:
记录每一种操作的”逆”操作,搜索时要尽量避开.
至于字典序最小…
都是老套路了....
另外,为了方便写代码.
我们可以直接将每种操作看做数字,输出时直接处理即可.
例如:将操作A看做0,输出时直接输出1+’A’即可.
时间复杂度 $O(指数级别)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int op[8][7]={//记录每一种操作对应的数字坐标
{0,2,6,11,15,20,22},
{1,3,8,12,17,21,23},
{10,9,8,7,6,5,4},
{19,18,17,16,15,14,13},
{23,21,17,12,8,3,1},
{22,20,15,11,6,2,0},
{13,14,15,16,17,18,19},
{4,5,6,7,8,9,10}
};
const int opposite[8]={5,4,7,6,1,0,3,2};//记录每一种操作的逆操作
const int center[8]={6,7,8,11,12,15,16,17};//记录目标的八个格子的数字坐标
int path[100],q[25];
int f()//估价函数
{
int sum[4]={0};
for(int i=0;i<8;i++)//记录目标八个格子中每个数字出现的次数
sum[q[center[i]]]++;
int MAX=0;
for(int i=1;i<=3;i++)//找出出现次数最多的数的个数
MAX=max(MAX,sum[i]);
return 8-MAX;
}
void operate(int x)//执行当前操作
{
int t=q[op[x][0]];
for(int i=0;i<6;i++)//每个格子向后移动一个
q[op[x][i]]=q[op[x][i+1]];
q[op[x][6]]=t;
}
bool dfs(int depth,int max_depth,int last)
{
if(depth+f()>max_depth)//当前状态加上预期步数大于最大可扩展深度
return false;//立即返回false
if(!f())
return true;
for(int i=0;i<8;i++)
if(opposite[i]!=last){//当前操作不是上一步操作的逆操作
operate(i);//执行当前操作
path[depth]=i;//记录路径
if(dfs(depth+1,max_depth,i))//如果搜索到答案
return true;//返回true
operate(opposite[i]);//回溯
}
return false;//无解
}
int main()
{
while(cin>>q[0]&&q[0]){
for(int i=1;i<24;i++)
scanf("%d",&q[i]);
int depth=0;//跌代加深
while(!dfs(0,depth,-1))//当前深度无法得到答案
depth++;//扩展深度
if(!depth)
printf("No moves needed");
else{
for(int i=0;i<depth;i++)//输出路径
printf("%c",(path[i]+'A'));
}
printf("\n%d\n",q[6]);//输出目标八个格子的数字
}
return 0;
}