?

題面

傳送門

分析

首先，直接搜索肯定會TLE
很容易想到用迭代加深的方法，限定搜索深度
但是，這樣仍然不夠，需要用啟發式的方法優化
我們設計一個估價函數f(x)=g(x)+h(x)f(x)=g(x)+h(x)
g(x)g(x)是初始狀態到當前狀態的實際代價
h(x)h(x)是當前到目標的估計代價
如果f(x)=g(x)+h(x)>d（當前限定深度）f(x)=g(x)+h(x)>d（當前限定深度），則直接返回
h(x)h(x)函數如何設計？
h(x)h(x)不能劣于實際最優值，所以可設為當前狀態與目標狀態不同方格的數量

代碼

#include<iostream> #include<cstdio> #include<cstring> #define maxn 16 using namespace std; int n=5; int walkx[10]= {1,1,-1,-1,2,2,-2,-2}; int walky[10]= {2,-2,2,-2,1,-1,1,-1}; char now[maxn][maxn]; char final[maxn][maxn]= {{},{' ','1','1','1','1','1'},{' ','0','1','1','1','1'},{' ','0','0','*','1','1'},{' ','0','0','0','0','1'},{' ','0','0','0','0','0'}}; int is_same() {for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(now[i][j]!=final[i][j]) return 0;}}return 1; } int h() { //估價函數int cnt=0;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(now[i][j]!=final[i][j]) cnt++;}}return cnt; } int ida(int deep,int limit,int x,int y) { // printf("%d %d %d %d\n",deep,dasadfslimit,x,y); // for(int i=1; i<=n; i++) { // for(int j=1; j<=n; j++) { // printf("%c",now[i][j]); // } // printf("\n"); // } // printf("\n");if(deep>limit) return 0;if(deep==limit) {if(is_same()) { // for(int i=1; i<=n; i++) { // for(int j=1; j<=n; j++) { // printf("%c",now[i][j]); // } // printf("\n"); // }return 1;} else return 0;}int flag=0;for(int i=0; i<8; i++) {int xx=x+walkx[i],yy=y+walky[i];if(xx<1||yy<1||xx>n||yy>n) continue;swap(now[x][y],now[xx][yy]);if(deep+h()<=limit) flag|=ida(deep+1,limit,xx,yy);swap(now[x][y],now[xx][yy]);}return flag; } int t; int main() {scanf("%d",&t);while(t--) {int sx,sy;for(int i=1; i<=5; i++) {for(int j=1; j<=5; j++) {cin>>now[i][j];if(now[i][j]=='*') {sx=i;sy=j;}}} // for(int i=1; i<=n; i++) { // for(int j=1; j<=n; j++) { // printf("%c",final[i][j]); // } // printf("\n"); // }for(int i=0; i<=16; i++) {if(i==16) {printf("-1\n");break;}if(ida(0,i,sx,sy)) {printf("%d\n",i);break;}}} }

轉載于:https://www.cnblogs.com/birchtree/p/9845828.html

總結

以上是生活随笔為你收集整理的BZOJ 1085（IDA*）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。