1.A 演算法 我們普通的搜索演算法往往複雜度都是指數級，OI中這樣的複雜度無法滿足我們的要求。這時我們一般都會進行一些剪枝優化，但在有些題目中卻可以有更加巧妙的方法——A 演算法。 A 演算法作為一種基礎的啟髮式搜索，它不同於DFS和BFS將所有情況進行遍歷，它能從所有情況中選出較優的再進行遍歷。因此，它 ...
1.A*演算法
我們普通的搜索演算法往往複雜度都是指數級，OI中這樣的複雜度無法滿足我們的要求。這時我們一般都會進行一些剪枝優化，但在有些題目中卻可以有更加巧妙的方法——A*演算法。
A*演算法作為一種基礎的啟髮式搜索，它不同於DFS和BFS將所有情況進行遍歷，它能從所有情況中選出較優的再進行遍歷。因此，它讓搜索從“瞎搜”轉化到了“有目標的搜索”。那麼如何確定較優的情況便是關鍵所在。
A*演算法中核心是一個估值函數，我們可以通過它來得到每種情況的優劣。用公式表示便是：
f(n)=g(n)+h(n)
當中g(n)是從初始狀態到當前狀態是實際代價，可以通過計算得出，h(n)便是估值函數，估計當前狀態到結束狀態的代價，f(n)便是估計出來的總代價。由此我們將每一個狀態估價，我們便可以選出f(n)更優的狀態進行遍歷。不難看出，這個估值函數可以有不同的選擇，同時也直接影響到了演算法的效率，因此這個函數的選取是極為重要的。
2.h(n)的選取
下麵所說的h(n)即為估值函數，d(n)為實際值（當前狀態到結束狀態的實際代價）
- 如果h(n)<d(n)，估算代價比實際值小，估計結果更優，因此搜索的範圍更大，效率低。但往往能得出最優解。
- 如果h(n)=d(n)，估算代價等於實際值，估計結果等於實際結果，因此搜索按照實際的最優情況經行，效率最高。
- 如果h(n)>d(n)，估算代價大於實際值，估計結果更優的較少，因此搜索的範圍更小，效率高，但是不一定得出最優解。
在OI中，為了保證答案最優，我們往往選擇h(n)$<$d(n)。
我們看兩個例子：
第一個是SCOI2005 騎士精神（BZOJ 1085），這道題目似乎沒有其他的技巧，只能進行搜索，數據範圍也確實不大。但是普通的搜索肯定會超時的，於是很自然的想到了A*演算法。這道題中h(n)不難想出，就是當前狀態有多少個需要移動的騎士。雖然有可能h(n)較小實際值卻偏大，但我們這裡是偏優的估計,即是h(n)$<$d(n)，所以可以保證答案的準確性。估值函數代碼如下：
int h()
{
int sum=0;
for(int i=1; i<=5; i++)
for(int j=1; j<=5; j++)
if(map[i][j]!=aim[i][j]){ //map為當前狀態，aim為目標狀態
sum++;
}
return sum;
}第二個是比較有名的八數位問題（不清楚的可以百度一下），這道題一般容易想到搜索。這道題目h(n)選取有兩種方法，第一種便是同上一題相似，h(n)是有多少個數字需要移動。但還有一種更為巧妙(當然也更精確)的選取方式：便是每一個數字到目標位置的曼哈頓距離（就是到目標位置要走多少個格子）之和。不難看出，這樣的估計也是偏優的。估值函數代碼如下：
const int aimx[9]={2,1,1,1,2,3,3,3,2},aimy[9]={2,1,2,3,3,3,2,1,1};
//aimx[i]表示目標狀態數字i的縱坐標，aimy表示橫坐標
int h()
{
int sum=0;
int nx[9],ny[9]; //nx[i]表示數字i的縱坐標，ny表示橫坐標
for(int i=1; i<=3; i++)
for(int j=1; j<=3; j++){
nx[map[i][j]]=i; //map為當前狀態
ny[map[i][j]]=j;
}
for(int i=1; i<9; i++)
sum+=abs(nx[i]-aimx[i])+abs(ny[i]-aimy[i]); //到目標位置曼哈頓距離
return sum;
}現在我們對估值函數的選取有了一定的瞭解，寫題時靈活準確的選取h(n)是關鍵。
3.IDA*演算法
A* 演算法在實現過程中往往是在獲得的子節點中選取f(n)最小的子節點進行擴展（一般用堆或優先隊列選出f(n)最小的子節點），通過維護關閉列表和開放列表，對擴展出來的節點進行檢測(判重，為提高效率有時使用hash）。詳細的實現步驟可以參考其他博客，這裡偏向於思想和應用層面。我們可以看出，普通A*將大部分時間消耗在了將f(n)排序和情況判重上，同時類似於BFS將狀態儲存到節點中，這也往往需要很大的空間。
而IDA* 綜合了A* 演算法和迭代加深搜索（一種DFS），有著空間消耗少的特點。同時不需要儲存節點，也不用將狀態排序和判重，在時間和空間上都優於普通的A* 演算法。它是在f(n)>預定的最大搜索深度時進行剪枝。這樣的代碼難度往往會小很多，在OI中IDA* 演算法比A* 演算法實用很多。
舉個例子，還是上一題的八數位問題，IDA*的代碼就很簡潔：（部分核心代碼）
void dfs(int x, int y, int g) //g便是公式中g(n)
{
if(g+h()>ans || flag) return; //g+h()便是f(n)，ans為預定最大搜索深度
if(h()==0) {flag=1; return;} //h(n)==0時便是與目標狀態完全相同
for(int i=0; i<4; i++) {
int rx=x+dx[i];
int ry=y+dy[i]; //遍歷四個方向
if(rx<1 || ry<1 || rx>3 || ry>3) continue; //判斷是否出界
swap(map[x][y], map[rx][ry]); //交換位置
dfs(rx, ry, g+1); //下一步搜索
swap(map[x][y], map[rx][ry]);
}
return ;
}
for(ans=0; ;ans++){ //迭代加深
dfs(sx, sy, 0); //IDA*搜索
if(flag) {
printf("%d\n",ans); //最優解
break;
}
}
