一、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=)