题意简述
有12个旋钮，每个旋钮开始时处于状态 ）。
单向BFS评测记录
超时的主要原因是搜索树过于庞大，而我们会发现本题对比图，应该可以便于理解。
可以看到双向 ），也可以继续往下看。
在 \(A*\) 算法中，我们要利用当前状态的信息对状态进行评价，以此来决定下一次的操作，极大地限制了搜索树的生长。首先介绍一个特别的估价函数 \(F^*\) 来表示：\(F^*(x)=g^* (x)+h^*(x)\) 。其中 \(g^* (x)\) 表示从初始状态到当前状态所付出的最小代价（在本题中意义为操作步数），而 \(h^*(x)\) 是从当前状态到目标状态走最佳路径所付出的代价。在实际代码中我们使用的其实是 \(F(x)=g (x)+h(x)\) ，因为我们实际上是不知道这个加星后的函数的，但是我们可以通过一些限制，让不加星的函数也可以在一定范围内求解出正确答案;
- \(g(x)\) 是对 \(g^*(x)\) 的估计，且 \(g(x)>0\) ,在代码中我们记录的就是步数；
- \(h(x)\) 是 \(h^*(x)\) 的下界，即对任意状态均有 \(h(x)≤h^*(x)\)。在代码中我们定义为 \(12\) 个旋钮在不考虑牵连时都转到 \(1\) 要多少步，再除以 \(2\) ,这样就可以保证 \(h(x)\) 肯定会比实际要转的次数要少（一次操作恰好就可以让两个旋钮都向目标状态转一次，而实际上可能会让某个旋钮转过目标状态，从而要转更多次数），
\(h(x)\) 是一个比较玄学的东东，没有唯一的定义，不同的定义可能会导致程序执行效率和结果不同，这题中你还可以乘一个系数给他，能明显加快运行效率。经过笔者多次测试，发现给 \(h\) 乘上系数从 \(1.1\) ~ \(2.3\) 都能 \(AC\) 这道题，但是乘 \(2.4\) 时会 \(WA\) 掉一个点。变化趋势是这个系数越大，跑得越快，最大的点可以跑进 \(100ms\) 。这是因为系数越大越接近真实值 \(h^*(x)\)，但是更大的系数不能保证一定可以得到最优解。
代码实现类似 \(Dijkstra\) 算法，定义一个结构体存状态和这个状态对应的估价函数值 \(F\) 。每次从小根堆中取出 \(F\) 最小的状态进行转移，存状态和转移状态的操作和上面双向 \(BFS\) 相同，这里直接给出代码。
\(Code:\)
#include <bits/stdc++.h>
using namespace std;
#define For(a,sta,en) for(int a = sta;a <= en;a++)
inline int read(){
int sum = 0,fu = 1;char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') fu = -1;ch = getchar();}
while(isdigit(ch)) { sum = (sum<<1)+(sum<<3)+(ch^48);ch =getchar();} return sum * fu;
}
const int N = 1<<24;
int g[N],nxt[14][6],fa[N],ans[30],choice[N];
struct node{
int state; //状态
double F; //状态对应估价函数值
node(int s):state(s){ //构造函数，冒号后面部分相当于 state = s;
double h = 0;
F = 0;
For(i,0,11) if((s>>(i<<1))&3) h += 4 - ((s >> (i << 1)) & 3); //计算不处在状态1的旋钮的对应的h值
F = h / 2 + g[s]; //可以在h/2前乘一个玄学系数
}
bool operator<(const node &y) const{
return F > y.F; //估价函数值小的放前面
}
};
priority_queue<node>q;
int main(){
int button,Start = 0;
For(i,0,11){
button = read(); //读入第i+1个旋钮状态
Start |= (button - 1) << (i << 1); //记录初始状态
For(j,0,3) nxt[i][j] = read()-1;
}
q.push(node(Start)); //调用构造函数，顺便计算出估价函数值
g[Start] = 0;
int flag = 1;
while(!q.empty()&&flag){
int state = q.top().state;
q.pop();
int si,sNxt,nx,nextState;
For(i,0,11){
si = (state>>(i<<1))&3;
nx = nxt[i][si];
sNxt = (state>>(nx<<1))&3;
nextState = state ^ (si << (i << 1)) ^ (((si + 1) & 3) << (i << 1)) ^ (sNxt << (nx << 1)) ^ (((sNxt + 1) & 3) << (nx << 1));
//如果没有访问过就可以转移新状态了
if(!g[nextState]){
g[nextState] = g[state] + 1;
fa[nextState] = state; //用于回溯
choice[nextState] = i + 1;
if(nextState == 0) { flag = 0;break;} //到达目标状态
q.push(node(nextState));
}
}
}
int cnt = 0,state = 0;
while(state != Start){
ans[++cnt] = choice[state];
state = fa[state];
}
printf("%d\n",cnt);
for(int i = cnt;i;i--) printf("%d ",ans[i]);
return 0;
}
对于 \(A^*\) 算法我可能有些地方描述不够严谨，如果有错误的地方欢迎指出。做完这道题建议去做一下 P1379 八数码难题 ,可以同时用单向 \(BFS\) ，双向 \(BFS\) ，\(A^*\) 和 \(IDA^*\) 做这道题，如果每个方法都写一下一定受益良多。