文档介绍：实验大作业实验题目:、实验目的:熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A算法求解九宫问题,理解求解流程和搜索顺序。二、实验方法:;、C++或JAVA语言编程实现实验内容。三、实验背景知识:,为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。这些控制信息反映在估价函数中。估价函数的任务就是估计待搜索节点的重要程度,给这些节点排定次序。估价函数可以是任意一种函数,如有的定义它是节点x处于最佳路径的概率上,或是x节点和目标节点之间的距离等等。在此,我们把估价函数f(n)定义为从初始节点经过n节点到达目标节点的最小代价路径的代价估计值,它的一般形式是:f(n)=g(n)+h(n)其中g(n)是从初始节点到节点n的实际代价,g(n)可以根据生成的搜索树实际计算出来;h(n)是从n到目标节点的最佳路径的代价估计,h(n)主要体现了搜索的启发信息。(1)可采纳性当一个搜索算法在最短路径存在的时候能保证能找到它,我们就称该算法是可采纳的。所有A*算法都是可采纳的。(2)单调性一个启发函数h是单调的,如果对所有的状态ni和nj,其中nj是ni的子孙,h(ni)-h(nj)≤cost(ni,nj),其中cost(ni,nj)是从ni到nj实际代价。目标状态的启发函数值为0,即h(Goal)=(不减)。(3)信息性比较两个启发策略h1和h2,如果对搜索空间中的任何一个状态n都有h1(n)≤h2(n),就说h2比h1具有更多的信息性。一般而言,若搜索策略h2比h1有更多的信息性,则h2比h1考察的状态要少。但必须注意的是更多信息性需要更多的计算时间,从而有可能抵消减少搜索空间所带来的益处。(1)局部择优搜索算法(瞎子爬山法)瞎子爬山法是最简单的启发式算法之一。该算法在搜索过程中扩展当前节点并估价它的子节点。最优的子节点别选择并进一步扩展;该子节点的兄弟节点和父节点都不再被保留。当搜索到达一种状态,该状态比它的所有子状态都要好,则搜索停止。因此,该算法的估价函数可表示为f(n)=h(n)。在一个限定的环境下,瞎子爬山法可能会极大的提高搜索的效率,但是对整个搜索空间而言,可能得不到全局最优解。(2)最好优先搜索法(有序搜索法)该算法的估价函数采用f(n)=g(n)+h(n),在搜索过程中算法使用OPEN表和CLOSE表来记录节点信息:OPEN表中保留所有已生成而未考察的节点;CLOSE表中保留所有已访问过的节点。算法在每一次搜索过程中都会对OPEN表中的节点按照每个节点的f值进行排序,选择f值最小节点进行扩展。算法的描述如下:①把起始节点S放到OPEN表中,计算f(S),并把其值与节点S联系起来。②若OPEN是个空表,则算法失败退出,无解。③从OPEN表中选择一个f值最小的节点i。结果有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i。④把节点i从OPEN表中移出,并把它放入到CLOSED的扩展节点表中。⑤若节点i是个目标节点,则成功退出,求得一个解。⑥扩展i,生成其全部后继节点。对i的每个后继节点j:计算f(j)。如果j既不在OPEN表中,也不在CLOSED表中,则用估价函数f将其添加到OPEN表。从j加一指向其父辈节点i的指针,以便一旦找到目标节点时记住一个解答路径。如果j已则OPEN表中或CLOSED表中,则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f的值。若新的f值较小,则以此值取代旧值。从j指向i,而不是指向它的父辈节点。若节点j在CLOSED表中,则把它移回OPEN表。⑦转向②。四、实验内容:问题描述:用启发式搜索方法求解下列九宫问题1238476528316475五、问题(1)状态表示的数据结构我们将一个状态的9个格子按照从上到下,从左到右的顺序进行编号,用一个长度为9的字符串表示九宫格问题的一个状态,第i个位置表示第i个格子,该位置的内容表示格子当中的数字,用0表示空格。这样,图1所示问题的初始状态可以表示成“856204137”;目标状态可以表示成“123456780”。(2)状态扩展规则的表示我们以空格为参照点,定义了四种操作:空格上移、空格下移、空格左移和空格左移。基于前面介绍的状态表示,假设空格(0)是状态字符串中的第i个字符,四个操作的前提条件和具体操作如表1所示。操作名称前提条件具体操作空格上移空格不在第一行,即i>3将状