本篇簡述一下IDA*算法，并列出代碼幫助大家理解。

（1）算法簡介

IDA*(ID A*)算法是一種啟發(fā)式搜索算法，他是采取了迭代加深的 A*算法，使用了深度優(yōu)先搜索的方式。

相對于A*算法，IDA*算法主要解決了：

1. A*算法需要判重，對優(yōu)先級排序的問題。

2. A*算法使用堆，需要大量空間存儲的問題。

（2）算法思想

IDA*算法的基本思想是設(shè)置一個搜索深度，這個搜索深度從0開始依次遞增。使用深度優(yōu)先搜索在這個深度內(nèi)搜索目標，可以知道第一個找到目標的最小深度其實就是最短路徑。

（3）回顧DFS

DFS是深度優(yōu)先搜索，DFS的模板如下：

void DFS(int u){
	if(isTarget(u)){//如果u是目標
		//記錄u
	}
	for(int i=head[u];i;last[i]){//訪問u的連接結(jié)點
		int v=to[i];
		DFS(v);
	}
}

（4）引入IDA*

因為IDA*基于迭代加深，所以需要一個函數(shù)來進行迭代加深。

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){//還可以繼續(xù)加深
		for(int i=head[u];i;last[i]){//訪問u的連接結(jié)點
			int v=to[i];
			flag=flag|IDAstar(v,deep-1);//只要有一個是true就行,所以用|
		}
	}
	return flag;
}

（5）優(yōu)化

IDA*基于深度優(yōu)先，本文距離采用遞歸實現(xiàn)，遞歸有深度限制，改成棧模擬遞歸將會更優(yōu)。

（6）缺點

每輪搜索失敗進行迭代加深后都需要重新開始搜索。

（7）應用

適用于A*算法無法滿足某些特殊要求時的一種替代算法。