例题

可达性问题

具体见书P95。

给定一个N个点，M条边的有向无环图，问每个点直接或间接可到达的点的数量。

书中有详细介绍，这里就不再赘述了，简而言之就是 拓扑排序+状态压缩 。

#include
#include
#include
#include
#include
#include
#include
#include
#define N 30030
#define M 30030
using namespace std;

int n,m,f[N],side[N];
int head[N],cnt=0;
struct node{
	int to,next;
}edge[M];

vectorpath;
bitsetb[N];
queueq;

void addedge(int x,int y){
	cnt++;
	edge[cnt].next=head[x];
	edge[cnt].to=y;
	head[x]=cnt;
	return;
}

void topo(){
	for(int i=1;i<=n;i++){
		if(!side[i]) q.push(i);
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		path.push_back(now);
		for(int i=head[now];i;i=edge[i].next){
			int y=edge[i].to;
			if(!--side[y]) q.push(y);
		}
	}
	return;
}

int main(){
	memset(side,0,sizeof(side));
	scanf("%d %d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d %d",&u,&v);
		addedge(u,v);
		side[v]++;
	}
	topo();
	for(int i=path.size()-1;i>=0;i--){
		int u=path[i];
		b[u][u]=1;
		for(int j=head[u];j;j=edge[j].next){
			int v=edge[j].to;
			b[u]|=b[v];
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",b[i].count());
	}
	return 0;
}

二、深度优先搜索及剪枝

DFS简述

• 其搜索方式为，在某个状态A，找到一个可以由此状态转移到的状态B，然后转移到状态B，遍历完B所有的后续状态后，返回状态A，再寻找A的另一个可转移状态C，如此往复，直至所有状态被遍历完。

• 更通俗地说，即在遍历时，优先选择一条路，往搜索树的深层遍历，当不能继续深入时则返回上一层，选择另一个岔路遍历。

代码框架大概是这个样子：

void dfs(...){//搜索状态
    if(...) return;//终止条件及剪枝
    for(...){//遍历子节点
        ...//进入下一层之前的处理
        dfs(...)//进入下一层
        ...//回溯
    }
    return;//结束
}

因为基本知识就这么多，主要依靠例题来讲解。

DFS例题

小猫爬山

CH2201 小猫爬山

主要思路书上讲的很详细了，这里提一下两个剪枝：

• 最优化剪枝：一旦目前的 \(cnt>ans\) ，果断 \(return\) 。
• 优化搜索顺序：重的猫一定比轻的猫要占空间，所以按照重量递减排序。

代码如下：

#include
#include
#include
#include
#include
#include
#include
#define N 25
#define maxd 999999999
using namespace std;

int n,c[N],m;
int cab[N],ans=maxd;

void dfs(int now,int cnt){
    if(now>n){
        ans=min(ans,cnt);
        return;
    }
    if(cnt>=ans) return;//剪枝1

    for(int i=1;i<=cnt;i++){
        if(c[now]+cab[i]<=m){
            cab[i]+=c[now];
            dfs(now+1,cnt);
            cab[i]-=c[now];
        }
    }
    cab[cnt+1]=c[now];
    dfs(now+1,cnt+1);
    cab[cnt+1]=0;
    return;
}

bool cmp(int a,int b){
    return a>b;
}

int main(){
     scanf("%d %d",&n,&m);
     for(int i=1;i<=n;i++) scanf("%d",&c[i]);
     sort(c+1,c+n+1,cmp);//剪枝2
     dfs(1,0);
     printf("%d\n",ans);
     //system("pasue");
     return 0;
}

Sudoku

POJ2676 Sudoku

具体思路同样被讲的很详细了，这里同样不再赘述。（书上讲的很多优化我没有用到，但还是能过的）

代码见下：

#include
#include
#include
#include
#include
using namespace std;

int a[20][20];
bool h[20][20],l[20][20],g[20][20];
bool flag;

int find(int x,int y){
	return (x-1)/3*3+(y-1)/3+1;
}

void print(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			printf("%d",a[i][j]);
		}
		printf("\n");
	}
	flag=true;
}

void dfs(int x,int y){
	if(flag) return;
	if(a[x][y]){
		if(x==9 && y==9) print();
		if(y==9) dfs(x+1,1);
		else dfs(x,y+1);
	}
	else{
		for(int i=1;i<=9;i++){
			if(h[x][i]&&l[y][i]&&g[find(x,y)][i]){
				a[x][y]=i;
				h[x][i]=l[y][i]=g[find(x,y)][i]=false;
				if(x==9&&y==9) print();
				if(y==9) dfs(x+1,1); else dfs(x,y+1);
				a[x][y]=0;
				h[x][i]=l[y][i]=g[find(x,y)][i]=true;
			}
		}
	}
	return;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
        flag=false;
        memset(h,true,sizeof(h));
        memset(l,true,sizeof(l));
        memset(g,true,sizeof(g));
	    for(int i=1;i<=9;i++){
		    for(int j=1;j<=9;j++){
			    scanf("%1d",&a[i][j]);
			    if(a[i][j]==0) continue;
			    h[i][a[i][j]]=false;
		        l[j][a[i][j]]=false;
			    g[find(i,j)][a[i][j]]=false;
		    }
	    }
	    dfs(1,1);
	}
	return 0;
}

剪枝

搜索的灵魂，暴力的核心（只要剪枝写得好，直接暴力踩标算）

剪枝：缩小搜索规模以达到时间上的优化，因类似于剪掉搜索树的枝条，所以形象地称为剪枝。

常见的剪枝方法如下：

1. 优化搜索顺序：由于每种搜索顺序所形成的搜索树形态各异，规模大小也相去甚远，例如：

   • 小猫爬山问题：按照重量递减排序。

2. 排除等效冗余：如果能确定两颗搜索树是等效的，显然只需要搜索其中一颗。

3. 可行性剪枝：如果发现前方是“死胡同”，就直接回头。例如某些题目的范围限制是一个区间。

4. 最优化剪枝：如果当前花费的代价已经 \(>ans\) ，无论后面再怎么优秀，都不可能刷新答案。

5. 记忆化：如果一颗子树的值需要重复利用多次，最好的方法是直接把这个值给记录下来。

   • 如果你丧心病狂地拿 DFS 写斐波那契数列，你一定深有体会。

接下来让我们用几道例题来感受剪枝的妙用。

剪枝例题

Sticks

P1120 小木棍

具体剪枝思路看书。

代码如下:

#include
#include
#include
#include
#include
using namespace std;

int n,cnt,len,a[70];
bool use[70];

bool dfs(int stick,int cab,int last){
	if(stick>cnt) return true;
	if(cab==len) return dfs(stick+1,0,1);
	int fail=0;
	for(int i=last;i<=n;i++){//剪枝1
		if(!use[i] && cab+a[i]<=len && a[i]!=fail){
			use[i]=true;
			if(dfs(stick,cab+a[i],i+1)) return true;
			fail=a[i];//剪枝2
			use[i]=false;
			if(cab+a[i]==len || cab==0) return false;//剪枝3、4
		}
	}
	return false;
}

bool cmp(int a,int b){
	return a>b;
}

int main(){
	int o,val=0,sum=0;
	scanf("%d",&o);
	for(int i=1;i<=o;i++){
		int p;
		scanf("%d",&p);
		if(p<=50){
			a[++n]=p;
			sum+=p;
			val=max(val,p);
		}
	}
	sort(a+1,a+n+1,cmp);//优化搜索顺序
	for(len=val;len<=sum;len++){
		if(sum%len) continue;
		memset(use,false,sizeof(use));
		cnt=sum/len;
		if(dfs(1,0,1)) break;
	}
	printf("%d\n",len);
	return 0;
}

生日蛋糕

P1731 生日蛋糕

搜索鼻祖，GY说：“你会了生日蛋糕，你就会了剪枝。”

说了很多次的话不想重复。

#include
#include
#include
#include
#include
#define maxn 2147483647
using namespace std;

int n,m,mins[20],minv[20],ans=maxn;

void dfs(int s,int v,int step,int r,int h){
	if(step==0){
		if(v==n) ans=min(ans,s);
		return;
	}
	//possible剪枝
	if(s+mins[step-1]>ans) return;
	if(v+minv[step-1]>n) return;
	//best剪枝
	if(s+2*(n-v)/r>=ans) return;
	//next
	for(int i=r-1;i>=step;i--){
		if(m==step) s=i*i;
		int maxh=min(h-1,(n-v-minv[step-1])/(i*i));
		for(int j=maxh;j>=step;j--){
			dfs(s+2*i*j,v+i*i*j,step-1,i,j);
		}
	}
	return;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		mins[i]=mins[i-1]+2*i*i;//预处理最小面积
		minv[i]=minv[i-1]+i*i*i;//预处理最小体积
	}
	
	dfs(0,0,m,n+1,n+1);
	
	if(ans==maxn){
		printf("0\n");
		return 0;
	}
	printf("%d\n",ans);
	return 0;
} 

三、迭代加深及DFS常见优化

迭代加深

DFS有一个缺陷，就是每次必须选定一个分支，直到终点才回溯。

假设每个节点的分支非常多，答案在很浅的节点上，而一开始就选错了分支，你就GG了。

所以就有了迭代加深（ID）算法，具体流程如下：

• 迭代加深以dfs为基础，本质上仍然是dfs。

• 从1开始，从小到大枚举一个深度界限d。

• 枚举d的同时进行dfs，并规定此次dfs的深度不能超过d。

• 当dfs搜索到目标时停止，此时的d值就是能够搜索到答案的最小深度。

你可能会很奇怪，每一次迭代不都重复计算了很多节点吗？这不会T吗？

答案是，即使重复搜索，每层的节点都是指数级增长，即使重复搜索 $$1$$~$$d-1$$ ，其时间消耗可能还不及第 \(d\) 层。

所以不用担心重复的问题。

总而言之：当搜索树规模随着层数的深入而增长很快，而且答案在一个较浅层的节点，就可以用ID算法。

例题

岳麓山打水

岳麓山打水 VIJOS1159

好像是模板题，自己理解吧：

#include
#include
#include
#include
#include
#define maxn 20020
using namespace std;

int n,m,a[maxn],p[maxn],d;
bool f[maxn];

bool chck(){
	memset(f,false,sizeof(f));
	f[0]=true;
	for(int i=1;i<=d;i++){
		for(int j=0;j+p[i]<=m;j++){
			if(f[j]) f[j+p[i]]=true; 
		}
	}
	return f[m];
}

bool dfs(int x,int y){
	if(x>d) return (chck());
	for(int i=y;i<=n;i++){
		p[x]=a[i];
		if(dfs(x+1,i+1)) return true;
	}
	return false;
}

int main(){
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	
	for(d=1;;d++){
		if(dfs(1,1)) break;
	}
	printf("%d ",d);
	for(int i=1;i<=d;i++) printf("%d ",p[i]);
	return 0;
} 

双向搜索

简单说就是从初态和终态出发各搜索一般状态，产生两棵深度减半的搜索树，在中间交汇，组成最终答案。

有效地避免了层数过深时的大规模增长，但前提是已知目标状态。

其实很好写，例题就不在赘述了。

四、广度优先搜索及其优化

广度优先搜索

在之前就已经讲述了图的BFS遍历，如果我们把搜索树看成一张图，在遍历时顺便做一些处理，这就变成了BFS。

很简单的介绍，主要通过例题来加强认识吧。

例题

Bloxorz

Bloxorz POJ3322

这是一道经典的 走地图 类的问题，这类问题可以用BFS来解决（具体见书）

因为书上有标程，而且还写得挺好，这里皆采用书上方法实现：

#include
#include
#include
#include
#include
#define maxn 550
using namespace std;

struct node{
	int x,y,lin;
}st,ed;
int n,m,f[maxn][maxn][5];//0直立，1横放（左为x,y），2竖放（上为x,y） 
char s[maxn][maxn];
int dx[5]={0,0,-1,1};//左右上下 
int dy[5]={-1,1,0,0};
int next_x[3][4]={{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
int next_y[3][4]={{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
int next_lin[3][4]={{1,1,2,2},{0,0,1,1},{2,2,0,0}};
queueq;

bool in(int x,int y){
	return x>=1&&x<=n&&y>=1&&y<=m;
}

void pre_work(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='O'){ed.x=i;ed.y=j;ed.lin=0;s[i][j]='.';}
			else if(s[i][j]=='X'){
				//bool flag=false;
				for(int k=0;k<=3;k++){
					int x=i+dx[k];
					int y=j+dy[k];
					if(in(x,y)&&s[x][y]=='X'){
						//flag=true;
						st.x=min(i,x);st.y=min(j,y);
						st.lin=k<2?1:2;
						s[i][j]=s[x][y]='.';
						break;
					}
				}
				if(s[i][j]=='X'){st.x=i;st.y=j;st.lin=0;}
			}
	return;
}

bool able(node next){
	if(!in(next.x,next.y)) return false;
	if(s[next.x][next.y]=='#') return false;
	if(next.lin==0&&s[next.x][next.y]!='.') return false;
	if(next.lin==1&&s[next.x][next.y+1]=='#') return false;
	if(next.lin==2&&s[next.x+1][next.y]=='#') return false;
	return true;
}

int bfs(){
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<=2;k++)
			f[i][j][k]=-1;
		}
	}
	f[st.x][st.y][st.lin]=0;
	q.push(st);
	
	while(!q.empty()){
		node now=q.front();q.pop();
		for(int i=0;i<=3;i++){
			node next;
			next.x=now.x+next_x[now.lin][i];
			next.y=now.y+next_y[now.lin][i];
			next.lin=next_lin[now.lin][i];
			if(!able(next)) continue;
			if(f[next.x][next.y][next.lin]==-1){
				f[next.x][next.y][next.lin]=f[now.x][now.y][now.lin]+1;
				q.push(next);
				if(ed.x==next.x&&ed.y==next.y&&ed.lin==next.lin) return f[next.x][next.y][next.lin];
			}
		}
	}
	return -1;
}

int main(){
	while(~scanf("%d %d",&n,&m)&&n){
		for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
		pre_work();
		//printf("%d %d %d\n%d %d %d\n",st.x,st.y,st.lin,ed.x,ed.y,ed.lin);
		int ans=bfs();
		if(ans==-1) printf("Impossible\n");else printf("%d\n",ans);
	}
	return 0;
}

好像码量还挺大

Pushing Boxes

Pushing Boxes POJ1475

同样是 走地图 式的题目，但是好恶心！（思路书上有）

#include
#include
#include
#include
#include
#include
#include
#define maxn 25
using namespace std;

int n,m,px,py,bx,by;
char a[maxn][maxn];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
char box_path[5]="SNEW";
char man_path[5]="snew";
bool box_vis[maxn][maxn];
bool man_vis[maxn][maxn];
string pathman;
struct man{
	int x,y;
	string path;	
};
struct box{
	int x,y;
	int mx,my;
	string path;
};

bool in(int x,int y){
	return x>=1&&x<=n&&y>=1&&y<=m;
}

bool bfs_man(int cantx,int canty,int sx,int sy,int ex,int ey){
	memset(man_vis,0,sizeof(man_vis));
	man p;
	pathman="";
	if(ex<1||ex>n||ey<1||ey>m) return false;
	p.x=sx;p.y=sy;p.path="";
	man_vis[sx][sy]=true;
	queueq;
	q.push(p);
	
	while(!q.empty()){
		man now=q.front();
		q.pop();
		if(now.x==ex&&now.y==ey){
			pathman=now.path;
			return true;
		}
		for(int i=0;i<=3;i++){
			int gx=now.x+dx[i];
			int gy=now.y+dy[i];
			if(gx==cantx && gy==canty) continue;
			if(in(gx,gy)&&!man_vis[gx][gy]&&a[gx][gy]!='#'){
				man_vis[gx][gy]=true;				
				p.x=gx;p.y=gy;
				p.path=now.path+man_path[i];
				q.push(p);
			}
		}
	}
	return false;
}

void bfs_box(){
	memset(box_vis,0,sizeof(box_vis));
	queueq;
	box p;
	p.x=bx;
	p.y=by;
	p.mx=px;
	p.my=py;
	p.path="";
	box_vis[bx][by]=true;
	q.push(p);
	
	while(!q.empty()){
		box now=q.front();
		q.pop();
		for(int i=0;i<=3;i++){
			int gx=now.x+dx[i];
			int gy=now.y+dy[i];
			if(in(gx,gy)&&a[gx][gy]!='#'&&!box_vis[gx][gy]&&
			bfs_man(now.x,now.y,now.mx,now.my,now.x-dx[i],now.y-dy[i])){
				box_vis[gx][gy]=true;
				p.x=gx;p.y=gy;
				p.mx=now.x;p.my=now.y;
				p.path=now.path+pathman+box_path[i];
				if(a[gx][gy]=='T'){
					cout << p.path << endl;
					return;
				}
				q.push(p);
			}
		}
	}
	printf("Impossible.\n");
	return;
}

int main(){
    int cnt=0;
	while(~scanf("%d %d",&n,&m)&&n){
		for(int i=1;i<=n;i++){
			scanf("%s",a[i]+1);
			for(int j=1;j<=m;j++){
				if(a[i][j]=='S'){
					px=i;py=j;
				}
				else if(a[i][j]=='B'){
					bx=i;by=j;
				}
			}
		}
		printf("Maze #%d\n",++ cnt);
		bfs_box();
		printf("\n");
	}
	return 0;
}

双端队列BFS

在以上的BFS算法之中，每走一步的代价始终是 \(1\) ，但如果不仅仅是 \(1\) 我们还算得出来吗？

别急，先看边权是 \(0\) 或 \(1\) ，的情况。

电路维修 CH2601

其实很简单的啦，在一张边权要么是0，要么是1的无向图上，我们可以通过双端队列BFS来实现搜索。

大体和基础广搜类似，只是如果一味往队尾添加元素的话，无法满足单调性（1有可能在0的前面）

所以当边权是0时，插入队头，否则插入队位，然后就和正常广搜一样了。（不懂 \(deque\) 请自行百度）

代码如下：

#include
#include
#include
#include
#include
#include
#define N 550
#define M 3000000
using namespace std;

int n,m,T,f[N*N];
char a[N][N];
int head[N*N],cnt=0;
struct node{
	int to,next,val;
}edge[M];
dequeq;

int get_num(int x,int y){
	return x*(m+1)+y+1;
}

void addedge(int x,int y,int z){
	cnt++;
	edge[cnt].next=head[x];
	edge[cnt].to=y;
	edge[cnt].val=z;
	head[x]=cnt;
	return;
}

void bfs(){
	while(!q.empty()) q.pop_front();
	for(int i=0;i<=(n+1)*(m+1);i++) f[i]=-1;
	f[1]=0;
	q.push_front(1);
	
	while(!q.empty()){
		int now=q.front();
		q.pop_front();
		if(now==(n+1)*(m+1)){
			printf("%d\n",f[now]);
			return;
		}
		for(int i=head[now];i;i=edge[i].next){
			int y=edge[i].to;
			int z=edge[i].val;
			if(f[y]==-1||f[y]>f[now]+z){
				f[y]=f[now]+z;
				if(z) q.push_back(y);
				else q.push_front(y);
			}
		}
	}
	printf("NO SOLUTION\n");
	return;
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);
		cnt=0;
		memset(head,0,sizeof(head));
		for(int i=1;i<=n;i++){
			scanf("%s",a[N]+1);
			for(int j=1;j<=m;j++){
				if(a[i][j]=='/'){
					addedge(get_num(i-1,j-1),get_num(i,j),1);//气
					addedge(get_num(i,j),get_num(i-1,j-1),1);//势
					addedge(get_num(i-1,j),get_num(i,j-1),0);//磅
					addedge(get_num(i,j-1),get_num(i-1,j),0);//礴
				}
				else{
					addedge(get_num(i-1,j-1),get_num(i,j),0);//的
					addedge(get_num(i,j),get_num(i-1,j-1),0);//存
					addedge(get_num(i-1,j),get_num(i,j-1),1);//图
					addedge(get_num(i,j-1),get_num(i-1,j),1);//啊（这个是凑字用的）
				}
			}
		}
		bfs();
	}
}

优先队列BFS

对于更具有普适性的算法，边权为任意值怎么做呢？

方法一：当有负权时

• 任然如一般广搜一般，采用队列。
• 不能保证每个状态第一次入队时就得到最小代价，所以允许多次重复遍历与更新。
• 具体请看最短路中的 \(SPFA\) 算法。
• PS：复杂度为玄学。

方法二：当无负权时

• 采用优先队列BFS。
• 能够保证每个状态第一次入队时就得到最小代价，所以每个节点至多入队一次。
• 具体请看最短路中的 \(Dijkstral\) 算法。
• PS：复杂度 \(O(N log N)\) 。

That's so easy that I don't want to say any more.

双向广搜

其实没什么两样，就是两边轮流进行，每次扩展一层。

例题：Nightmare Ⅱ HDOJ3085

很简单的双向广搜题，但要注意男孩走三层，女孩走一层。（就被这个坑了 \(INF\) 次）

代码如下：

#include
#include
#include
#include
#include
#include
#define maxn 810
using namespace std;

int n,m,f[maxn][maxn];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
bool vis[maxn][maxn][2];
char s[maxn][maxn];
struct point{
    int x,y;
};
point mm,gg,go[2];
queueq[2];

void init(){
    int t=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++){
            if(s[i][j]=='M'){mm.x=i;mm.y=j;}
            else if(s[i][j]=='G'){gg.x=i;gg.y=j;}
            else if(s[i][j]=='Z'){go[t].x=i;go[t++].y=j;}
        }
    }
    return;
}

void pre_work(){
    while(!q[0].empty()) q[0].pop();
    while(!q[1].empty()) q[1].pop();
    memset(vis,false,sizeof(vis));
    return;
}

int dis(int x1,int y1,int x2,int y2){
    return abs(x1-x2)+abs(y1-y2);
}

bool chck(int x,int y,int typ,int step){
    if(x<1 || x>n || y<1 || y>m || s[x][y]=='X') return false; 
    for(int i=0;i<=1;i++){
        if(dis(x,y,go[i].x,go[i].y)<=step*2) return false;
    }
    return true;
}

bool bfs(int typ,int step){
    int si=q[typ].size();
    while(si--){
        point now=q[typ].front();
        q[typ].pop();
        if(!chck(now.x,now.y,typ,step)) continue;
        for(int i=1;i<=4;i++){
            int fx=now.x+dx[i];
            int fy=now.y+dy[i];
            if(!chck(fx,fy,typ,step)||vis[fx][fy][typ]) continue;
            if(vis[fx][fy][typ^1]) return true;
            vis[fx][fy][typ]=true;
            q[typ].push((point){fx,fy});
        }
    }
    return false;
}

void work(){
    pre_work();
    vis[mm.x][mm.y][0]=true;
    vis[gg.x][gg.y][1]=true;
    q[0].push((point){mm.x,mm.y});
    q[1].push((point){gg.x,gg.y});
    int step=0;
    while(!q[0].empty() || !q[1].empty()){
        step++;
        for(int i=1;i<=3;i++){
            if(bfs(0,step)){
                printf("%d\n",step);
                return;
            }
        }
        if(bfs(1,step)){
            printf("%d\n",step);
            return;
        }
    }
    printf("-1\n");
    return;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
        work();
    }
    return 0;
}

五、A*算法

A*简述

难度真心很大，在优先队列BFS算法，如果给定目标状态要求求出到达目标状态的最小代价，显然它不够优。

因为它是建立在贪心的基础之上的，但目前最优不代表以后最优。

所以为了提高搜索效率，我们可以设置一个估价函数，计算出所有已知状态的估计值，

不断从堆顶出选出 当前代价+未来估价 最小的状态进行扩展。

注意，估价函数一定要满足以下准则 （核能预警） ：

• 设估价函数值为 $ f(state)$

• 设未来实际求出的最小值为 $ g(state)$

• 一定要满足 \(f(state)<=d(state)\)

这个规律显而易见吧。

这种带有估价函数的优先队列BFS就称为A*算法。

例题1

第K短路 POJ2449

思路很巧（好像A*的思路都很巧）

简单说就是讲终点到这个节点的最短路作为估价函数（显然最短路<第K短路）

代码如下：

#include
#include
#include
#include
#include
#include
#include
#define N 1010
#define M 100010
using namespace std;

int n,m,s,t,k;
int dis[N],head[N],sum[N],cnt=0;
bool use[N];
struct node{
	int to,val,next;
}edge[M];
priority_queue >q;
struct Astar{
	int x,h,g;
	friend bool operator < (Astar a,Astar b){
		return a.h+a.g>b.h+b.g;
	}
};
priority_queueqq;
vectorv[N];

void addedge(int x,int y,int z){
	cnt++;
	edge[cnt].next=head[x];
	edge[cnt].to=y;
	edge[cnt].val=z;
	head[x]=cnt;
	v[y].push_back((node){x,z,0});
	return;
}

void dij(){
	memset(use,false,sizeof(use));
	memset(dis,0x3f,sizeof(dis));
	dis[t]=0;
	q.push(make_pair(0,t));
	
	while(!q.empty()){
		int now=q.top().second;
		q.pop();
		if(use[now]) continue;
		use[now]=true;
		for(int i=0;idis[now]+z){
				dis[y]=dis[now]+z;
				q.push(make_pair(-dis[y],y));
			}
		}
	}
	return;
}

void A_star(){
	memset(sum,0,sizeof(sum));
	qq.push((Astar){s,0,0});
	
	while(!qq.empty()){
		Astar now=qq.top();
		qq.pop();
		sum[now.x]++;
		if(sum[now.x]==k && now.x==t){
			printf("%d\n",now.h);
			return;
		}
		if(sum[now.x]>k) continue;
		for(int i=head[now.x];i;i=edge[i].next){
			int y=edge[i].to;
			int z=edge[i].val;
			//printf("%d %d\n",y,dis[y]+now.dist+z);
			qq.push((Astar){y,now.h+z,dis[y]});
		}
	}
	printf("-1\n");
	return;
}

int main(){
	scanf("%d %d",&n,&m);
	int a,b,c;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&a,&b,&c);
		addedge(a,b,c);
	}
	scanf("%d %d %d",&s,&t,&k);
	dij();
	if(s==t) k++;
	A_star();
	return 0;
}

例题2

八数码难题

我好像是用双向BFS做的，但是A*跑得更快（自己啃书吧）

#include
#include
#include
#include
#include
#include

六、IDA*算法

IDA*简述

简单说，$$ IDA=ID+A $$ （废话）

核心一句话：若当前深度+未来估计步数>深度限制，立即回溯 。

例题

Booksort POJ3460

简单的很，具体思路回原文。

#include
#include
#include
#include
#include
#define maxn 20
using namespace std;

int n,a[maxn],flag,deep;

void book_swap(int x,int y,int z){
    int p[maxn],tot=x;
    for(int i=y+1;i<=z;i++) p[tot++]=a[i];
    for(int i=x;i<=y;i++) p[tot++]=a[i];
    for(int i=x;i<=z;i++) a[i]=p[i];
    return;
}

int h(){
    int sum=0;
    for(int i=1;ideep||flag) return;
    if(h()==0){
        flag=true;
        printf("%d\n",step);
        return;
    }

    for(int i=1;i

#include
#include
#include
#include
#include
#include

#include
#include
#include
#include
#include
using namespace std;

int n,a[30],b[30],c[30];
int num[30],id[30],sum=0;
char aa[30],bb[30],cc[30];
bool use[30];

void Get(int x){
	if(!use[x]){
		use[x]=true;
		id[sum++]=x;
	}
	return;
}

bool check(){
	for(int i=n,p=0;i>=1;i--){
		int A=num[a[i]],B=num[b[i]],C=num[c[i]];
		if((A+B+p)%n!=C) return false;
		p=(A+B+p)/n;
	}
	return true;
}

void print(){
	for(int i=1;i<=n;i++) printf("%d ",num[i]);
	exit(0);
}

bool cut_down(){
	if(num[a[1]]+num[b[1]]>=n) return true;
	for(int i=n;i>=1;i--){
		int A=num[a[i]],B=num[b[i]],C=num[c[i]];
		if(A==-1||B==-1||C==-1) continue;
		if((A+B)%n!=C&&(A+B+1)%n!=C) return true;
	}
	return false;
}

void dfs(int x){
	//for(int i=1;i<=n;i++) printf("%d ",num[i]);
	//printf("\n");
	if(cut_down()) return;
	if(x==n){
		if(check()) print();
		return;
	}
	
	for(int i=n-1;i>=0;i--){
		if(!use[i]){
			num[id[x]]=i;
			use[i]=true;
			dfs(x+1);
			num[id[x]]=-1;
			use[i]=false;
		}
	}
	return;
}

int main(){
	scanf("%d",&n);
	cin>>aa>>bb>>cc;
	for(int i=1;i<=n;i++){
		a[i]=aa[i-1]-'A'+1;
		b[i]=bb[i-1]-'A'+1;
		c[i]=cc[i-1]-'A'+1;
		num[i]=-1;
	}
	
	memset(use,false,sizeof(use));
	for(int i=n;i>=1;i--){
		Get(a[i]);Get(b[i]);Get(c[i]);
	}
	memset(use,false,sizeof(use));
	dfs(0);
	return 0;
}

#include
#include
#include
#include
#include
#include
using namespace std;

int deep,map[10][10],ans[10][5];
int last[10][10][10];

void copy(int x){
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            last[x][i][j]=map[i][j];
        }
    }
    return;
}

void build(){
    for(int i=1;i<=5;i++){
        int sum=0;
        for(int j=1;j<=7;j++){
            if(!map[i][j]) sum++;
            else{
                if(!sum) continue;
                map[i][j-sum]=map[i][j];
                map[i][j]=0;
            }
        }
    }
    return;
}
bool can[10][10];
bool delet(){
    bool flag=false;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            if(i-1>=1&&i+1<=5&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]&&map[i][j]){
                can[i][j]=true;can[i-1][j]=true;can[i+1][j]=true;flag=true;
            }
            if(j-1>=1&&j+1<=7&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]&&map[i][j]){
                can[i][j]=true;can[i][j-1]=true;can[i][j+1]=true;flag=true;
            }
        }
    }
    if(!flag) return false;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            if(can[i][j]){
			map[i][j]=0;
			can[i][j]=false;
		    }
        }
    }
    return true;
}

void change(int i,int j,int x){
    int tmp=map[i][j];
    map[i][j]=map[i+x][j];
    map[i+x][j]=tmp;
    build();
    while(delet())build();//我就把while写成if了，调了我三个小时...
}

bool chck(){
    for(int i=1;i<=5;i++){
        if(map[i][1]) return false;
    }
    return true;
}

void dfs(int x){
    if(chck()){
        for(int i=1;i<=deep;i++){
            if(i!=1)printf("\n");
            for(int j=1;j<=3;j++)
            printf("%d ",ans[i][j]);
        }
        exit(0);
    }
    if(x==deep+1)return;
    copy(x);
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++){
            if(map[i][j]){
                if(i+1<=5&&map[i][j]!=map[i+1][j]){
                change(i,j,1);
                ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1;
                dfs(x+1);
                for(int i=1;i<=5;i++)
                    for(int j=1;j<=7;j++)
                    map[i][j]=last[x][i][j];
                ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;
            }
            if(i-1>=1&&map[i-1][j]==0){
                change(i,j,-1);
                ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1;
                dfs(x+1);
                for(int i=1;i<=5;i++)
                    for(int j=1;j<=7;j++)
                    map[i][j]=last[x][i][j];
                ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;
            }
            }
        }
}

int main(){
    int p;
    scanf("%d",&deep);
    for(int i=1;i<=5;i++){
        for(int j=1;j<=8;j++){
            scanf("%d",&p);
            if(!p) break;
            map[i][j]=p;
        }
    }
    memset(ans,-1,sizeof(ans));
    dfs(1);
    printf("-1\n");
    return 0;
}

#include
#include
#include
#include
#include
#define maxn 160 
using namespace std;

int n,m,sx,sy,ex,ey;
int dx[10]={0,2,2,1,1,-1,-1,-2,-2};
int dy[10]={0,1,-1,2,-2,2,-2,1,-1};
int dis[maxn][maxn];
char a[maxn][maxn];
struct node{
	int x,y;
};
queueq;

void bfs(){
	q.push((node){sx,sy});
	memset(dis,-1,sizeof(dis));
	dis[sx][sy]=0;
	
	while(!q.empty()){
		node now=q.front();
		q.pop();
		for(int i=1;i<=8;i++){
			int fx=dx[i]+now.x;
			int fy=dy[i]+now.y;
			if(fx<1 || fx>n || fy<1 || fy>m || dis[fx][fy]!=-1 || a[fx][fy]=='*') continue;
			dis[fx][fy]=dis[now.x][now.y]+1;
			if(fx==ex && fy==ey){
				printf("%d\n",dis[fx][fy]);
				return;
			}
			q.push((node){fx,fy});
		}
	}
}

int main(){
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
		for(int j=1;j<=m;j++){
			if(a[i][j]=='K'){sx=i;sy=j;}
			else if(a[i][j]=='H'){ex=i;ey=j;}
		}
	}
	bfs();
	return 0;
}

#include
#include
#include
#include
#include
#define maxn 110
using namespace std;

int n,m,sx,sy,sum=0,tot=1;
int dx[10]={0,1,-1,0,0,1,1,-1,-1};
int dy[10]={0,0,0,1,-1,1,-1,1,-1};
int dis[maxn][maxn];
char a[maxn][maxn];
queue >q;

void bfs(){
	memset(dis,-1,sizeof(dis));
	dis[sx][sy]=0;
	q.push(make_pair(sx,sy));
	
	while(!q.empty()){
		int nowx=q.front().first;
		int nowy=q.front().second;
		q.pop();
		for(int i=1;i<=8;i++){
			int fx=nowx+dx[i];
			int fy=nowy+dy[i];
			if(fx<1 || fx>n || fy<1 || fy>m || dis[fx][fy]!=-1 || a[fx][fy]=='*') continue;
			dis[fx][fy]=dis[nowx][nowy]+1;
			tot++;
			if(tot==sum){
				printf("%d\n",dis[fx][fy]);
				return;
			}
			q.push(make_pair(fx,fy));
		}
	}
	return;
}

int main(){
	int p,q;
	scanf("%d %d %d %d",&m,&n,&p,&q);
	sx=n-q+1;sy=p;
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
		for(int j=1;j<=m;j++){
			if(a[i][j]!='*'){
				sum++;
			}
		}
	}
	//printf("%d\n",sum);
	bfs();
	return 0;
}

#include
#include
#include
#include
#include

#include
#include
#include
#include
#include
using namespace std;

int T,a[10][10];
bool flag;//,chong[10][10];
int dx[10]={0,1,1,-1,-1,2,2,-2,-2};
int dy[10]={0,2,-2,2,-2,1,-1,1,-1};
int f[10][10]={
	{0,0,0,0,0,0},
	{0,1,1,1,1,1},
	{0,0,1,1,1,1},
	{0,0,0,2,1,1},
	{0,0,0,0,0,1},
	{0,0,0,0,0,0},
};

int check(){
	int sum=0;
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(f[i][j]!=a[i][j]) sum++;
		}
	}
	return sum;
}

void dfs(int xx,int yy,int step,int maxstep){
	if(flag) return;
	if(step==maxstep){
		if(!check()) flag=true;
		return;
	}
	//if(step+check()/2>maxstep) return;
	
	for(int i=1;i<=8;i++){
		int gx=xx+dx[i];
		int gy=yy+dy[i];
		if(gx>5||gx<1||gy>5||gy<1) continue;
		//chong[gx][gy]=true;
		swap(a[xx][yy],a[gx][gy]);
		if(check()+step<=maxstep) dfs(gx,gy,step+1,maxstep);
		swap(a[xx][yy],a[gx][gy]);
	}
	return;
}

int main(){
	scanf("%d",&T);
	while(T--){
		char ch;
		int xx,yy;
		flag=false;
		
		for(int i=1;i<=5;i++){
			for(int j=1;j<=5;j++){
				cin>>ch;
				if(ch=='*') {a[i][j]=2;xx=i;yy=j;}
				else a[i][j]=ch-'0';
			}
		}
		
		if(!check()) {printf("0\n");continue;}
		
		for(int i=1;i<=15;i++){
			//memset(chong,false,sizeof(chong));
			dfs(xx,yy,0,i);
			if(flag) {printf("%d\n",i);break;}
		}
		
		if(!flag) printf("-1\n"); 
	}
	return 0;
}