1、-1-八数码问题具体思路：宽度优先算法实现过程（1）把起始节点放到 OPEN 表中；（2）如果 OPEN 是个空表，则没有解，失败退出；否则继续；（3）把第一个节点从 OPEN 表中移除，并把它放入 CLOSED 的扩展节点表中；（4）扩展节点 n。如果没有后继节点，则转向（2）（5）把 n 的所有后继结点放到 OPEN 表末端，并提供从这些后继结点回到 n 的指针；（6）如果 n 的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2） 。开始把 S 放入 OPEN 表OPEN 表为空 失败把第一个节点 n 从把 S 放入OPEN 表移除，放到 CLOSED表中移除扩展 n，把
2、它的后继节点放入OPEN 表的末端，提供回到 n的指针是否任何节点为目标节点成功-2-深度优先实现过程（1）把起始节点 S 放入未扩展节点 OPEN 表中。如果此节点为一目标节点，则得到一个解；（2）如果 OPEN 为一空表，则失败退出；（3）把第一个节点从 OPEN 表移到 CLOSED 表；（4）如果节点 n 的深度等于最大深度，则转向（2） ；（5）扩展节点 n，产生其全部后裔，并把它们放入 OPEN 表的前头。如果没有后裔，则转向（2） ；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2） 。开始把 S 放入 OPEN 表S 是否为目标节点 成功把第一个节点
3、n 从把 S 放入 OPEN表移除，放到 CLOSED 表中移除 节点 n 的深度是否等于最深界限OPEN 表为空失败扩展 n，把它的后继放入 OPEN 表的前头，提供回到 n 的指针是否有任何后继节点为目标节点 成功-3-方法一：用 C 语言实现#include #include #includetypedef long UINT64;typedef structchar x; /位置 x 和位置 y 上的数字换位char y; /其中 x 是 0 所在的位置 EP_MOVE;#define SIZE 3 /8 数码问题，理论上本程序也可解决 15 数码问题，#define NUM SIZE
4、 * SIZE /但 move_gen 需要做很多修改，输入初始和结束状态的部分和 check_input 也要修改-4-#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 = 0; iii-) biii=ttt ttt=4; /将一个 64 位整数 a 转换为数组 b/typedef struct EP_NODE_Tag UINT64 v; /保存状态，每个数
5、字占 4 个二进制位，可解决 16 数码问题struct EP_NODE_Tag *prev; /父节点struct EP_NODE_Tag *small, *big; EP_NODE;EP_NODE m_arMAX_NODE;-5-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 /找到 0 的位置tv
6、, ss);XCHG(ssmv-x, ssmv-y);TRANS(ss, n2-v);return 0;-9-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(node-v q-v) q-
7、big= else if(node-v v) q-small= return 1;/*得到节点所在深度*/-10-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) for(i=0; i c; i+) mov(
