实验三：A星算法求解8数码问题实验

实验3: A*算法解决8数字问题实验。一、实验目的熟悉和掌握启发式搜索的定义、评估函数和算法过程，利用A*算法解决n数字问题，了解解决方案过程和搜索顺序。二、实验内容1、8数字问题说明游戏：在33个正方形内放了8个数字1，2，3，4，5，6，7，8，其中一个是空的。如图1所示，将任意数字磁盘(城市初始状态)逐步放置到指定数字磁盘的校准(目标状态)图1 8数字问题的初始状态和目标状态对于这个问题，我们可以把数字的运动与城市空间的运动相媲美。在图1的初始对齐中，数字7等于左空格。对于每个阵列，数字移动最多为4个。即向左移动空格、向右移动空格、向上移动空格、向下移动空格等。至少两个(如果空格位于正方形的四个角点上)。因此，问题从初始状态开始，切换为空格以最小移动次数对齐到目标状态的方式。2、8数字故障诊断算法2.1盲目搜索宽度优先搜索算法，深度优先搜索算法2.2启发式搜索启发式搜索算法的基本思想是定义评估函数f，它评估当前搜索状态，查找和扩展最有希望的节点之一。首先，定义以下函数的含义：F*(n)=g*(n) h*(n) (1)表达式中的g*(n)表示从初始节点s到当前节点n的最短路径的耗散值。H*(n)表示从当前节点n到目标节点g的最短路径的保险存储值，f*(n)表示从初始节点s到目标节点g的最短路径的保险存储值。评价函数的形式可以像(2)表达式那样定义。F(n)=g(n) h(n) (2)其中n是评估的当前节点。F(n)、g(n)和h(n)分别表示对以下三个函数值的估计：f*(n)、g*(n)和h * (n)。使用计算函数f(n)=g(n) h(n)排列OPEN表节点顺序的图形搜索算法称为算法a。在a算法中，对于所有xH(x)=h*(x) (3)如果成立，则把h(x)称为h*(x)的下限，表示一种保守的估计。将H*(x)的下限h(x)用作启发式函数的A算法，称为A*算法。8个数字问题的灵感函数的设计如下：F(n)=d(n) p(n) (4)其中，A*算法的g(n)根据情况设计为d(n)，表示n节点的深度，h(n)设计为将s放入OPEN表中，并记住f=hOPEN=NULL？是失败展开BESTNODE以创建下一个节点SUCCESSOR选择OPEN表中未设置最小f值的节点BESTNODE，插入CLOSED表BESTNODE是目标节点设置从SUCCESSOR返回BESTNODE的指针计算g(SUC)=g(BES) k(BES，SUC)SUCOPEN开始G(SUC)#include#include/8数字状态相应的节点结构Structnodeint s33；/储存8位数的状态。0表示空格Int f、g；/灵感函数的f和g值Struct Node * nextStruct Node * previous/保存父节点int open _ N=0；/记录Open列表中的节点数/8数字初始状态Int inital_s33=2，8，3，1，6，4，7，0，5/8数字目标状态Int final_s33=1，2，3，8，0，4，7，6，5/-是的-是的添加/节点函数条目，方法：插入排序以添加到指定表/-是的-是的Void add _ node (structnode * head，structnode * p)struct Node * q；考虑平视/关联列表为空 q=head-next；If(p-f head-next-f)/考虑插入小于连接列表中第一个节点值的节点值p-next=head-next；head-next=p；Else考虑插入节点x，例如While(q-next)/a=x=bif(q-f p-f | | q-f=p-f)(q-next-f p-f | | q-next-f=p-f)p-next=q-next；q-next=p；Breakq=q-next；If(q-next=NULL) /考虑插入大于连接列表中最后一个元素值的节点值q-next=p；else head-next=p；/-是的-是的/删除节点函数条目/-是的-是的Void del _ node (structnode * head，structnode * p)struct Node * q；Q=headWhile(q-next)If(q-next=p)q-next=p-next；p-next=NULL；if(q-next=NULL)return；/free(p)；q=q-next；/-是的-是的/确定两个数组是否等于函数的入口/-是的-是的Int equal (ints1 3 3，ints2 3 3)Int i、j、flag=0；for(I=0)；I 3；I)for(j=0)；j 3；j)If(s1ij！=S2Ij) flag=1；BreakIf(！旗标)return 1；else return 0；/-是的-是的/确定后续节点是否位于Open或Closed表的函数入口中/-是的-是的Intexit _ node (structnode * head，ints 3 3，structnode * old _ node)struct Node * q=head-next；int flag=0；While(q)If (equal (q-s，s)flag=1；old _ Node-next=q；return 1；else q=q-next；If(！flag)return 0；/-是的-是的/计算p(n)的函数条目/其中p(n)是放置错误的数字与其位置之间的距离总和/特定方法：放错位置的数字及其正确位置是下标差异绝对值的总和/-是的-是的Int wrong_sum(int s33)Int i、j、fi、fj、sum=0；for(I=0)；i3；I)for(j=0)；J3；j)for(fi=0)；Fi3Fi)for(FJ=0)；Fj3Fj)if(final _ sfiFJ=sIj)总计=fab(I-fi)fab(j-FJ)；BreakReturn sum/-是的-是的/获取后续节点函数入口/确认每个空格移动的正当性，如果合适，移动空格以获得后续子节点/-是的-是的int get _ SUCCESSOR(struct node * best node，int direction，struct node * succssor)/best node，以建立后续节点succssorInt i、j、i_0、j_0、tempfor(I=0)；i3；I)