骑士精神笔记（IDA*)

万恶之源

做法

这道题就是一道很典型的搜索题，可以像滑雪那样用深搜一路枚举到最后复原，也可以像马的遍历那样用广搜逐层扩展的一步步的拓展。但是，这道题的深度可能非常深，需要枚举的情况又非常多，状态也很难保存（当然是可以保存的），单纯的深搜和广搜都很难完成这题，因此迭代加深诞生了！！

迭代加深简单来说就是逐层拓展的深搜，显然它既有广搜也有深搜的特性，具体性质这里不赘述。

我们可以将移动步数作为层数，一层层加深，在加深的过程中枚举可能的移动方式，这样一直到十五层一定可以找出答案。

但是这样也并不能过这道题，因为一层层下去可能的情况是指数级增长的，因此我们还需要继续优化。。。可以选择双向bfs，A * 和IDA*。

我莫名其妙用了IDA*参考题解的，感觉好像还是能够接受？

核心代码

void IDA(int dep,int x,int y,int maxdep) {
	if (dep == maxdep) {
		if (!hx()) suc = 1;
		return;
	}
	for (register int j = 1; j <= 8; j++) {
		int xx = x + dx[j];
		int yy = y + dy[j];
		if (!check(xx,yy)) continue;
		swap(G[x][y],G[xx][yy]);
		int fx = dep + hx();//评价函数
		if (fx <= maxdep) { //估计未来的深度是否会超过最大深度
			IDA(dep+1,xx,yy,maxdep);
		}
		swap(G[x][y],G[xx][yy]);//回溯
	}
}
           

ID和普通的DFS主要就是添加了逐层拓展这一特性，这一特性在main函数中用一个递增IDA的maxdep参数的循环体现

for (register int Maxdep = 1; Maxdep <= 15; Maxdep++) {
	IDA(0,wx,wy,Maxdep);
	if (suc == 1) {printf("%d\n",Maxdep);break;}
	} 
    
           

但是我们这里是IDA，它与ID的主要差别就是增加了启发函数*，如同A*算法是比BFS多了个启发函数。

这个优化简直如虎添翼

定义：

f(n)=g(n)+h(n)

其中n是一个状态，f就是评价函数，g是n已经用掉的开销，h是一个启发函数。

当h(n)=0时，A算法本质就是普通的堆优化bfs

h(n)是启发式搜索的核心，因为g（n）就相当于我们平时的一些堆优化之类的，h

简单来说h（n）就是对未来有个估计，看有多少希望达到目标，上面的IDA* 就将有多少棋子不在自己该在的位置上作为h（n）函数，虽然看着没什么，但是却能带来非常非常非常神奇的优化。

此题糟点（细节问题）

1. 首先学习一种看上去好像挺厉害的逐个读取字符的方式，读取字符这块搞到我都头疼，一开始本来用cin，但是它好像很慢，所以就改了，但是并没有加快多少，但还是学习学习趴

void readChar(char &c) {
    for (c = getchar(); c != '0' && c != '1' && c != '*'; c = getchar());
}
           

2. 启发函数的实际应用

inline int hx() { //启发函数，评估当前状态有多少个点不在自己的原位上,除了空白
	int cnt = 0;
	for (register int i = 1; i <= 5; i++) {
		for (register int k = 1; k <= 5; k++) {
			if (G[i][k]!=goal[i][k]) {//&& G[i][k]!=2
				cnt++;
			}
		}
	}
	return cnt;
}
if (dep + hx <= maxdep) { 
	IDA(dep+1,xx,yy,maxdep);
}
           

直观来讲就是估计还有多少步才能到目标，估计之后在范围之内才继续搜索，因为估计值一定小于实际值，若是估计值都大于范围了，那实际搜索肯定也会大于它，所以没必要搜下去。

1. 网格题一定都要记得带上判断是否超界的函数！！！
2. 起点应该是空白格
3. 这里的搜索函数不是bool型的，因为我们利用的是maxdep来确定答案（当然我感觉应该可以改成bool型的）
4. 特殊情况要特判，特判一开始就正确的图
5. 其实这题就算用了IDA* 也还是过不了，需要一点点常数优化。