IDAstar搜索
2011-01-17 09:45:21 来源:WEB开发网核心提示:http://poj.org/problem?id=1077Source CodeProblem: 1077 User: p_hoenix Memory: 220K Time: 0MS Language: C++ Result: Accepted Source Code #include <iostream
http://poj.org/problem?id=1077 Source Code Problem: 1077 User: p_hoenix Memory: 220K Time: 0MS Language: C++ Result: Accepted Source Code #include <iostream> #include <utility> #include <vector> #include <fstream> #include <math.h> using namespace std; const int MAX = 1 << 20; const int ROW = 3, COL = 3; //棋盘 struct Board { Board& operator=(const Board &b) { for(int i = 0; i < ROW; i++) for(int j = 0; j < COL; j++) tile[i][j] = b.tile[i][j]; r = b.r; c = b.c; return *this; } int tile[ROW][COL];//4*4的方块 int r,c;//空格的位置 }; typedef Board Status; struct Step { int r,c; int dir; }; class PicturePizzle { public: friend void input(PicturePizzle &pp); PicturePizzle() { pStepDir = (int*)malloc(sizeof(int) * MAX); stepHeap = (Board*)malloc(sizeof(Board) * MAX); } ~PicturePizzle() { free(pStepDir); free(stepHeap); } //移动步骤. typedef struct{ int r,c;//空格位置 int dir;//移动方向 }Step; //判断以该状态开始是否可以完成拼图 bool JudgeValidStatus(); //heuristic function,启发式函数,计算(估算)最大移动步数 int Heuristic(); //IDA*搜索寻找移动方案 //当前状态,深度,h(),前一步的移动方向. bool IDAstar(Status &s, int depth, int h, int prevDir); //打印移动路径 void ShowStep(int depth); void Run(); //private: Board board; int h; int maxDepth; vector<Board> step; int *pStepDir; Board *stepHeap; //郁闷的地方,C++ primer里面说可以给const static在里面初始化,在类外面定义的,但是VC6.0不可以 //目标棋盘 const static Board destBoard;// = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 4, 4}; const static int nDestPos[ROW * COL + 1][2];//最终棋盘的各个方块的位置 const static int dir[4][2]; }; //1到16的方块编号 const Board PicturePizzle::destBoard = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 2, 2};//10, 11, 12, 13, 14, 15, 16, 3, 3}; const int PicturePizzle::nDestPos[ROW * COL + 1][2] = {{-1, -1}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1},{1, 2}, {2, 0}, {2, 1}, {2, 2}}; //{3, 0}, {3, 1}, {3, 2}, {3, 3}}; const int PicturePizzle::dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//左上右下 bool PicturePizzle::JudgeValidStatus() { int i, j, array[ROW * COL], k, sum; sum = k = 0; //转化成一维数组 for(i = 0; i < ROW; i++) for(j = 0; j < COL; j++) { array[k++] = board.tile[i][j]; } //因为在最终状态下,棋盘的一维数组是有序递增的. //除了X结点外,要到达目标位置需要移动的最大步数,因为在转换成了一维后原本可以上下移动的都被转化成了水平移动. //但是幸运的是,他们是同奇同偶的.具体的证明我也不知道,画图有这么个规律 for(i = 0; i <= ROW * COL - 2; i++) for(j = i + 1; j <= ROW * COL - 1; j++) if(array[i] > array[j]) sum++; //这个是X方块到目标位置的最短步数,不管怎么移动,只要最后是在目标位置,必定是同奇同偶的.(简单的考虑就是撤销) //而每一次的其他方块的移动都是与X方块的交换来实现的,所以他们的和必定是偶数 sum += abs(board.r - nDestPos[ROW * COL][0]) + abs(board.c - nDestPos[ROW * COL][1]); return sum % 2 == 0; } int PicturePizzle::Heuristic() { int r, c, tile, sum = 0; for(r = 0; r < ROW; r++) for(c = 0; c < COL; c++) { tile = board.tile[r][c]; //计算每个方块(非空格)移动到目标位置的曼哈顿距离,不需要计算空格 if(tile != ROW * COL) { sum += abs(r - nDestPos[tile][0]) + abs(c - nDestPos[tile][1]); } } h = sum; return sum; } int global = 0; bool PicturePizzle::IDAstar(Status &s, int depth, int h, int prevDir) { //cout<<global++<<endl; if(memcmp(&s, &destBoard, sizeof(destBoard)) == 0)//到达目标状态 { this->ShowStep(depth); return true; } if(depth >= maxDepth)//超过当前深度 return false; Status ns; int nr,nc,nh,moveTile; for(int d = 0; d < 4; d++) { if(abs(d - prevDir) == 2)//会撤销上次的移动 continue; ns = s; nr = s.r + dir[d][0]; nc = s.c + dir[d][1]; if(nr < 0 || nr > ROW - 1 || nc < 0 || nc > COL - 1)//越界 continue; //移动方块 moveTile = s.tile[nr][nc]; ns.tile[s.r][s.c] = moveTile; ns.tile[nr][nc] = ROW * COL; ns.r = nr; ns.c = nc; //向左移动.并且与X交换的方块离它的目标位置近了一步. //反过来,因为X是向左的,那么moveTile就是向右的,那么这个时候只有moveTile在它的目标位置的左边的时候才成立 //也就是说它原来的位置nc是在目标的左边 if(d == 0 && nc < nDestPos[moveTile][1]) nh = h - 1;//nh比当前的h少1 else if(d == 1 && nr < nDestPos[moveTile][0])//上 nh = h - 1; else if(d == 2 && nc > nDestPos[moveTile][1])//右 nh = h - 1; else if(d == 3 && nr > nDestPos[moveTile][0]) nh = h - 1; else nh = h + 1; //大于f if(depth + nh > maxDepth) continue; //step.insert(step.begin() + depth, ns); //step.erase(step.begin() + depth + 1); pStepDir[depth] = d; stepHeap[depth] = ns; if(IDAstar(ns, depth + 1, nh, d)) return true; } return false; } void PicturePizzle::ShowStep(int depth) { int i = 0; //cout<<depth<<endl; for(i = 0; i < depth; i++) switch(pStepDir[i]) { case 0: cout<<'l'; break; case 1: cout<<'u'; break; case 2: cout<<'r'; break; case 3: cout<<'d'; break; } cout<<endl; /* for(i = 0; i < depth; i++) { for(int r = 0; r < ROW; r++) { for(int c = 0; c < COL; c++) cout<<stepHeap[i].tile[r][c]<<"\t"; cout<<endl; } cout<<endl<<endl; } */ /* cout<<step.size()<<endl<<endl; for(vector<Board>::iterator iter = step.begin(); iter != step.end(); iter++) { cout<<i++<<endl; for(int r = 0; r < 4; r++) { for(int c = 0; c < 4; c++) cout<<iter->tile[r][c]<<"\t"; cout<<endl; } cout<<endl<<endl; }*/ } void PicturePizzle::Run() { if(JudgeValidStatus()) { maxDepth = Heuristic(); while(maxDepth++) if(IDAstar(board, 0, h, 20)) break; } else { cout<<"unsolvable"<<endl; } } void input(PicturePizzle &pp) { //cout<<"输入一个文件(.txt),表示拼图的初始" //fstream file("in.txt"); int num; for(int r = 0; r < ROW; r++) for(int c = 0; c < COL; c++) { //file>>num; cin>>num; if(/*file.fail()*/cin.fail()) { //file.clear(); //file.ignore(1,'\t'); cin.clear(); cin.ignore(1, ' '); pp.board.tile[r][c] = ROW * COL; pp.board.r = r; pp.board.c = c; } else pp.board.tile[r][c] = num; } //file.close(); } int main() { //freopen("out.txt", "w", stdout); PicturePizzle pp; input(pp); pp.Run(); return 0; }
[]
更多精彩
赞助商链接