一、A*算法
A* 算法指的是有估价函数优化的bfs。估价函数f(x) （即从当前状态x到终点T的估计代价）需要满足f(x)<=g(x)（g(x)指的是从x到T的真实代价）。
例题1：AcWing 178.第K短路
我们知道：求单源最短路的Dijkstra算法本质上是优先队列bfs，当某个点第一次从堆中取出时，就得到了起点到这个点的最短距离。那么我们很容易得到一个引理：当某个点第k次从堆中取出时，就得到了起点到这个点的k短路。若直接利用该结论求解，时间复杂度上界为O(K(N+M)log(N+M))，会T。但是如果我们采用A*算法，实际复杂度上界的常数会远小于K。由于这题是求第K短路，我们不难想到用x到T的最短路作为估价函数f(x)的值，这样不仅满足估价函数设计的基本原则，还能顺应g(x)的变化。
代码如下:
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005,M=2e4+5;
int n,m;
int S,T,k;
int h[N],rh[N],ne[M],to[M],w[M],idx;
void add(int h[],int x,int y,int z){
ne[++idx]=h[x];
to[idx]=y;
w[idx]=z;
h[x]=idx;
}
int f[N],cnt[N];
typedef pair<int,int> PII;
bool st[N];
void dijkstra(){//在反图上跑dij来预处理出估价函数
priority_queue<PII,vector<PII>,greater<PII> > heap;
memset(f,0x3f,sizeof f);
heap.push({0,T});
f[T]=0;
while(heap.size()){
PII t=heap.top();
heap.pop();
int ver=t.second,d=t.first;
if(st[ver]) continue;
st[ver]=true;
for(int i=rh[ver];i;i=ne[i]){
int j=to[i];
if(f[j]>d+w[i]){
f[j]=d+w[i];
heap.push({f[j],j});
}
}
}
}
typedef pair<int,PII> PIP;
int dist[N];
int Astar(){
dijkstra();//计算估价函数
priority_queue<PIP,vector<PIP>,greater<PIP> > heap;
heap.push({f[S],{0,S}});
while(heap.size()){
PIP t=heap.top();
heap.pop();
int ver=t.second.second,d=t.second.first,fd=t.first;
cnt[ver]++;
if(cnt[T]==k) return d;
for(int i=h[ver];i;i=ne[i]){
int j=to[i];
if(cnt[j]<k) heap.push({d+w[i]+f[j],{d+w[i],j}});
}
}
return -1;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(h,x,y,z);
add(rh,y,x,z);//反图
}
scanf("%d%d%d",&S,&T,&k);
if(S==T) k++;//"路"最少包含一条边
printf("%d",Astar());
return 0;
}
例题2：AcWing 179.八数码
本题在排序算法一章中利用逆序对数量的奇偶性判定了八数码问题是否有解。但这题要求我们输出一个字典序最小的可行解，那么考虑使用A* 算法实现。
首先要利用逆序对的奇偶性判断询问输入数据是否有解。这样将大大提升效率。因为A*算法不能优化处理无解的情况，其复杂度会降至普通的优先队列bfs的复杂度。
这里很明显是用整个八数码图形作为状态，不断地扩展（这里需要用到STL里的有Hash表功能的unordered_map）。估价函数也比较好设计：直接取出当前状态上每一个数的坐标及其对应在最终状态上的数的坐标，计算每一个数的曼哈顿距离，求和即可。这个设计方法显然是正确的。设计思路很简单，关键在于代码实现：
P.S.:unordered_map的用法：
定义：
unordered_map<数组下标类型,数组值类型>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<unordered_map>
using namespace std;
int f(string state){
int res=0;
for(int i=0;i<9;i++){
if(state[i]!='x'){
int t=state[i]-'1';
res+=abs(i/3-t/3)+abs(i%3-t%3);
}
}
return res;
}
typedef pair<int,string> PIS;
unordered_map<string,int> dist;
unordered_map<string,bool> st;
unordered_map<string,pair<char,string>> pre;
priority_queue<PIS,vector<PIS>,greater<PIS> > heap;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char op[5]="udlr";
string bfs(string start){
string end="12345678x";
heap.push({f(start),start});
dist[start]=0;
while(heap.size()){
PIS t=heap.top();
heap.pop();
string ver=t.second;
int d=t.first;
if(ver==end) break;
if(st[ver]) continue;
st[ver]=true;
int x,y;
for(int i=0;i<9;i++){
if(ver[i]=='x'){
x=i/3,y=i%3;
break;
}
}
string source=ver;
for(int i=0;i<4;i++){
int kx=dx[i]+x,ky=dy[i]+y;
if(kx>=0 && kx<3 && ky>=0 && ky<3){
ver=source;
swap(ver[kx*3+ky],ver[x*3+y]);
if(dist.count(ver)==0 || dist[ver]>dist[source]+1){
dist[ver]=dist[source]+1;
pre[ver]={op[i],source};
heap.push({dist[ver]+f(ver),ver});
}
}
}
}
string ans;
while(end!=start){
ans+=pre[end].first;
end=pre[end].second;
}
reverse(ans.begin(),ans.end());
return ans;
}
int main(){
string c,start,seq;
for(int i=0;i<9;i++){
cin>>c;
start+=c;
if(c!="x") seq+=c;
}
int cnt=0;
for(int i=0;i<8;i++){
for(int j=i+1;j<8;j++){
if(seq[i]>seq[j]) cnt++;
}
}
if(cnt&1) puts("unsolvable");
else cout<<bfs(start)<<endl;
return 0;
}
二、IDA*
A* 算法是利用估价函数优化的优先队列bfs，那么类似地，IDA*是利用估价函数优化的迭代加深dfs。
例题1：AcWing 180.排书
这题并不确定操作次数，而且本题限定了最深的深度为5，所以必然考虑采用迭代加深dfs。估价函数的设计比较巧妙：因为每次移动至多只会改变3个位置后面的数，假设每次移动都能全部改对，那么至少也要移动[tot/3] (上取整)次（其中tot是自身后面的数是错误的，即不比自己恰好多1）。所以估价函数的值直接返回[tot/3]即可。代码如下：
#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
int n;
int a[N];
int f(){
int tot=0;
for(int i=1;i<n;i++){
if(a[i]+1!=a[i+1]) tot++;
}
return (tot+2)/3;
//上取整的写法(上取整是指当该数为非整数时，取其整数部分加一，若为整数，则不变)
}
bool dfs(int dep,int cnt){
if(cnt+f()>dep) return false;
if(cnt==dep){
if(!f()) return true;
return false;
}
int b[N];
for(int len=1;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int k=r+1;k<=n;k++){
memcpy(b,a,sizeof a);
int x=r+1,y=l;//双指针
for(y=l;x<=k;x++,y++){
a[y]=b[x];
}
for(x=l;x<=r;x++,y++){
a[y]=b[x];
}
if(dfs(dep,cnt+1)) return true;
//bool类型的递归函数一定要这样写，直接调用会TLE
memcpy(a,b,sizeof b);
}
}
}
return false;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int k=0;
while(k<5 && !dfs(k,0)) k++;
if(k>=5) puts("5 or more");
else cout<<k<<endl;
}
return 0;
}
P.S.:这类移动、插入整个区间的操作适合使用双指针算法。
例题2：AcWing 181.回转游戏
这题实在没什么好说的，太暴力了。连优化的估价函数也仅仅只是统计一下当前中心8格的众数出现次数x，直接返回8-x。难点就是在于代码实现：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int seq[25],a[9][9],num;
char ans[35];
int f(){//丑陋的估价函数
int x=0,y=0,z=0;
for(int i=3;i<=5;i++){
for(int j=3;j<=5;j++){
if(a[i][j]==1) x++;
if(a[i][j]==2) y++;
if(a[i][j]==3) z++;
}
}
return 8-max(x,max(y,z));
}
void cwork(int y,bool f){//对列操作,f=0表示向前拉，反之向后拉
if(!f){
for(int x=1;x<=7;x++){
a[x-1][y]=a[x][y];
}
a[7][y]=a[0][y];
}
else{
for(int x=7;x>=1;x--){
a[x+1][y]=a[x][y];
}
a[1][y]=a[8][y];
}
}
void rwork(int x,bool f){//对行操作
if(!f){
for(int y=1;y<=7;y++){
a[x][y-1]=a[x][y];
}
a[x][7]=a[x][0];
}
else{
for(int y=7;y>=1;y--){
a[x][y+1]=a[x][y];
}
a[x][1]=a[x][8];
}
}
bool dfs(int dep,int mdep,char lst){//存储上一步操作防止来回搜索
if(f()+dep>mdep) return false;
if(!f()){
num=a[3][3];
return true;
}
int b[9][9];
memcpy(b,a,sizeof a);
if(lst!='F'){
cwork(3,0);
ans[dep]='A';
if(dfs(dep+1,mdep,'A')) return true;
memcpy(a,b,sizeof b);
}
if(lst!='E'){
cwork(5,0);
ans[dep]='B';
if(dfs(dep+1,mdep,'B')) return true;
memcpy(a,b,sizeof b);
}
if(lst!='H'){
rwork(3,1);
ans[dep]='C';
if(dfs(dep+1,mdep,'C')) return true;
memcpy(a,b,sizeof b);
}
if(lst!='G'){
rwork(5,1);
ans[dep]='D';
if(dfs(dep+1,mdep,'D')) return true;
memcpy(a,b,sizeof b);
}
if(lst!='B'){
cwork(5,1);
ans[dep]='E';
if(dfs(dep+1,mdep,'E')) return true;
memcpy(a,b,sizeof b);
}
if(lst!='A'){
cwork(3,1);
ans[dep]='F';
if(dfs(dep+1,mdep,'F')) return true;
memcpy(a,b,sizeof b);
}
if(lst!='D'){
rwork(5,0);
ans[dep]='G';
if(dfs(dep+1,mdep,'G')) return true;
memcpy(a,b,sizeof b);
}
if(lst!='C'){
rwork(3,0);
ans[dep]='H';
if(dfs(dep+1,mdep,'H')) return true;
memcpy(a,b,sizeof b);
}
return false;
}
int main(){
while(cin>>seq[1] && seq[1]){
for(int i=2;i<=24;i++) cin>>seq[i];//丑陋的预处理过程
int cnt=1;
for(int i=1;i<=2;i++){
a[i][3]=seq[cnt++];
a[i][5]=seq[cnt++];
}
for(int i=1;i<=7;i++) a[3][i]=seq[cnt++];
a[4][3]=seq[cnt++];a[4][5]=seq[cnt++];
for(int i=1;i<=7;i++) a[5][i]=seq[cnt++];
for(int i=6;i<=7;i++){
a[i][3]=seq[cnt++];
a[i][5]=seq[cnt++];
}
int k=0;
while(k<=30 && !dfs(0,k,'.')) k++;
if(!k) puts("No moves needed");
else{
for(int i=0;i<k;i++) cout<<ans[i];
cout<<endl;
}
cout<<num<<endl;
}
return 0;
}
例题3：AcWing 182.破坏正方形
这题的基本思路是把所有正方形所拥有的火柴编号算出来，然后将问题转化为：最少要选多少根火柴可以使得每一个正方形都被选中至少一根火柴。这是一个精确覆盖（DLX）问题，但是这里不适用DLX这一数据结构，考虑直接通过搜索解决（由于精确覆盖问题没有多项式复杂度的解法，只能用搜索算法）。精确覆盖问题一般可以用IDA*解决，那么参考DLX的做法，估价函数可以这样设计：枚举当前每一个完整的正方形，将它的所有火柴都选走，但只记一次操作，直到满足条件为止。但是本题还有一个难点：预处理出所有正方形包含的火柴编号，这步较为繁杂。代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=61;
int n,m;
vector<int> square[N];
bool st[N],bst[N];
bool check(vector<int> &sq){//检查该正方形是否完整
for(int i=0;i<sq.size();i++){
if(st[sq[i]]) return false;
}
return true;
}
int f(){
int res=0;
memcpy(bst,st,sizeof st);
for(int i=0;i<m;i++){
vector<int> &sq=square[i];
if(check(sq)){
for(int j=0;j<sq.size();j++){
st[sq[j]]=true;
}
res++;
}
}
memcpy(st,bst,sizeof bst);
return res;
}
bool dfs(int dep,int mdep){
if(dep+f()>mdep) return false;
for(int i=0;i<m;i++){
vector<int> &sq=square[i];
if(check(sq)){
for(int j=0;j<sq.size();j++){
int x=sq[j];
st[x]=true;
if(dfs(dep+1,mdep)) return true;
st[x]=false;
}
return false;
}
}
return true;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(st,false,sizeof st);
m=0;
scanf("%d",&n);
int d=2*n+1;
for(int i=1;i<=n;i++){//枚举正方形的边长
for(int a=1;a+i-1<=n;a++){//枚举正方形的左上角横坐标
for(int b=1;b+i-1<=n;b++){//枚举正方形的左上角纵坐标
vector<int> &sq=square[m];
sq.clear();
for(int j=0;j<i;j++){
sq.push_back((a-1)*d+b+j);//上
sq.push_back((a+i-1)*d+b+j);//下
sq.push_back((a-1)*d+b+j*d+n);//左
sq.push_back((a-1)*d+b+j*d+n+i);//右
}
m++;
}
}
}
int k;
scanf("%d",&k);
while(k--){
int x;
scanf("%d",&x);
st[x]=true;
}
int dep=0;
while(!dfs(0,dep)) dep++;
printf("%d\n",dep);
}
return 0;
}
例题4：AcWing 193.算乘方的牛
这题标签是A*，但是用IDA*更好实现：我们考虑将乘方运算转化为指数运算，每次相乘除相当于相加减。且两个变量的存放顺序对最终结果没有影响，所以代码就变得很简洁明了了：
#include<iostream>
#include<queue>
using namespace std;
int P,dep;
int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}
bool dfs(int step,int a,int b){//限制了a>b
if(step==dep) return a==P;
if(a<<(dep-step)<P) return false;//相当于估价函数
if(P%gcd(a,b)) return false;//好剪枝，没有想到
int x=2*a,y=2*b,z=a+b,u=a-b;
if(dfs(step+1,x,a)) return true;
if(dfs(step+1,x,b)) return true;
if(dfs(step+1,y,b)) return true;
if(dfs(step+1,z,a)) return true;
if(dfs(step+1,z,b)) return true;
if(dfs(step+1,a,u)) return true;
if(dfs(step+1,max(y,a),min(y,a))) return true;
if(dfs(step+1,max(u,b),min(u,b))) return true;
return false;
}
int main(){
cin>>P;
while(!dfs(0,1,0)) dep++;
cout<<dep;
return 0;
}
例题5：AcWing 194.涂满它！
这题是连通块类的问题，考虑用不同的数来表示各个点的状态：0表示与连通块不相邻，1表示已联通，2表示与连通块相邻但是未联通。这样方便处理每一步的扩展情况：
bool dfs(int dep,int mdep){
if(dep+f()>mdep)return false;
if(!f()) return true;
int bst[N][N];
memcpy(bst,st,sizeof st);
for(int t=0;t<=5;t++){//枚举相同颜色
bool flag=false;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(col[i][j]==t && st[i][j]==2){
flag=true;
fill(i,j,t);
//填充颜色为t与连通块相邻的部分
}
}
}
if(flag && dfs(dep+1,mdep)) return true;
memcpy(st,bst,sizeof st);
}
return false;
}
fill函数的实现：
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void fill(int x,int y,int z){
st[x][y]=1;
for(int i=0;i<4;i++){
int kx=x+dx[i],ky=y+dy[i];
if(kx<=0 || kx>n || ky<=0 || ky>n || st[kx][ky]==1) continue;
if(col[kx][ky]==z) fill(kx,ky,z);
else st[kx][ky]=2;
}
}
估价函数的思路：比较好想，直接用剩余的不同种类的颜色数量作为估价函数值即可。
例题6：AcWing 195.骑士精神
这题实际上非常简单：我们只要一开始想到一个转换：把骑士的跳动等效为空格的跳动，所以实际上这个问题变成了一个点在网格上不停地跳动，使得初始状态变为最终状态。那么可以想到利用估价函数，做一个IDA*算法。估价函数的设计也很简单：用当前与目标状态不符的点的个数作为估价函数值即可。代码如下：
#include<iostream>
#include<cstdio>
using namespace std;
const int N=6;
char a[N][N];
char tar[N][N]={'1','1','1','1','1',
'0','1','1','1','1',
'0','0','*','1','1',
'0','0','0','0','1',
'0','0','0','0','0'};
int f(){
int res=0;
for(int i=0;i<5;i++){
for(int j=0;j<5;j++)
if(a[i][j]!=tar[i][j] && a[i][j]!='*') res++;
}
return res;
}
bool check(){
for(int i=0;i<5;i++){
for(int j=0;j<5;j++)
if(a[i][j]!=tar[i][j]) return false;
}
return true;
}
int dx[8]={-2,-2,-1,1,2,2,1,-1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
bool dfs(int dep,int mdep,int sx,int sy){
if(dep+f()>mdep) return false;
if(dep==mdep) return check();
for(int i=0;i<8;i++){
int x=sx+dx[i],y=sy+dy[i];
if(x<0 || x>=5 || y<0 || y>=5) continue;
swap(a[sx][sy],a[x][y]);
if(dfs(dep+1,mdep,x,y)) return true;
swap(a[sx][sy],a[x][y]);
}
return false;
}
int main(){
int T;
cin>>T;
while(T--){
for(int i=0;i<5;i++) cin>>a[i];
int x,y;
for(int i=0;i<5;i++){
for(int j=0;j<5;j++)
if(a[i][j]=='*'){
x=i,y=j;
}
}
int dep=0;
while(dep<=15 && !dfs(0,dep,x,y)) dep++;
if(dep>15) puts("-1");
else cout<<dep<<endl;
}
return 0;
}
总结：启发式搜索其实相当于一个剪枝，可以及时地剪去不可能的状态，使得搜索的规模大为减小。但是我们在考虑估价函数时，不仅要考虑其剪枝规模大小，亦要考虑其时间复杂度，不能入不敷出。
![python学习——阿里云天池龙珠计划（python训练营）——task01注释运算符位运算条件语句循环语句for循环异常处理结尾[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)