紫书例题。
首先附上我第一次bfs+剪枝TLE的版本：
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
const int b[][]= {
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
};
const int md[]= {,,,,,,,};
void rot(int* c,int x) {
const int* bb=b[x];
for(int i=; i<; ++i)swap(c[bb[i]],c[bb[i+]]);
}
void enc(int* c,ll& x) {
x=;
for(int i=; i>=; --i)x=x*+c[i];
}
void dec(int* c,ll x) {
for(int i=; i<; ++i)c[i]=;
for(int i=; i<; ++i)c[i]=x%,x/=;
}
int ok(int* c) {
for(int i=; i<; ++i)if(c[md[i]]!=c[md[i+]])return false;
return true;
}
map<ll,int> d;
vector<ll> t;
int c[N],cc[N],s[N],mi;
ll ss; void bfs1() {
mi=inf;
d.clear();
t.clear();
queue<ll> q;
q.push(ss),d[ss]=;
while(!q.empty()) {
ll u=q.front();
q.pop();
dec(c,u);
if(ok(c)) {
mi=min(mi,d[u]);
t.push_back(u);
}
if(d[u]>=mi)continue;
for(int i=; i<; ++i) {
memcpy(cc,c,sizeof c);
rot(cc,i);
ll v;
enc(cc,v);
if(!d.count(v)) {
d[v]=d[u]+;
q.push(v);
}
}
}
} void bfs2() {
d.clear();
queue<ll> q;
for(ll i:t)q.push(i),d[i]=;
while(!q.empty()) {
ll u=q.front();
q.pop();
if(d[u]==mi)continue;
dec(c,u);
for(int i=; i<; ++i) {
memcpy(cc,c,sizeof c);
rot(cc,i);
ll v;
enc(cc,v);
if(!d.count(v)) {
d[v]=d[u]+;
q.push(v);
}
}
}
} void prans() {
ll u;
for(u=ss; d[u];) {
dec(c,u);
for(int i=; i<; ++i) {
memcpy(cc,c,sizeof c);
rot(cc,i);
ll v;
enc(cc,v);
if(d.count(v)&&d[v]==d[u]-) {
printf("%c",i+'A');
u=v;
}
}
}
dec(c,u);
printf("\n%d\n",c[md[]]+);
} int input() {
for(int i=; i<; ++i)if(scanf("%d",&s[i])!=)return ;
return ;
} int main() {
while(input()) {
for(int i=; i<; ++i)s[i]--;
enc(s,ss);
bfs1();
bfs2();
prans();
}
return ;
}
这个版本TLE的原因是，如果直接bfs的话，总状态数为$C(24,8)*C(16,8)=9465511770$，显然太大了，即使加了剪枝状态数依然很大，妥妥地TLE。
但如果预先假定一个数是正确答案，那么剩下的两个数就没有区别了，所以状态可以用0和1来表示，这样总状态数就缩小到了$C(24,8)=735471$，在可接受范围内了。把原状态分解成三个子状态跑一遍bfs即可得到正确结果。但是如果对每个输入都跑一遍bfs的话依然会TLE，而我们发现对于每组输入，所有的状态表示的含义都是一样的，因此可以预先对末状态跑一遍bfs，记录下所有状态到末状态的最短距离，这样每接受一组输入都可以直接通过bfs树得到路径。
bfs的版本：(状态的保存用了哈希表，用stl中的map应该也可以)
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
const int b[][]= {
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
};
int t[]= {,,,,,,,,,,,,,,,,,,,,,,};
void rot(int* c,int x) {
const int* bb=b[x];
for(int i=; i<; ++i)swap(c[bb[i]],c[bb[i+]]);
}
void enc(int* c,int& x) {
x=;
for(int i=; i>=; --i)x=x<<|c[i];
}
void dec(int* c,int x) {
for(int i=; i<; ++i)c[i]=;
for(int i=; i<; ++i)c[i]=x&,x>>=;
}
struct Hashmap {
static const int N=1e6+;
static const int mod=1e6+;
int hd[mod],nxt[N],tot,key[N],val[N];
int H(int x) {return (x+)%mod;}
void clear() {tot=; memset(hd,-,sizeof hd);}
int count(int x) {
for(int u=hd[H(x)]; ~u; u=nxt[u])if(key[u]==x)return ;
return ;
}
int& operator[](int x) {
int h=H(x);
for(int u=hd[h]; ~u; u=nxt[u])if(key[u]==x)return val[u];
nxt[tot]=hd[h],key[tot]=x,val[tot]=,hd[h]=tot;
return val[tot++];
}
} d; int c[N],cc[N],s[N],ss,tt,mi,ans;
string str1,str2; void bfs() {
d.clear();
queue<int> q;
q.push(tt),d[tt]=;
while(!q.empty()) {
int u=q.front();
q.pop();
dec(c,u);
for(int i=; i<; ++i) {
memcpy(cc,c,sizeof c);
rot(cc,i);
int v;
enc(cc,v);
if(!d.count(v)) {
d[v]=d[u]+;
q.push(v);
}
}
}
} int input() {
for(int i=; i<; ++i)if(scanf("%d",&s[i])!=)return ;
return ;
} int main() {
enc(t,tt);
bfs();
while(input()) {
mi=inf;
for(int i=; i<=; ++i) {
for(int j=; j<; ++j)c[j]=s[j]==i?:;
int u;
enc(c,u);
mi=min(mi,d[u]);
}
str1="Z";
for(int i=; i<=; ++i) {
for(int j=; j<; ++j)c[j]=s[j]==i?:;
int u;
enc(c,u);
if(d[u]==mi) {
str2.clear();
while(u!=tt) {
dec(c,u);
for(int j=; j<; ++j) {
memcpy(cc,c,sizeof c);
rot(cc,j);
int v;
enc(cc,v);
if(d.count(v)&&d[v]==d[u]-) {
str2.push_back(j+'A');
u=v;
break;
}
}
}
if(str2<str1)str1=str2,ans=i;
}
}
if(mi==)printf("No moves needed\n");
else printf("%s\n",str1.c_str());
printf("%d\n",ans);
}
return ;
}
另外一种方法是IDA*。看了看网上的题解，基本都是IDA*的做法。IDA*还是很有参考价值的。
设g(n)为从初始状态到当前状态n所需步数，h(n)为当前状态n到目标状态至少所需步数，则g(n)+h(n)>maxdep时剪枝。显然h(n)可以用中心格点中1,2,3中的最大个数与8的差来表示，这样就不用保存状态，直接搜就行了。IDA*特别适用于这种bfs树的宽度较大而深度较小的搜索问题。（可以用bfs跑一遍试试，会发现在用01状态表示法的情况下，最坏情况下达到目标状态也仅需14步。）
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
const int b[][]= {
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
};
const int md[]= {,,,,,,,};
void rot(int* c,int x,int f) {
const int* bb=b[x];
if(f==)for(int i=; i<; ++i)swap(c[bb[i]],c[bb[i+]]);
else for(int i=; i>=; --i)swap(c[bb[i]],c[bb[i+]]);
}
int count(int* c) {
int cnt[]= {};
for(int i=; i<; ++i)cnt[c[md[i]]-]++;
return max(cnt[],max(cnt[],cnt[]));
}
int s[N],ans;
char str[N]; bool dfs(int dep,int mxd) {
int cnt=count(s);
if(cnt==) {ans=s[md[]]; str[dep]='\0'; return ;}
if(-cnt>mxd-dep)return ;
for(int i=; i<; ++i) {
rot(s,i,);
if(dfs(dep+,mxd)) {str[dep]=i+'A'; return ;}
rot(s,i,-);
}
return ;
} void IDA() {
for(int mxd=;; ++mxd)if(dfs(,mxd))break;
if(str[])puts(str);
else puts("No moves needed");
printf("%d\n",ans);
} int input() {
for(int i=; i<; ++i)if(scanf("%d",&s[i])!=)return ;
return ;
} int main() {
while(input())IDA();
return ;
}
怎么样，代码是不是比bfs的版本简洁多了？而且速度出乎意料地比bfs还要快很多。
感觉IDA*就像暴搜+剪枝，bfs就像dp，具体该用哪个还得靠自己斟酌斟酌~~