原博客地址：http://blog.csdn.net/t1019256391/article/details/9257243
15s的时间，150000kb的内存，一眼就让人想到广搜，但状态实在太多，3^25-1种吧，想写又没下手。。。
其实这是一道IDA*的题目。
顺便讲一下自己对IDA*的理解：
1、什么是IDA*？
是结合深搜和广搜二者优势的一种算法，深搜内存消耗少，路径容易保存，状态少，但不能保证最优解。广搜能找到最优解，但内存开销大，状态多，代码长。 而IDA*就是二者的完美结合。它在深搜的基础上人为的增加一个deep（搜索深度），一旦当前深度大于等于这个deep则直接返回，然后deep++重新搜索。这样就保证了解的最优性。这就是ID。而通过对题目的分析，找到一个好的估价函数h()，用来描述当前状态到目标状态的估计值（理想值），用now+h()>deep来剪枝，这就是IDA*。
2、什么情况下用IDA*?
内存紧，状态多判重复杂，问题一定有解（或者无解情况能判断出来）。
这道题要求使得中间8个数都一样，可以得出，每移动一次，中间8个数最多只会改变1个，所以我们把
8 减去当前8个数中出现最多的次数 设计成我们的估价函数h，一旦当前深度now+h()超过了我们的deep，则剪枝。
这题蛋疼的地方就是做转换的时候数组的移动，不过可以事先用一个辅助数组来存下每次要交换的点。
本以为代码会很长，写完后发现还不到100行。
这题也是一个很好的IDA* hdu 1560
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; int deep; vector<int> ans; int dig[8]={7,8,9,12,13,16,17,18}; int a[25]; //循环移动数组，，后一个数字等于前一个数字 int move[8][15]= { {0,1,23,3,1,7,3,12,7,16,12,21,16,23,21}, {0,2,24,4,2,9,4,13,9,18,13,22,18,24,22}, {0,11,5,10,11,9,10,8,9,7,8,6,7,5,6}, {0,20,14,19,20,18,19,17,18,16,17,15,16,14,15}, {0,24,2,22,24,18,22,13,18,9,13,4,9,2,4}, {0,23,1,21,23,16,21,12,16,7,12,3,7,1,3}, {0,14,20,15,14,16,15,17,16,18,17,19,18,20,19}, {0,5,11,6,5,7,6,8,7,9,8,10,9,11,10} }; int ret[8]={5,4,7,6,1,0,3,2}; //还原数组 bool isend() { int tmp=a[7]; for(int i=1;i<8;i++) { if(a[dig[i]]!=tmp) return false; } return true; } int h() { int maxn=0; int tmp[4]={0}; for(int i=0;i<8;i++) { tmp[a[dig[i]]]++; } maxn=max(tmp[1],max(tmp[2],tmp[3])); return 8-maxn; } void change(int k) { a[0]=a[move[k][2]]; for(int i=1;i<15;i+=2) { if(i==13) a[move[k][i+1]]=a[0]; else a[move[k][i+1]]=a[move[k][i]]; } } bool dfs(int now) { if(now==deep) return isend(); if(now+h()>deep) return false; //剪枝 for(int i=0;i<8;i++) { change(i); ans.push_back(i); if(dfs(now+1)) return true; ans.pop_back(); change(ret[i]); } return false; } int main() { while(scanf("%d",&a[1])&&a[1]) { ans.clear(); for(int i=2;i<=24;i++) { scanf("%d",&a[i]); } if(isend()) { printf("No moves needed\n"); printf("%d\n",a[7]); continue; } deep=1; while(dfs(0)==false) { deep++; } for(int i=0;i<ans.size();i++) { putchar(ans[i]+'A'); } printf("\n%d\n",a[7]); } return 0; }