题目地址：http://poj.org/problem?id=2286
本题若用广搜，空间需求量非常大，空间不足。深搜的话，深度很难控制，容易陷入死循环。在这个时候就要用到迭代加深的深搜方法。
所谓迭代加深，就是在深度无上限的情况下，先预估一个深度（尽量小）进行搜索，如果没有找到解，再逐步放大深度搜索。这种方法虽然会导致重复的遍历 某些结点，但是由于搜索的复杂度是呈指数级别增加的，所以对于下一层搜索，前面的工作可以忽略不计，因而不会导致时间上的亏空。
这种方法，可以算作是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;
- }