《用图搜索法：广度优先、深度优先和A算法实现八数码问题报告.doc》由会员分享，可在线阅读，更多相关《用图搜索法：广度优先、深度优先和A算法实现八数码问题报告.doc（7页珍藏版）》请在三一办公上搜索。
1、用图搜索法：广度优先、深度优先和A*算法实现八数码问题-报告一、 试验目的用图搜索法：广度优先、深度优先和A*算法实现八数码问题。二、 试验内容八数码问题是：将分别标有数字1，2，3，8的八块正方形数码牌任意地放在一块33的数码盘上。放牌时要求不能重叠。于是，在33的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。三、 试验流程图及程序12384765问题描述：例如下图23184765开始状态 目标状态程序代码：#include #include typedef unsigned long UINT64;typedef
2、 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=
3、0; iii NUM; iii+) (b)=(b) = 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
4、 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的位置 tv, 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; el
5、se if(node-v p-v) p=p-big; else if(node-v 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 v) q-small= &m_arr; return 1;/*得到节点所在深度*/long get_node_depth(EP_NODE *node) long d=0; while(node-prev) d+; node=node-prev; retu
6、rn 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=m
7、ove_gen(&m_arh, mv); for(i=0; i 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=
8、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 = 0
9、; 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 = 0x30 & a 0x39 & check_input(s1, a, r) s1r+=a - 0x30; printf(%c, a); printf(n请输入结束状态:); r=0;
10、 while(r = 0x30 & a = 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。结果有几
11、个节点合适，当其中有一个为目标节点时，则选择此目标节点，否则就选择任意一个节点作为节点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）。试验结果：试验结论：问题的求解过程就是搜索的过程，采用适合的搜索算法是很关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。 通过这次试验使我对搜索算法有了一定的了解，也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验使我受益匪浅。
