深度宽度优先搜索---八数码

.

. 八数码问题

具体思路：

宽度优先算法实现过程

（1）把起始节点放到OPEN 表中；

（2）如果OPEN 是个空表，则没有解，失败退出；否则继续；

（3）把第一个节点从OPEN 表中移除，并把它放入CLOSED 的扩展节点表中；

（4）扩展节点n 。如果没有后继节点，则转向（2）

（5）把n 的所有后继结点放到OPEN 表末端，并提供从这些后继结点回到n 的指针；

（6）如果n 的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2）。

Y

.

深度优先实现过程

（1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解；（2）如果OPEN为一空表，则失败退出；

（3）把第一个节点从OPEN表移到CLOSED表；

（4）如果节点n的深度等于最大深度，则转向（2）；

（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；

（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。

.

方法一：用C语言实现

#include

#include

#include

typedef long UINT64;

typedef struct

{

char 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) + a[iii]; }*/ //将数组a转换为一个64位的整数b

#define RTRANS(a, b) \

{ \

long iii; \

.

.

UINT64 ttt=(a); \

for(iii=NUM - 1; iii >= 0; iii--) \

{ \

b[iii]=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_ar[MAX_NODE];

EP_NODE *m_root;

long m_depth; //搜索深度

EP_NODE m_out[MAX_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:

move[0].x=0;

move[0].y=1;

move[1].x=0;

move[1].y=3;

return 2;

case 1:

move[0].x=1;

move[0].y=0;

move[1].x=1;

move[1].y=2;

move[2].x=1;

move[2].y=4;

return 3;

case 2:

move[0].x=2;

.

. move[0].y=1;

move[1].x=2;

move[1].y=5;

return 2;

case 3:

move[0].x=3;

move[0].y=0;

move[1].x=3;

move[1].y=6;

move[2].x=3;

move[2].y=4;

return 3;

case 4:

move[0].x=4;

move[0].y=1;

move[1].x=4;

move[1].y=3;

move[2].x=4;

move[2].y=5;

move[3].x=4;

move[3].y=7;

return 4;

.

. case 5:

move[0].x=5;

move[0].y=2;

move[1].x=5;

move[1].y=4;

move[2].x=5;

move[2].y=8;

return 3;

case 6:

move[0].x=6;

move[0].y=3;

move[1].x=6;

move[1].y=7;

return 2;

case 7:

move[0].x=7;

move[0].y=6;

move[1].x=7;

move[1].y=4;

move[2].x=7;

move[2].y=8;

return 3;

.

.

case 8:

move[0].x=8;

move[0].y=5;

move[1].x=8;

move[1].y=7;

return 2;

}

return 0;

}

long mov(EP_NODE *n1, EP_MOVE *mv, EP_NODE *n2) //走一步，返回走一步后的结果

{

char ss[NUM];

RTRANS(n1->v, ss);

XCHG(ss[mv->x], ss[mv->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_ar[r].v=node->v;

m_ar[r].prev=node->prev;

m_ar[r].small=NULL;

m_ar[r].big=NULL;

if(node->v > q->v)

{ q->big= &m_ar[r];

}

else if(node->v < q->v)

{ q->small= &m_ar[r];

}

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 mv[4]; //每个局面最多4种走法

TRANS(begin, m_ar[0].v);

TRANS(end, l_end.v);

m_ar[0].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_ar[h], mv);

for(i=0; i < c; i++)

{ mov(&m_ar[h], &mv[i], &node);

node.prev= &m_ar[h];

if(node.v == l_end.v)

.

本文来源：https://www.bwwdw.com/article/d7pq.html