《搜索策略实验》由会员分享，可在线阅读，更多相关《搜索策略实验（14页珍藏版）》请在金锄头文库上搜索。
1、实验一：搜索策略实验一、实验目的1、熟悉和掌握启发式搜索的定义、估价函数和算法过程。2、利用A*算法求解N数码难题，理解求解流程和搜索顺序。二、实验内容以八数码为例实现A或A*算法。1、分析算法中的OPEN表CLOSE表的生成过程。2、分析估价函数对搜索算法的影响。3、分析启发式搜索算法的特点。启发式函数选取为：f*(n)=g*(n)+h*(n)其中：g*(n)是搜索树中节点n的深度；h*(n)用来计算对应于节点n的数据中错放的棋子个数。三、实验设计与结果八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树 式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就
2、是无“向导”的搜索，启发式搜索就是有“向导”的搜索。由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的 路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减 少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距 离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息 来扩展节点的选择，减少搜索范围，提高搜索速度。由此解决八数码问题就是在初始状态和目标状态两个状态之间寻找一系列 可过渡状态。利用A*算法实现寻找中间状态，从而得到目标状态。根据启发式搜索算法A*算法的具体步骤，结合八数码问题的要求，从而得 出相应的流程图为：其中：
3、OPEN 表：算法已搜索但尚未扩展的节点集合。CLOSED 表：算法已扩展的节点集合。实验输出结果：运行程序，输入起始棋局与目标棋局: * B H-M 卩 * 丁 - - ” -请输人初始状态J呷数字胡代恚空格:2 8 310 4? 6 5请输入目标状态数字前代義空榕:12 38 0 47 6 5结果输出为：四、程序1、设定启发式函数：八数码问题的目标是要搜索到目标节点，所以为了尽快的向目标节点进行靠 近，可以把启发式函数设定为当前节点与目标节点中状态的差异，即与目标节点 中数码的位置不同的个数作为启发函数的返回值，然后根据启发函数值找出启发 值最小的状态节点进行扩展。2、OPEN 表和 CL
4、OSE 表的生成过程：OPEN 表是用来存放经过扩展得到的待考察的状态节点， CLOSE 表是用来存 放考察过的状态节点，并且标记上当前节点的编号和父节点的编号，然后可以根 据编号便可以形成一个搜索树，即可以找到一个解路径。其中状态节点的结构体 如下所示：struct nodeint a33;/存放矩阵int father; int gone; int fn;int x,y;int deep;/父节点的位置/是否遍历过,1 为是,0 为否/评价函数的值/空格的坐标/节点深度/清空 store/建立 open 表把初始状态在store中的位置数压入open表; 从而可以定义 OPEN 表和 CL
5、OSE 表如下 store.clear();vector open; open.push_back(1);/当 open 表不为空时,开始寻找路径中 while(!open.empty() if(check(top) break;min=top;3、计算启发函数值函数：int get_fn(int num)int fn_temp=0;bool test=true;for(int i=0;i3;i+)/返回storenum的评价函数值/评价函数值int i_min=0;/当找到一个值后,计算这个值位置与目标位置的距离差,test置为false后继续寻找下一个值for(int j=0;j3;j+)
6、test=true;for(int k=0;k3;k+)for(int l=0;l3;l+)if(storenum.x!=i|storenum.y!=j)&storenum.aij=store0.akl) /寻值时排除空格位 fn_temp=fn_temp+abs(i-k)+abs(j-l);test=false;if(test=false) break;if(test=false) break;fn_temp=fn_temp+storenum.deep;/加上节点深度return fn_temp; 4、判断新扩展节点是否是已经扩展过的的节点函数：bool search(int num)判断s
7、torenum节点是否已经扩展过，没有扩展返回 trueint pre=storenum.father;/pre 扌旨向 storenum的父节点位置bool test=true;while(!pre)循环直到pre为0,既初始节点for(int i=0;i3;i+)for (int j=0;j3;j+)if(storepre.aij!=storenum.aij)test=false;break;if(test=false) break;if(test=true) return false;pre=storepre.father;/pre 继续指向 storepre父节点位置return tr
8、ue;5、在open表中找出启发值最小的节点(待扩展)函数：open.push_back(1);/把初始状态在 store 中的位置数压入 open 表中while(!open.empty()/当 open 表不为空时,开始寻找路径if(check(top) break;min=top;int i_min=0;for(i=0;iopen.size();i+)/遍历 open 表中元素,找出store 中 fn 值最小的节点if(storeopeni.fn=storemin.fn&storeopeni.gone=0)min=openi; i_min=i;storemin.gone=1;open.
9、erase(open.begin()+i_min); /把最小节点标记遍历过, 并从 open 表中删除五、实验结论1、估价函数的值对搜索算法速度的影响 估价函数的任务就是估计待搜索结点的重要程度，给它们排定次序。评价函 数可以是任意一种函数，如定义它是结点x处于最佳路径上的概率，或是x结点和目标结点之间的距离，或是X格局的得分等等。一般来说，评价一个结点的价 值，必须综合考虑两方面的因素：已付出的代价和将要付出的代价。在此，我们 把评价函数f(n)定义为从初始结点经过n结点到达目标结点的最小代价路径的代 价估计值。A*算法成功与否的关键在于估价函数的正确选择，从理论上说，一个完全正 确的估价
10、函数是可以非常迅速地得到问题的正确解答，但一般完全正确的估价函 数是得不到的，因而A*算法不能保证它每次都得到正确解答。一个不理想的估 价函数可能会使它工作得很慢，甚至会给出错误的解答。如果对其估价函数中的h*(n)部分即启发性函数，加以适当的单调性限制条 件，就可以使它对所扩展的一系列节点的估价函数值单调递增(或非递减)，从 而减少对OPEN表或CLOSED表的检查和调整，提高搜索效率。为了提高解答的正确性，我们还可以适当地降低估价函数的值，从而使之进 行更多的搜索，但这是以降低它的速度为代价的，因而我们可以根据实际对解答 的速度和正确性的要求而设计出不同的方案，使之更具弹性。2、启发式搜索
11、的特点对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方 法，人们常常称之为启发式算法(Heuristic Algorithm)。现在的启发式算法也不 是全部来自自然的规律，也有来自人类积累的工作经验。启发式算法有不同的定义：一种定义为，一个基于直观或经验的构造的算法， 对优化问题的实例能给出可接受的计算成本(计算时间、占用空间等)内，给出 一个近似最优解，该近似解于真实最优解的偏离程度不一定可以事先预计；另一 种是，启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好 的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所 得解同最优解的近似程度。
12、启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的 解。其具有的特点是：从随机的可行初始解出发，才用迭代改进的策略，去逼近 问题的最优解。附：源程序/存放矩阵/父节点的位置 /是否遍历过,1 为是,0 为否/评价函数的值/空格的坐标/节点深度/存放路径节点#include #include #include using namespace std; struct nodeint a33;int father; int gone; int fn; int x,y; int deep;vector store;int mx4=-1,0,1,0;int my4=0,-1,0,1;in
13、t top;bool check(int num)节点储存在store0中/上下左右移动数组/当前节点在store中的位置判断storenum节点与目标节点是否相同，目标for(int i=0;i3;i+)for(int j=0;j3;j+)if(storenum.aij!=store0.aij) return false;bool扩展返回 truesearch(int num)/判断storenum节点是否已经扩展过，没有return true;int pre=storenum.father;/pre 扌旨向 storenum的父节点位置bool test=true;while(!pre)循
14、环直到pre为0,既初始节点for(int i=0;i3;i+)for (int j=0;j3;j+)if(storepre.aij!=storenum.aij) if(test=false) break;if(test=true) return false; pre=storepre.father;return true;void print(int num)vector temp;int pre=storenum.father; temp.push_back(num);while(pre!=0) temp.push_back(pre); pre=storepre.father;coutendl;test=false;break;/pre继续指向storepre父节点位置/打印路径,store num为目标节点/存放路径/从目标节点回溯到初始节点
