用图搜索法：广度优先、深度优先和A算法实现八数码问题报告.doc
用图搜索法：广度优先、深度优先和A*算法实现八数码问题-报告一、 试验目的用图搜索法：广度优先、深度优先和A*算法实现八数码问题。二、 试验内容八数码问题是：将分别标有数字1，2，3，8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。三、 试验流程图及程序1238 4765问题描述：例如下图2 3184765开始状态 目标状态程序代码：#include <stdio.h>#include <string.h>typedef unsigned long UINT64;typedef structchar x; /位置x和位置y上的数字换位 char y; /其中x是0所在的位置 EP_MOVE;#define SIZE 3 /8数码问题，理论上本程序也可解决15数码问题，#define NUM SIZE * SIZE /但move_gen需要做很多修改，输入初始和结束状态的部分和check_input也要修改#define MAX_NODE 1000000#define MAX_DEP 100#define XCHG(a, b) a=a + b; b=a - b; a=a - b; #define TRANS(a, b) long iii; (b)=0; for(iii=0; iii < NUM; iii+) (b)=(b) << 4) + aiii; /将数组a转换为一个64位的整数b#define RTRANS(a, b) long iii; UINT64 ttt=(a); for(iii=NUM - 1; iii >= 0; iii-) biii=ttt & 0xf; ttt>>=4; /将一个64位整数a转换为数组b/typedef struct EP_NODE_Tag UINT64 v; /保存状态，每个数字占4个二进制位，可解决16数码问题 struct EP_NODE_Tag *prev; /父节点 struct EP_NODE_Tag *small, *big; EP_NODE;EP_NODE m_arMAX_NODE;EP_NODE *m_root;long m_depth; /搜索深度EP_NODE m_outMAX_DEP; /输出路径/long move_gen(EP_NODE *node, EP_MOVE *move)long pz; /0的位置 UINT64 t=0xf; for(pz=NUM - 1; pz >= 0; pz-) if(node->v & t) = 0) break; /找到0的位置 t<<=4; switch(pz) case 0: move0.x=0; move0.y=1; move1.x=0; move1.y=3; return 2; case 1: move0.x=1; move0.y=0; move1.x=1; move1.y=2; move2.x=1; move2.y=4; return 3; case 2: move0.x=2; move0.y=1; move1.x=2; move1.y=5; return 2; case 3: move0.x=3; move0.y=0; move1.x=3; move1.y=6; move2.x=3; move2.y=4; return 3; case 4: move0.x=4; move0.y=1; move1.x=4; move1.y=3; move2.x=4; move2.y=5; move3.x=4; move3.y=7; return 4; case 5: move0.x=5; move0.y=2; move1.x=5; move1.y=4; move2.x=5; move2.y=8; return 3; case 6: move0.x=6; move0.y=3; move1.x=6; move1.y=7; return 2; case 7: move0.x=7; move0.y=6; move1.x=7; move1.y=4; move2.x=7; move2.y=8; return 3; case 8: move0.x=8; move0.y=5; move1.x=8; move1.y=7; return 2; return 0;long mov(EP_NODE *n1, EP_MOVE *mv, EP_NODE *n2) /走一步，返回走一步后的结果 char ssNUM; RTRANS(n1->v, ss); XCHG(ssmv->x, ssmv->y); TRANS(ss, n2->v); return 0;long add_node(EP_NODE *node, long r) EP_NODE *p=m_root; EP_NODE *q; while(p) q=p; if(p->v = node->v) return 0; else if(node->v > p->v) p=p->big; else if(node->v < p->v) p=p->small; m_arr.v=node->v; m_arr.prev=node->prev; m_arr.small=NULL; m_arr.big=NULL; if(node->v > q->v) q->big= &m_arr; else if(node->v < q->v) q->small= &m_arr; return 1;/*得到节点所在深度*/long get_node_depth(EP_NODE *node) long d=0; while(node->prev) d+; node=node->prev; return d;/*返回值：成功返回搜索节点数，节点数不够(-1)，无解(-2)*/long bfs_search(char *begin, char *end) long h=0, r=1, c, i, j; EP_NODE l_end, node, *pnode; EP_MOVE mv4; /每个局面最多4种走法 TRANS(begin, m_ar0.v); TRANS(end, l_end.v); m_ar0.prev=NULL; m_root=m_ar; m_root->small=NULL; m_root->big=NULL; while(h < r) && (r < MAX_NODE - 4) c=move_gen(&m_arh, mv); for(i=0; i < c; i+) mov(&m_arh, &mvi, &node); node.prev= &m_arh; if(node.v = l_end.v) pnode= &node; j=0; while(pnode->prev) m_outj=*pnode; j+; pnode=pnode->prev; m_depth=j; return r; if(add_node(&node, r) r+; /只能对历史节点中没有的新节点搜索，否则会出现环 h+; printf("rSearch.%9d/%d %d", h, r, get_node_depth(&m_arh); if(h = r) return -2; else return -1; long check_input(char *s, char a, long r) long i; for(i=0; i < r; i+) if(si = a - 0x30) return 0; return 1;long check_possible(char *begin, char *end) char fs; long f1=0, f2=0; long i, j; for(i=0; i < NUM; i+) fs=0; for(j=0; j < i; j+) if(begini != 0) && (beginj != 0) && (beginj < begini) fs+; f1+=fs; fs=0; for(j=0; j < i; j+) if(endi != 0) && (endj != 0) && (endj < endi) fs+; f2+=fs; if(f1 & 1) = (f2 & 1) return 1; else return 0;void output(void) long i, j, k; char ssNUM; for(i=m_depth - 1; i >= 0; i-) RTRANS(m_outi.v, ss); for(j=0; j < SIZE; j+) for(k=0; k < SIZE; k+) printf("%2d", ssSIZE * j + k); printf("n"); printf("n"); int main(void) char s1NUM; char s2NUM; long r; char a; printf("请输入开始状态:"); r=0; while(r < NUM) a=getchar(); if(a >= 0x30 && a < 0x39 && check_input(s1, a, r) s1r+=a - 0x30; printf("%c", a); printf("n请输入结束状态:"); r=0; while(r < NUM) a=getchar(); if(a >= 0x30 && a < 0x39 && check_input(s2, a, r) s2r+=a - 0x30; printf("%c", a); printf("n"); if(check_possible(s1, s2) r=bfs_search(s1, s2); printf("n"); if(r >= 0) printf("查找深度=%d,所有的方式=%ldn", m_depth, r); output(); else if(r = -1) printf("没有找到路径.n"); else if(r = -2) printf("这种状态变换没有路径到达.n"); else printf("不确定的错误.n"); else printf("不允许这样移动!n"); return 0; （1） 把起始节点s放到OPEN 表中，计算f（S） ，并把其值与节点S联系起来。（2） 如果OPEN 是个空表，则失败退出，无解。（3） 从OPEN 表中选择一个f值最小的节点i。结果有几个节点合适，当其中有一个为目标节点时，则选择此目标节点，否则就选择任意一个节点作为节点i。（4） 把节点i从OPEN 表中移出，并把它放入CLOSED 的扩展节点表中。（5） 如果i是目标节点，则成功退出，求得一个解。（6） 扩展节点i，生成其全部后继节点。对于i的没一个后继节点j：计算f ( j );如果j既不在OPEN 表中，也不在CLOSED 表中，则用估价函数f 把它添加到OPEN 表中。从j 加一指向其父辈节点i的指针以便一旦找到目标节点时记住一个解答途径。如果j已经在OPEN 表或CLOSED 表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中f值。如果新的f 值较小，则以此新值代替旧值。从j指向i，而不是指向它的父辈节点。如果节点j在CLOSED表中，则把它移回OPEN 表中。(7) 转向（2）。 试验结果：试验结论：问题的求解过程就是搜索的过程，采用适合的搜索算法是很关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。 通过这次试验使我对搜索算法有了一定的了解，也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验使我受益匪浅。
