《实验三：A星算法求解8数码问题实验》由会员分享，可在线阅读，更多相关《实验三：A星算法求解8数码问题实验（25页珍藏版）》请在金锄头文库上搜索。
1、实验三：A算法求解8数码问题实验一、 实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A算法求解N数码难题，理解求解流程和搜索顺序。二、 实验内容1、 八数码问题描述所谓八数码问题起源于一种游戏:在一个3的方阵中放入八个数码1、2、3、4、5、6、8，其中一个单元格是空的。将任意摆放的数码盘（城初始状态）逐步摆成某个指定的数码盘的排列（目标状态），如图1所示 图1八数码问题的某个初始状态和目标状态对于以上问题，我们可以把数码的移动等效城空格的移动。如图1的初始排列，数码7右移等于空格左移。那么对于每一个排列，可能的一次数码移动最多只有4中,即空格左移、空格右移、空格上移、空格下移
2、。最少有两种（当空格位于方阵的4个角时)。所以,问题就转换成如何从初始状态开始,使空格经过最小的移动次数最后排列成目标状态。2、 八数码问题的求解算法2.盲目搜索 宽度优先搜索算法、深度优先搜索算法2. 启发式搜索 启发式搜索算法的基本思想是:定义一个评价函数,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。 先定义下面几个函数的含义: *(n)=g(n）+h（n) (1） 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;*(n)表示从当前节点n到目标节点g的最短路径的耗散值，*（）表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如（）式所示:
3、 f(）g（）h(） （2)其中n是被评价的当前节点.f(n)、(n）和h(n）分别表示是对f*（n)、g*(n）和（n)3个函数值的估计值。利用评价函数（n)=g（）+(n）来排列E表节点顺序的图搜索算法称为算法.在A算法中，如果对所有的x， h(x）=（x) (）成立，则称好h（x)为（）的下界，它表示某种偏于保守的估计。采用h*(）的下界h（x）为启发函数的算法，称为A算法。针对八数码问题启发函数设计如下:f(n)（）+p(n） （4)其中A*算法中的(n)根据具体情况设计为（n）,意为节点的深度，而h(n）设计为把S放入OPEN表，记f=hOPEN=NULL?是失败扩展BESTNODE
4、,产生其后继结点SUCCESSOR选取OPEN表上未设置过的具有最小f值的节点BESTNODE,放入CLOSED表BESTNODE是目标节点建立从SUCCESSOR返回BESTNODE的指针计算g(SUC)=g(BES)+k(BES,SUC)SUCOPEN开始g(SUC)next； i（f headnextf）/考虑插入的节点值比链表的第一个节点值小 p-next heanext;he = ; ele wil（qnext)/考虑插入节点x，形如a= x =bf（qf pf |qf =p-f) & （nexf p-f q-extf p-） -net=q-next； qnext p； bre； q
5、-next; if（q-next = NL） /考虑插入的节点值比链表最后一个元素的值更大 -next ； ele ha-net = p；/-/删除节点函数入口/-voiddel_ode(sc Nod* he， struct Noe*p )strt oe *q； q hea； il（qnext) f(qnext =p) qnxt -net； pnex =NUL； if(q-next =L) retur; /free(p)； q = q-nxt； /-/判断两个数组是否相等函数入口/-intequa(nt s133， ints23) iti，j，fla=0; for（i=； i3 ；i+） fr（=； jnext; int fg=0； we（） f（equal（qs，s）)flag=1； Old_odenxt ； return ; ese = -ext；if（!lag） rturn ；/-/计算p（n）的函数入口/其中（n）为放错位的数码与其正确的位置之间距离之和具体方法：放错
