《重排九宫格》由会员分享，可在线阅读，更多相关《重排九宫格（9页珍藏版）》请在金锄头文库上搜索。
1、重排九宫格问题一问题描述在3*3的方格棋盘上放置分别标有数字123,4,5,6,7,8的8张牌，初始状态为sO,目标状态为sg, 可使用的算符有空格左移，空格上移，空格右移和空格下移，即它们只允许把位于空格左，上 右，下边的牌移入空格。要求寻找从初始状态到目的状态的路径。二算法描述(1) 把初始节点SO放入OPEN表。(2) 如果OPEN表为空，则问题无解，退出。(3) 把OPEN表的第一个节点取出放入CLOSE表(记为节点n)。(4) 考察节点n是否为目标节点。若是，则求得了问题的解，退出。(5) 若节点n不可扩展，则转第2步。(6) 扩展节点n,将其子节点放入OPEN表的尾部，并为每一个子
2、节点都配置指向父节点的指 针，然后转第 2 步。三.实验结果D:nDebugnO2- exeRtTFf p 12 0 318 4P G 5R c c 3 4 5 t*t*A a u s 0 6 e 7 s E 2 丄70Step 22 3 0”显4 t? 6 5Gtcp 3 e 3 418 0/ b 5Press any heto continue四.实验结果分析 应用广度优先搜索可得到如上图所示的从初始状态到目标状态的路径。广度优先搜索盲目性较 大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。但只要问题有解，用广 度优先搜索总可以得到解，而且得到的是路径最短的解。五源代码#i
3、nclude using namespace std;#include classes.hchar element:ebegin33 = 2,8,3,1,0,4,7,6,5;char element:dest33 = 1,2,3,8,0,4,7,6,5;double element:k = 1; / if you change the k val, you may get different result. int main() list open, close; / these are two list that holds the tree node. element ebegin(ele
4、ment:ebegin);mygraph G(&ebegin);/ step 1open.pushtop(&ebegin);/G.add(&ebegin);- the construction function did it very well. while(1)/ step 2if (open.getnum() = 0) coutThis question has no solution.362880)cout out of bound errorendl;break;*/coutopen.getnum() : close.getnum()endl;-完整版学习资料分享/ step 3 el
5、ement * n;close.pushend(n = open.pop();/ step 4if (element:reach(n) coutsolution got:; G.drawtree(n); coutTotal steps:layergoup();M1 = n-godown();M2 = n-goleft();M3 = n-goright();int i;for (i = 0; i draw();if (!open.exist(Mi) & !close.exist(Mi) open.pushbyforder(Mi);else/ b & c G.changeparent(Mi, n)
6、;/ 7 order has beeen down in inserting./ 8 when we reached here, we will go to the front. system(pause); return 0;classes.h struct point int x; int y;point (int px, int py)x = px; y = py;class element public:char m33; static char dest33;static char ebegin33;int layer; static double k;int f_val;eleme
7、nt(char s33, int l = 0) layer = l + 1;for (int i = 0; i 3 ; i+) for(int j = 0; j f();point getpos()for (int i = 0; i 3 ; i+) for(int j = 0; j 3; j+) if (mij = 0) return point(i, j);system(echo unable &pause);int f()int g = 0;for(int i = 0; i 3; i+) for (int j = 0; j getpos();if (p.x 0)element* pnew
8、= new element(m, layer); pnew-mp.xp.y = pnew-mp.x - 1p.y; pnew-mp.x - 1p.y = 0;return pnew;return NULL;element * godown()point p = this-getpos();if (p.x mp.xp.y = pnew-mp.x + 1p.y; pnew-mp.x + 1p.y = 0;return pnew;return NULL;element * goleft()point p = this-getpos();if (p.y 0)element* pnew = new el
9、ement(m, layer); pnew-mp.xp.y = pnew-mp.xp.y - 1; pnew-mp.xp.y - 1 = 0;return pnew;return NULL;element * goright()point p = this-getpos();if (p.y mp.xp.y = pnew-mp.xp.y + 1; pnew-mp.xp.y + 1 = 0;return pnew;return NULL;static bool reach(element * p)for(int i = 0; i 3; i+) for(int j = 0; j mij != des
10、tij) return false;return true;void draw()coutendl;for (int i = 0; i 3 ; i+) cout|;for(int j = 0; j 3; j+) cout(int)mij ;cout|endl;bool equals(const element *p)for(int i = 0; i 3; i+) for(int j = 0; j mij != this-mij) return false;return true;template class liststruct node T * ptr;node * next;node *
11、base; / stack base pointernode * top; / stack top pointerint m_num;public:list()m_num = 0; base = top = NULL;bool pushtop(T * tp) if (base = NULL) base = top = (node *)malloc(sizeof(node); base-next = NULL; else node * tmp;tmp = (node *)malloc(sizeof(node);tmp-next = top;top = tmp;top-ptr = tp;m_num
12、+;return true;bool pushbyforder(T* tp)if (base = NULL) base = top = (node *)malloc(sizeof(node); base-next = NULL;top-ptr = tp; else node * tmp, *find = top;tmp = (node *)malloc(sizeof(node); tmp-ptr = tp;while (find != NULL) if (tmp-ptr-f_val ptr-f_val) tmp-next = find-next; find-next = tmp;if (find = top) top = tmp; break;find = find-next;if (find =
