洛谷-騎士精神

啟發(fā)式搜索-A*

估價(jià)函數(shù)

對(duì)于當(dāng)前狀態(tài)，我們可以將其與目標(biāo)狀態(tài)對(duì)比，得到一個(gè)預(yù)估的代價(jià)，即最少（不一定滿足題意）的代價(jià)，得到這個(gè)代價(jià)的函數(shù)叫做估價(jià)函數(shù)

對(duì)于一個(gè)最短路問(wèn)題來(lái)說(shuō)，我們可以定義一個(gè)如下的函數(shù)式來(lái)表示搜索的過(guò)程
\[ f^*(x)=g^*(x)+h^*(x) \]
其中，f*(x)為從x到目標(biāo)節(jié)點(diǎn)預(yù)估的總代價(jià)，g*(x)表示目前到達(dá)x點(diǎn)已經(jīng)付出的代價(jià)，h*(x)表示預(yù)估從x到目標(biāo)的最小代價(jià)，如上題（騎士精神）中，f(x)用迭代加深枚舉出來(lái)，g(x)為已經(jīng)走的步數(shù)（已知），h*(x)則可表示為目前局面與目標(biāo)局面的不同點(diǎn)的個(gè)數(shù)。

上題代碼

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int a[5][5]; int _std[5][5]= {{1,1,1,1,1},{0,1,1,1,1},{0,0,-1,1,1},{0,0,0,0,1},{0,0,0,0,0} }; int dx[]={0,-2,-2,-1,-1,1,1,2,2}; //重點(diǎn)，剪枝，兩邊對(duì)稱并在下面判斷防止走回去 int dy[]={0,-1,1,-2,2,-2,2,-1,1}; int ans; int lim; int fc() {int ret=0;for(int i=0; i<5; i++) {for(int j=0; j<5; j++) {if(a[i][j]!=_std[i][j]) {ret++;}}}return ret; } void dfs(int x,int y,int step,int f) {int diff=fc();if(diff+step>lim)return;if(step>=ans)return;if(diff==0) {ans=step;return;}for(int i=1; i<=8; i++) {if(x+dx[i]<0||(x+dx[i]>4)) continue;if(y+dy[i]<0||(y+dy[i]>4)) continue;if(i+f!=9) {swap(a[x+dx[i]][y+dy[i]],a[x][y]);dfs(x+dx[i],y+dy[i],step+1,i);swap(a[x+dx[i]][y+dy[i]],a[x][y]);}} }int main() {int t;scanf("%d",&t);while(t--) {int x,y;ans=20;int dif=0;for(int i=0; i<5; i++) {for(int j=0; j<5; j++) {char tmp;cin>>tmp;if(tmp=='1') {a[i][j]=1;}if(tmp=='0') {a[i][j]=0;}if(tmp=='*') {a[i][j]=-1;x=i;y=j;}if(a[i][j]!=_std[i][j])dif++;}}for(int i=dif;i<=16;i++){lim=i;dfs(x,y,0,0);}printf("%d\n",ans==20? -1:ans);}return 0; }

而對(duì)于上題的搜索則需要最優(yōu)性剪枝，通過(guò)變化數(shù)組的遍歷方式防止走回去

轉(zhuǎn)載于:https://www.cnblogs.com/shulker/p/9832596.html

總結(jié)

以上是生活随笔為你收集整理的[启发式搜索/A*] [SCOI2005]骑士精神题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。