九宫问题.docx

1、九宫问题（十一）九宫问题)题目叙述：九宫问题又称“八数码问题”，是说在33的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，从某种初始状态开始，对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态变换至目标状态。求其最少步数。/*/* EIGHT DIGIT PROBLEM */* 唐国峰 2012年4月23日 */*/ / 预编译命令#include iostream#include stdlib.husing namespace std;/棋盘大小#define size 3/定义二维数组来存储数据表示某一个特定状态typedef int statussize

2、size;/定义状态图中的节点数据结构，即节点的状态信息等typedef struct Node status data; /节点所存储的状态 struct Node *parent; /指向节点的父亲节点 struct SpringLink *child; /指向节点的后继节点 struct Node *next; /指向链表的后一个节点 int f_value; /由初始状态经由当前节点至目标状态的总耗散值 int g_value; /由初始状态经到当前节点实际耗散值 int h_value; /由当前节点到目标状态的预计耗散值NNode, *PNode;/定义表述指向当前节点的扩展节点的

3、链表typedef struct SpringLink struct Node *pointData; /指向节点的指针 struct SpringLink *next; /指向当前节点的其他扩展节点SPLink, *PSPLink;/声明OPEN表和CLOSED表PNode open;PNode closed;/计算棋盘状态的逆序数int InverseNumber(status a) int i, j, sum=0; int data_changsize*size=0; /将二维数组转换成一维数组，以方便求逆序数 for(i=0;isize;i+) for(j=0;jsize;j+) da

4、ta_changi*size+j=aij; /计算序列中除零外的逆序数 for(i=0;i=0;j-) /当后一个数比前一个数小时 if(data_changinext = NULL;/判断链表是否为空bool isEmpty(PNode Head) if(Head-next = NULL) return true; else return false; /从链表中拿出一个数据void popNode(PNode &Head , PNode &FNode) if(isEmpty(Head) FNode = NULL; return; FNode = Head-next; Head-next =

5、 Head-next-next; FNode-next = NULL;/向节点的最终后继节点链表中添加新的子节点void addSpringNode(PNode &Head , PNode newData) PSPLink newNode = (PSPLink)malloc(sizeof(SPLink); newNode-pointData = newData; newNode-next = Head-child; Head-child = newNode;/释放状态图中存放节点后继节点地址的空间void freeSpringLink(PSPLink &Head) PSPLink tmm; w

6、hile(Head != NULL) tmm = Head; Head = Head-next; free(tmm); /释放open表与closed表中的资源void freeLink(PNode &Head) PNode tmn; tmn = Head; Head = Head-next; free(tmn); while(Head != NULL) /首先释放存放节点后继节点地址的空间 freeSpringLink(Head-child); tmn = Head; Head = Head-next; free(tmn); /向普通链表中添加一个节点void addNode(PNode &

7、Head , PNode &newNode) newNode-next = Head-next; Head-next = newNode;/向非递减排列的链表中添加一个节点void addAscNode(PNode &Head , PNode &newNode) PNode P; PNode Q; P = Head-next; Q = Head; while(P != NULL & P-f_value f_value) Q = P; P = P-next; /上面判断好位置之后，下面就是简单的插入节点了 newNode-next = Q-next; Q-next = newNode;/计算节点

8、到目标状态的预计耗散值int computeh_value(PNode theNode,status targetStatus) int num = 0; for(int i = 0 ; i 3 ; i+) for(int j = 0 ; j dataij != targetStatusij) num+; return num;/计算节点的f，g，h值void computeAllValue(PNode &theNode , PNode parentNode, status targetStatus) if(parentNode = NULL) theNode-g_value = 0; els

9、e theNode-g_value = parentNode-g_value + 1; theNode-h_value = computeh_value(theNode,targetStatus); theNode-f_value = theNode-g_value + theNode-h_value;/初始化函数，进行算法初始条件的设置void initial(status startStatus,status targetStatus) /初始化open以及closed表 initLink(open); initLink(closed); /初始化起始节点，令初始节点的父节点为空节点 PN

10、ode NULLNode = NULL; PNode StartNode = (PNode)malloc(sizeof(NNode); for(int i = 0 ; i 3 ; i+) for(int j = 0 ; j dataij = startStatusij; StartNode-parent = NULL; StartNode-child = NULL; StartNode-next = NULL; computeAllValue(StartNode, NULLNode,targetStatus); /起始节点进入OPEN表 addAscNode(open , StartNode)

11、;/将B节点的状态赋值给A节点void statusAEB(PNode &ANode , PNode BNode) for(int i = 0 ; i 3 ; i+) for(int j = 0 ; j dataij = BNode-dataij; /两个节点是否有相同的状态bool hasSameStatus(PNode ANode , PNode BNode) for(int i = 0 ; i size ; i+) for(int j = 0 ; j dataij != BNode-dataij) return false; return true;/节点与其祖先节点是否有相同的状态bo

12、ol hasAnceSameStatus(PNode OrigiNode , PNode AnceNode) while(AnceNode != NULL) if(hasSameStatus(OrigiNode , AnceNode) return true; AnceNode = AnceNode-parent; return false;/取得方格中空的格子的位置void getPosition(PNode theNode , int &row , int &col) for(int i = 0 ; i size ; i+) for(int j = 0 ; j dataij = 0) ro

13、w = i; col = j; return; /交换两个数字的值void changeAB(int &a , int &b) int c; c = b; b = a; a = c;/检查相应的状态是否在某一个链表中bool inLink(PNode spciNode , PNode theLink , PNode &theNodeLink , PNode &preNode) preNode = theLink; theLink = theLink-next; while(theLink != NULL) if(hasSameStatus(spciNode , theLink) theNode

14、Link = theLink; return true; preNode = theLink; theLink = theLink-next; return false;/产生节点的后继节点链表void SpringLink(PNode theNode , PNode &spring, status targetStatus) int row; int col; getPosition(theNode , row , col); /空的格子右边的格子向左移动 if(col != 2) PNode rlNewNode = (PNode)malloc(sizeof(NNode); statusAE

15、B(rlNewNode, theNode); changeAB(rlNewNode-datarowcol, rlNewNode-datarowcol + 1); if(hasAnceSameStatus(rlNewNode, theNode-parent) free(rlNewNode);/与父辈相同，丢弃本节点 else rlNewNode-parent = theNode; rlNewNode-child = NULL; rlNewNode-next = NULL; computeAllValue(rlNewNode, theNode, targetStatus); /将本节点加入后继节点

16、链表 addNode(spring, rlNewNode); /空的格子左边的格子向右移动 if(col != 0) PNode lrNewNode = (PNode)malloc(sizeof(NNode); statusAEB(lrNewNode, theNode); changeAB(lrNewNode-datarowcol, lrNewNode-datarowcol - 1); if(hasAnceSameStatus(lrNewNode, theNode-parent) free(lrNewNode);/与父辈相同，丢弃本节点 else lrNewNode-parent = theN

17、ode; lrNewNode-child = NULL; lrNewNode-next = NULL; computeAllValue(lrNewNode, theNode, targetStatus); /将本节点加入后继节点链表 addNode(spring , lrNewNode); /空的格子上边的格子向下移动 if(row != 0) PNode udNewNode = (PNode)malloc(sizeof(NNode); statusAEB(udNewNode , theNode); changeAB(udNewNode-datarowcol, udNewNode-dataro

18、w - 1col); if(hasAnceSameStatus(udNewNode, theNode-parent) free(udNewNode);/与父辈相同，丢弃本节点 else udNewNode-parent = theNode; udNewNode-child = NULL; udNewNode-next = NULL; computeAllValue(udNewNode, theNode, targetStatus); /将本节点加入后继节点链表 addNode(spring, udNewNode); /空的格子下边的格子向上移动 if(row != 2) PNode duNew

19、Node = (PNode)malloc(sizeof(NNode); statusAEB(duNewNode, theNode); changeAB(duNewNode-datarowcol, duNewNode-datarow + 1col); if(hasAnceSameStatus(duNewNode, theNode-parent) free(duNewNode);/与父辈相同，丢弃本节点 else duNewNode-parent = theNode; duNewNode-child = NULL; duNewNode-next = NULL; computeAllValue(du

20、NewNode, theNode, targetStatus); /将本节点加入后继节点链表 addNode(spring , duNewNode); /输出给定节点的状态void outputStatus(PNode stat) for(int i = 0 ; i 3 ; i+) for(int j = 0 ; j 3 ; j+) cout dataij ; cout g_value; if(goal-parent != NULL) outputBestRoad(goal-parent); cout 第 deepnum- 步的状态： endl; outputStatus(goal);void

21、 AStar(status startStatus,status targetStatus) PNode tmpNode; /指向从open表中拿出并放到closed表中的节点的指针 PNode spring; /tmpNode的后继节点链 PNode tmpLNode; /tmpNode的某一个后继节点 PNode tmpChartNode; PNode thePreNode; /指向将要从closed表中移到open表中的节点的前一个节点的指针 bool getGoal = false; /标识是否达到目标状态 long numcount = 1; /记录从open表中拿出节点的序号 in

22、itial(startStatus,targetStatus); /对函数进行初始化 initLink(spring); /对后继链表的初始化 tmpChartNode = NULL; cout 从OPEN表中拿出的节点的状态及相应的值 endl; while(!isEmpty(open) /从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中 popNode(open, tmpNode); addNode(closed, tmpNode); cout 第 numcount+ 个状态是： endl; outputStatus(tmpNode); cout 其f值为： f_value endl; cout 其g值为： g_value endl; cout 其h值为： h_value g_value g_value) tmpChartNode-parent = tmpLNode-parent; tmpChartNode-g_value = tmpLNode-g_value; tmpChartNode-f_value = tmpLNode-f_value; fre