八数码难题代码与基本思路Eightpuzzles

《八数码难题代码与基本思路Eightpuzzles》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图搜索求解八数码算法--A*算法（步程差）一.流程框图开始U将Begin放入storage,记Value=30拓展首节点，计算步程差存入storage,深度自增二.算法基本原理拓展节点并计算步程差,如果是目标节点，成功并退出，如果不是,判断是否为优质节点，是则拓展为子节点，否则舍弃；判断深度是否越界，是则失败，未越界则继续拓展节点，若拓展表为空，则失败退出。八数码结构体由矩阵Array,步稈差Value,屏蔽方向Undirect和父节点指针^parent四部分组成，Array存放矩阵数字状态，Value存放估值函数

2、值，UndirectiL录上一步移动方向避免逆推，^parentiL录父子关系用于寻径。三.模块分析Getgraph键盘输入获得初始数码组并返回Graph结构体指针。Printgraph输入八数码结构体地址，打印矩阵数字状态与当前步程差。Evaluate输入目标矩阵与当前矩阵，计算步程差并返回值。Move输入当前矩阵与移动方向Direct,移动并返回新结构体地址。Search输入起始结构体与冃标结构体，尝试寻径并记录路径并返回终点地址(若成功)或返回空指针(若失败)。Main主函数，定义目标矩阵并调用函数。四.源代

3、码//Eight-figurepuzzle//A*#includez/stdafx.h"#include#includeSdefineN3//数码组长度#defineMAX50//最人搜索深度tvpedefstructnode//八数码结构体{intarray[N][N]://数码组intValue;//评估值intUndirect;//所屏蔽方向,防止往冋推到上已状态，1上2卜‘3左4右struetnode*parent;//父节点}Graph;Graph^Storage[M

4、AX];//拓展节点存储队歹!JGraph*path[MAX];//路径堆栈Graph*GetGraph(Graph*New_graph)////////fl定义初始数码组{intx;for(x=0;xarray[x][0],&New_graph->array[x][1],&Newgraph->array[x][2]);}Newgraph->Value=30;Newgraph->Undirect=0;Newgraph-〉parent=NULL;r

5、eturnYewgraph;}—voidPrintGraph(Graph*point_graph)/////////打印数码组{inti,j;if(point_graph=NULL)printf("NULL");else{printf(〃〃)；for(i=0;i

6、“)；for(j=0;jarray[i][j]);}printf("

7、");if(i=NT)printf(z，Value%d“，point_graph-

8、>Value);//评估函数值printf("");}printf(“〃)；}}intEvaluate(Graph*point_graph,Graph*I:nd_graph)/////////评价函数{intvalue=0;//评估值inti,j,m,n;for(i=0;iarray[i][j]==End_graph->array[m][n])value=va

9、lue+abs(i-m)+abs(j-n);//数字当前位置与目标位置步程差之和}}}}pointgraph~>Value=value;returnvalue;Graph*Move(Graph*point_graph,intDirect)/////////移动数码组{Graph*New_graph;intBlankLocate=0;//定位空格指示intMovable=1;//移动有效inti,j,xO,yO,x,y;for(i=0;i

10、ntgraph->arrav[i][j]二二0){BlankLocate=1;break;}}if(BlankLocate==1)break;}xO=i;y0=j;switch(Direct){case1://上xO—;if(x0<0)Movable=0;break;case2://下x0++;if(xO>=N)Movable=0;break;case3:/