题目描述 Description
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入描述 Input Description
输入初试状态，一行九个数字，空格用0表示
输出描述 Output Description
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入 Sample Input
283104765
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
详见试题
思路：
（康托展开+双向广搜） or ida*
代码：
①双向广搜：
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<queue> #include<map> #include<algorithm> #define mx 4000000 using namespace std; struct chess{ int node[9]; int step; int pos; bool cla; }; int chart = 0,step[2][10000]; map<int,int> trans[2]; chess start,end; bool jud[2][mx]; int m_jud[9][4] = {1,3,-1,-1, 0,4,2,-1, 1,5,-1,-1, 0,4,6,-1, 1,3,5,7, 2,4,8,-1, 3,7,-1,-1, 4,6,8,-1, 5,7,-1,-1}; int getval(chess x){ int res = 1,val = 0; for(int i = 1;i <= 9;i++){ val += res * x.node[i-1]; res *= (i+1); } return val; } void putout(chess pt){ cout<<"the class:"<<pt.cla<<endl; for(int i = 1;i <= 3;i++){ for(int j = 1;j <= 3;j++){ cout<<pt.node[(i-1) * 3 + j - 1] <<" "; } cout<<endl; } cout<<"steps: "<<pt.step<<" , pos: "<<pt.pos<<endl; } void init(){ int co,md = 1; cin>>co; for(int i = 8;i >= 0;i--){ start.node[i] = (co / md)% 10; md *= 10; if(start.node[i] == 0) start.pos = i; } start.cla = 0; end.node[0] = 1; end.node[1] = 2; end.node[2] = 3; end.node[3] = 8; end.node[4] = 0; end.node[5] = 4; end.node[6] = 7; end.node[7] = 6; end.node[8] = 5; end.step = start.step = 0; end.pos = 4; end.cla = 1; } void bfs(){ queue<chess> now,then; now.push(start); now.push(end); chess test,h; int p,code; while(!now.empty()){ h = now.front(); p = h.pos; code = getval(h); trans[h.cla][code] = chart; step[h.cla][chart] = h.step; chart++; jud[h.cla][code] = 1; for(int i = 0,j = m_jud[p][i];j != -1 && i <= 3;i++,j = m_jud[p][i]){ test = h; test.step++; swap(test.node[p],test.node[j]); code = getval(test); //if(jud[test.cla][code]) continue; test.pos = j; trans[test.cla][code] = chart; step[test.cla][chart] = test.step; chart++; if(jud[!test.cla][code]){ cout<<step[0][trans[0][code]] + step[1][trans[1][code]]<<endl; return; } if(!jud[test.cla][code]){ now.push(test); jud[test.cla][code] = 1; } } now.pop(); } } int main(){ init(); bfs(); return 0; }
②IDA*：
#include <iostream> #include <cmath> #include <cstdlib> #include <cstdio> #include <cstring> using namespace std; const unsigned int M = 1001; int dir[4][2] = { 1, 0, // Down -1, 0, // Up 0,-1, // Left 0, 1 // Right }; typedef struct STATUS{ int arr[3][3]; int r,c; }STATUS; char dirCode[] = {"dulr"}; char rDirCode[] = {"udrl"}; char path[M]; // 最优解 STATUS begin, end = { 1,2,3,4,5,6,7,8,0,2,2 }; // 起始和终止状态 int maxDepth = 0; // 深度边界 int diff(const STATUS &cur) // 启发函数 { int i,j,k,m,ans=0; for(i=0;i<=2;i++) for(j=0;j<=2;j++) { if(cur.arr[i][j] != 0) { for(k=0;k<=2;k++) for(m=0;m<=2;m++) { if(cur.arr[i][j] == end.arr[k][m]) { ans+=abs(i-k)+abs(j-m); break; } } } } return ans; } bool dfs(STATUS &cur, int depth, int h, char preDir) { if(memcmp(&cur, &end, sizeof(STATUS)) == 0 ) { // OK找到解了:) path[depth] = '/0'; return true; } if( depth + h > maxDepth ) return false; // 剪枝 STATUS nxt; // 下一状态 for(int i=0; i<4; i++) { if(dirCode[i]==preDir) continue; // 回到上次状态,剪枝 nxt = cur; nxt.r = cur.r + dir[i][0]; nxt.c = cur.c + dir[i][1]; if( !( nxt.r >= 0 && nxt.r < 3 && nxt.c >= 0 && nxt.c < 3 ) ) continue; int nxth = h; int preLen,Len,desNum=cur.arr[nxt.r][nxt.c],desR=(desNum-1)/3,desC=(desNum-1)%3; preLen=abs(nxt.r-desR)+abs(nxt.c-desC); Len=abs(cur.r-desR)+abs(cur.c-desC); nxth = h - preLen + Len; swap(nxt.arr[cur.r][cur.c], nxt.arr[nxt.r][nxt.c]); path[depth] = dirCode[i]; if(dfs(nxt, depth + 1, nxth, rDirCode[i])) return true; } return false; } int IDAstar() { int nh = diff(begin); maxDepth = nh; while (!dfs(begin, 0, nh, '/0')) maxDepth++; return maxDepth; } void Input() { char ch; int i, j; for(i=0; i < 3; i++){ for(j=0; j < 3; j++){ do{ scanf("%c", &ch); } while( !( ( ch >= '1' && ch <= '8' ) || ( ch == 'x' ) ) ) ; if( ch == 'x' ) { begin.arr[i][j] = 0; begin.r = i; begin.c = j; } else begin.arr[i][j] = ch - '0'; } } } bool IsSolvable(const STATUS &cur) { int i, j, k=0, s = 0; int a[8]; for(i=0; i < 3; i++){ for(j=0; j < 3; j++){ if(cur.arr[i][j]==0) continue; a[k++] = cur.arr[i][j]; } } for(i=0; i < 8; i++){ for(j=i+1; j < 8; j++){ if(a[j] < a[i]) s++; } } return (s%2 == 0); } int main() { Input(); if(IsSolvable(begin)){ IDAstar(); printf("%s/n", path); } else printf("unsolvable/n"); return 0; }