C++代码浅谈IDA*算法

本篇简述一下IDA*算法，并列出代码帮助大家理解。

（1）算法简介

IDA*(ID A*)算法是一种启发式搜索算法，他是采取了迭代加深的 A*算法，使用了深度优先搜索的方式。

相对于A*算法，IDA*算法主要解决了：

1. A*算法需要判重，对优先级排序的问题。

2. A*算法使用堆，需要大量空间存储的问题。

（2）算法思想

IDA*算法的基本思想是设置一个搜索深度，这个搜索深度从0开始依次递增。使用深度优先搜索在这个深度内搜索目标，可以知道第一个找到目标的最小深度其实就是最短路径。

（3）回顾DFS

DFS是深度优先搜索，DFS的模板如下：

void DFS(int u){
	if(isTarget(u)){//如果u是目标
		//记录u
	}
	for(int i=head[u];i;last[i]){//访问u的连接结点
		int v=to[i];
		DFS(v);
	}
}

（4）引入IDA*

因为IDA*基于迭代加深，所以需要一个函数来进行迭代加深。

void incDeep(int u){
	for(int i=0;;i++){//深度加强
		if(IDAsstar(u,i)){
			//输出解
			break;
		}
	}
}

有了叠在加深之后，我们就可以写IDA*的核心代码了。

bool IDAstar(int u,int deep){
	if(predict()>deep){//预测以最快的速度都得超过剩余深度才能达到终点
		return false;
	}
	if(isTarget(u)){//如果u是目标
		//记录u
		return true;
	}
	bool flag=false;
	if(deep>0){//还可以继续加深
		for(int i=head[u];i;last[i]){//访问u的连接结点
			int v=to[i];
			flag=flag|IDAstar(v,deep-1);//只要有一个是true就行,所以用|
		}
	}
	return flag;
}

（5）优化

IDA*基于深度优先，本文距离采用递归实现，递归有深度限制，改成栈模拟递归将会更优。

（6）缺点

每轮搜索失败进行迭代加深后都需要重新开始搜索。

（7）应用

适用于A*算法无法满足某些特殊要求时的一种替代算法。