《深度宽度优先搜索》由会员分享，可在线阅读，更多相关《深度宽度优先搜索（32页珍藏版）》请在金锄头文库上搜索。
1、八数码问题具体思路:宽度优先算法实现过程（1）把起始节点放到OPEN表中；（2）如果OPEN是个空表，则没有解，失败退出；否则继续；（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；（4）扩展节点n。如果没有后继节点，则转向（2）（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2）。深度优先实现过程（1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解；（2）如果OPEN为一空表，则失败退出；（3）把第一个节点从OPEN表移到CLOS
2、ED表；（4）如果节点n的深度等于最大深度，则转向（2）；（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。方法:用C语言实现#include #include #includetypedef long UINT64;typedef struct(char x; 位置x和位置y上的数字换位char y; 其中x是0所在的位置 EP_MOVE;#define SIZE 3 /8数码问题，理论上本程序也可解决15数码问题，#define NUM SIZE * SIZE /但mov
3、e_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) = 0; iii-) ( biii=ttt & 0xf; ttt=4; /将一个64位整数a转换为数组b/typedef struct EP_NODE_Tag( UINT64 v; 保
4、存状态，每个数字占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) (
5、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;else 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
6、(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;return d;/*返回值：成功一返回搜索节点数，节点数不够一(-1)，无解一(-2)*/long bfs_search(char *begin, char *end)( long h=0, r=1, c, i, j；EP_NODE l_end, node, *pno
7、de;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 prev)( m_outj=*pnode;j+;pnode二pnode-prev; m_depth=j;return r;if(add_node(&node, r) r+; 只能对历史节点中没有的新节点搜索，
8、否则会出现环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
9、; 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; 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请输入结束状态:)；while(r = 0x30 & a 0x39 & check_input(s2, a, r)( s2r+=a - 0x30;printf(%c, a);printf(n)；
