POJ 2286 The Rotation Game 搜索-IDA*+迭代加深
本题若用广搜,空间需求量非常大,空间不足。深搜的话,深度很难控制,容易陷入死循环。在这个时候就要用到迭代加深的深搜方法。
所谓迭代加深,就是在深度无上限的情况下,先预估一个深度(尽量小)进行搜索,如果没有找到解,再逐步放大深度搜索。这种方法虽然会导致重复的遍历 某些结点,但是由于搜索的复杂度是呈指数级别增加的,所以对于下一层搜索,前面的工作可以忽略不计,因而不会导致时间上的亏空。
这种方法,可以算作是DFS和BFS的结合。适合大树而可行解不是很深的题目。
IDA*对于最优解层数小,每次扩展状态多的时候是一个杀手锏啊。IDA*就是一个加了层数限制depth的DFS,超过了限制就不在搜索下去,如果在当前层数没有搜到目标状态,就加大层数限制depth,这里还只是一个IDA算法,并不是A*的。当然我们可以用A*的估计函数去剪枝,如果当前深度d+h()>depth的时候就可以不再搜索下去了,这样就是IDA*了。
对于这道题,我们把状态用一维数组存储,然后对每个元素设定相应的编号:
0 1
2 3
4 5 6 7 8 9 10
11 12
13 14 15 16 17 18 19
20 21
22 23 并且把每个操作的相应编号用数组存起来就好处理了:
AC代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; typedef long long LL; const int N=2222222; const LL II=1000000007; int n,m,depth; int vis[2222222],s[24]; int path[N]; int t[4][2]={-1,0,0,1,1,0,0,-1}; char op[]="ABCDEFGH"; int mid[8]={6,7,8,11,12,15,16,17};//中间位置 int fan[8]={5,4,7,6,1,0,3,2};//反方向移动,回归 int xh[8][7]=//8种操作,每次移动7位 { 0,2,6,11,15,20,22, 1,3,8,12,17,21,23, 10,9,8,7,6,5,4, 19,18,17,16,15,14,13, 23,21,17,12,8,3,1, 22,20,15,11,6,2,0, 13,14,15,16,17,18,19, 4,5,6,7,8,9,10 }; int max3(int a,int b,int c) { return (a>b?a:b)>c?(a>b?a:b):c; } int get(int a[]) { int i,cnt[4]={0,0,0,0}; for(i=0;i<8;i++) cnt[s[mid[i]]]++; return 8-max3(cnt[1],cnt[2],cnt[3]);// 8-返回中间最多的那个数 的数量 } void move(int k) { int i,t=s[xh[k][0]]; for(i=1;i<7;i++) s[xh[k][i-1]]=s[xh[k][i]]; s[xh[k][6]]=t; } bool dfs(int k) { if(k>=depth) return false; int i,h; for(i=0;i<8;i++) { move(i); path[k]=i; h=get(s); if(h==0) return true; if((k+h)<depth&&dfs(k+1))//当前的步数加还需要的最少步数<depth return true; move(fan[i]);//移回来 } return false; } int main() { int i,j; while(scanf("%d",&s[0])&&s[0]) { for(i=1;i<24;i++) scanf("%d",&s[i]); depth=get(s);//差最少的步数 if(depth==0) { printf("No moves needed\n%d\n",s[mid[0]]); continue; } while(!dfs(0)) depth++;//如果不行,最少步数+1 for(i=0;i<depth;i++) printf("%c",op[path[i]]); printf("\n%d\n",s[6]);//输出中间位置的数字 } return 0; } #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; typedef long long LL; const int N=2222222; const LL II=1000000007; int n,m,depth; int vis[2222222],s[24]; int path[N]; int t[4][2]={-1,0,0,1,1,0,0,-1}; char op[]="ABCDEFGH"; int mid[8]={6,7,8,11,12,15,16,17};//中间位置 int fan[8]={5,4,7,6,1,0,3,2};//反方向移动,回归 int xh[8][7]=//8种操作,每次移动7位 { 0,2,6,11,15,20,22, 1,3,8,12,17,21,23, 10,9,8,7,6,5,4, 19,18,17,16,15,14,13, 23,21,17,12,8,3,1, 22,20,15,11,6,2,0, 13,14,15,16,17,18,19, 4,5,6,7,8,9,10 }; int max3(int a,int b,int c) { return (a>b?a:b)>c?(a>b?a:b):c; } int get(int a[]) { int i,cnt[4]={0,0,0,0}; for(i=0;i<8;i++) cnt[s[mid[i]]]++; return 8-max3(cnt[1],cnt[2],cnt[3]);// 8-返回中间最多的那个数 的数量 } void move(int k) { int i,t=s[xh[k][0]]; for(i=1;i<7;i++) s[xh[k][i-1]]=s[xh[k][i]]; s[xh[k][6]]=t; } bool dfs(int k) { if(k>=depth) return false; int i,h; for(i=0;i<8;i++) { move(i); path[k]=i; h=get(s); if(h==0) return true; if((k+h)<depth&&dfs(k+1))//当前的步数加还需要的最少步数<depth return true; move(fan[i]);//移回来 } return false; } int main() { int i,j; while(scanf("%d",&s[0])&&s[0]) { for(i=1;i<24;i++) scanf("%d",&s[i]); depth=get(s);//差最少的步数 if(depth==0) { printf("No moves needed\n%d\n",s[mid[0]]); continue; } while(!dfs(0)) depth++;//如果不行,最少步数+1 for(i=0;i<depth;i++) printf("%c",op[path[i]]); printf("\n%d\n",s[6]);//输出中间位置的数字 } return 0; }
补充:软件开发 , C++ ,