内容发布更新时间 : 2024/5/2 23:16:43星期一 下面是文章的全部内容请认真阅读。
实验一 启发式搜索算法
学号：2220103430 班级：计科二班 姓名：刘俊峰
一、实验内容：
使用启发式搜索算法求解8数码问题。
1、编制程序实现求解8数码问题A?算法，采用估价函数
??w?n?f?n??d?n???， pn????其中：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)，以便找到当前节点空格所在位置以利于接下来的程序执行。返回值为空格所在的行和列。
4）int Wrong(LNode *Node)和int pick(LNode *Node)： 分别为函数?(n)和p(n)。
5）LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose)
树形方式扩展节点。Node为要扩展的当前节点，depth为当前深度，zero存放该节点空格位置信息，moveflag即扩展节点的移动方式，Choose为选择函数?(n)还是p(n)。
6）void InitList(LNode* &Open,LNode* &Close)和int ListInsert(List &L,LNode* NewNode)
分别为表OPEN、CLOSE的创建和表的插入操作。 7）LNode* Getminf(List &L)
主要是实现从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同，当其中 有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i。
五、实验源代码
#include
#include
int goal[N][N]={1,2,3,8,0,4,7,6,5}; int zero[2],NodeQTY=0;
int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列 typedef int Piece;
struct Chessboard{//棋盘信息