IDA*

算法分析

IDA* 本质上就是带有估价函数和迭代加深优化的dfs与，A * 相似A *的本质便是带

有估价函数的bfs,估价函数是什么呢?估价函数顾名思义，就是估计由目前状态达

到目标状态的总费用，这个费用可以是距离，可以是路程，估价函数用于对dfs过

程进行优化，由当前状态借助估价函数判断怎么搜索更优，从而去走较优的状态，

\[f(n)=g(n)+h(n);
\]

\(f(n)\)就是我们的估价函数，\(n\)表示当前状态，\(g(n)\)表示由当前状态的费用，

\(h(n)\)当前状态到目标状态的费用，估价函数的设计因题而异，一道题的估价函数

也有很多种，不同设计方案对dfs起到的优化作用不同，\(h(n)\)设计的越准确，对dfs

的优化越高，但如果求h(n)太复杂也没有什么实际意义，也就是说，\(h(n)\)不保证绝对准确

介绍完估价函数，我们再来介绍迭代加深优化，什么是迭代加深优化？其本质就是对

搜索层数进行限制，避免无意义的搜索，比如需要找到的答案在搜索树的第四层，我

们先搜第一层，设置搜索上限深度为1 ，我们搜索搜索树的第一层，没找到答案，停

止搜索，搜索上限+1,继续从起点进行搜索，直到找到答案，为什么这样可以对dfs起

到优化？考虑一颗深度非常大，并且答案在较小层的右侧的树，如果普通进行dfs明

显是很慢的，这时候IDA * 的优点就显现出来了

例题

[SCOI2005]骑士精神

以此题举例

下面是代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

using namespace std;

const int maxn=100;

int t;

char ca;

int x1,y1;

int map[maxn][maxn];

int cr[maxn][maxn]={

{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 gu(){//估价函数

	int cnt=0;

	for(int i=1;i<=5;i++){

		for(int j=1;j<=5;j++){

			if(map[i][j]!=cr[i][j]){

				cnt++;

			}

		}

	}

	return cnt;

}

bool success=0;

int y2[maxn]={0,2,-2,2,-2,1,-1,1,-1};

int x2[maxn]={0,-1,-1,1,1,2,2,-2,-2};

void astar(int deep,int x,int y,int us){

	if(us==deep){

		if(!gu()){

			success=1;

		//	cout<<1;

			return ;

		}

	}

	for(int i=1;i<=8;i++){

		int xx=x;

		int yy=y;

		xx=x+x2[i];

		yy=y+y2[i];

		if(xx<1||xx>5||yy>5||yy<1){

			continue;

		}

		swap(map[xx][yy],map[x][y]);

	//	cout<<xx<<" "<<yy<<" "<<x<<" "<<y<<endl;

		if(us+gu()>deep){

			swap(map[xx][yy],map[x][y]);

			continue;

		}

		if(success){

			return ;

		}

		astar(deep,xx,yy,us+1);

		swap(map[xx][yy],map[x][y]);

	}

	return ;

}

int main(){

	freopen("a.txt","r",stdin);

	cin>>t;

	while(t--){

		for(int i=1;i<=5;i++){

			for(int j=1;j<=5;j++){

				cin>>ca;

			//	cout<<ca<<" ";

				if(ca=='*'){

					x1=i;

					y1=j;

					map[i][j]=2;

		//			cout<<map[i][j]<<" ";

				}

				else{

					map[i][j]=ca-'0';

			//		cout<<map[i][j]<<" ";

				}

			}

		//	cout<<endl;

		}

	//	cout<<gu();

		if(!gu()){

			cout<<-1;//所给的图符合题意，所以直接结束，此处剪枝优化比较明显

			return 0;

		}

		for(int i=1;i<=15;i++){

			astar(i,x1,y1,0);

			if(success){

				cout<<i<<endl;

				break;

			}

		}

		if(!success){

			cout<<-1<<endl;

		}

		success=0;

	}

	return 0;

}

完结撒花

巴特西

还不会ida*算法?看完这篇或许能理解点。

IDA*

算法分析

例题

最新文章

热门文章