文档介绍：实验一启发式搜索算法学号: 2220103430 班级:计科二班姓名:刘俊峰一、实验内容: 使用启发式搜索算法求解 8 数码问题。 1、编制程序实现求解 8 数码问题 A ?算法,采用估价函数???????? w n f n d n p n ??? ????, 其中:?? d n 是搜索树中结点 n 的深度;?? w n 为结点 n 的数据库中错放的棋子个数;?? p n 为结点 n 的数据库中每个棋子与其目标位置之间的距离总和。 2、分析上述⑴中两种估价函数求解 8 数码问题的效率差别,给出一个是?? p n 的上界的?? h n 的定义,并测试使用该估价函数是否使算法失去可采纳性。二、实验目的: 熟练掌握启发式搜索 A ?算法及其可采纳性。三、实验原理: (一)问题描述在一个 3*3 的方棋盘上放置着 1,2,3,4,5,6,7,8 八个数码, 每个数码占一格, 且有一个空格。这些数码可以在棋盘上移动, 其移动规则是: 与空格相邻的数码方格可以移入空格。现在的问题是: 对于指定的初始棋局和目标棋局, 给出数码的移动序列。该问题称八数码难题或者重排九宫问题。(二)问题分析八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式, 即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索, 启发式搜索就是有“向导”的搜索。启发式搜索: 由于时间和空间资源的限制,穷举法只能解决一些状态空间很小的简单问题, 而对于那些大状态空间的问题,穷举法就不能胜任,往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。由八数码问题的部分状态图可以看出, 从初始节点开始, 在通向目标节点的路径上, 各节点的数码格局同目标节点相比较, 其数码不同的位置个数在逐渐减少, 最后为零。所以, 这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息, 利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择, 减少搜索范围, 提高搜索速度。启发函数设定。对于八数码问题, 可以利用棋局差距作为一个度量。搜索过程中, 差距会逐渐减少,最终为零,为零即搜索完成,得到目标棋局。四、实验程序及其说明: 1) int goal[N][N] , struct Chessboard : 试验中我定义 goal 数组为目标状态——{1,2,3,8,0,4,7,6,5} 。结构体 Chessboard 记录棋盘信息, 其中变量 pos 数组坐标记录每个数码 a 的位置, 其值为数码 a。d 表示该棋盘的深度, f 为启发函数值, move 为父节点移动到该节点的方式, 以便在输出时告诉用户该如何移动棋子知道目标状态。 2) struct LNode : 定义节点 LNode 结构体, 存放该节点状态时的棋盘信息 board , 和指向父节点、下一节点的指针(*parent,*next) ,以及标记量 flag ——值为 true 时表示该节点是最佳路径上的节点。 3) int* Findzero(LNode* &Node) : 为方便找到空格, 我设计了找到该函数 Findzero(*&Node) , 以便找到当前节点空格所在位置以利于接下来的程序执行