何昭霞 状态空间搜索 启发式搜索

1、重庆交通大学计算机与信息学院验证性实验报告班 级： 软件开发 专业 2013 级 1 班 学 号： 631306050105 姓 名： 何昭霞 实验项目名称： 状态空间搜索 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼） 指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 10 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的 1. 理解和掌握状态空间搜索的策略。 2.熟悉人工智能系统中的问题求解过程； 3.熟悉状态空间的盲目搜索和启发式搜索算法的应用； 4.熟悉对八数码问题的建模、求解及编程语言的应用。二、实验内容及要求

2、（一）实验内容在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。 （二）实验要求 用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、实验设备及软件 PC机一台、Visual Studio 2012编程软件四、设计方案 题目 状态空间搜索 8数码问题 设计的主要思路考虑广度优先算法：(1) 状态空间盲目搜索宽度优先搜索其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察

3、它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。(2) 宽度优先算法如下首先把初始结点S0放入OPEN表中，然后若OPEN表为空，则搜索失败，问题无解，接着取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n，若目标结点Sg=N，则搜索成功，问题有解。若N无子结点，则重复取OPEN表中最前面的结点N放在CLOSE表中。扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，然后重复取OPEN表中最前面的结点N放在CLOSE表中。

4、根据算法的中心思想进行程序设计，其流程图如下图所示。 主要功能使用C语言相关知识，将3*3的九宫格调整为某种有序的形式。五、主要代码#include<stdlib.h> #include<memory.h> struct node int x,y; int cntdif;int step; int f9; int xy33; queue10000; int map33; int dir42=-1,0,1,0,0,1,0,-1; int open10000; int zz9; int f1,f2; struct node sour,dest; queuetail.fi*3

5、+j=queuetail.xyij=ffi*3+j; queuetail.step=HH.step+1; queuetail.x=sx; queuetail.y=sy; tdif=count(queuetail.f,zz); opentail=visit(queuetail.f); print(queuetail.xy); if(match(queuetail) printf("step(s):%d！n",queuetail.step); return; qsort(queue+head,tail-head+1,sizeof(queue0),comp

6、);/排序，每次选择cntdif数目最小的扩展 int main() int i,j,a9,b9; printf("Please input the nitial status,input 0 to the vacant position :n"); for(i=0;i<3;i+) for(j=0;j<3;j+) scanf("%d",&mapij); sour.xyij=mapij; sour.fi*3+j=mapij; ai*3+j=mapij; if(mapij=0) sour.x=i; sour.y=j; sour.step=

7、0; tdif=0; printf("Please input the final status:n"); for(i=0;i<3;i+) for(j=0;j<3;j+) scanf("%d",&mapij); dest.xyij=mapij; dest.fi*3+j=mapij; bi*3+j=mapij; zzi*3+j=mapij; printf("n"); if(judge(a)+judge(b)&1) printf("The final status cannot be reached

8、."); return 0; printf("The searching process is:n"); bfs(); return 0; 六、测试结果及说明 七、实验体会 人工智能搜索可分为盲目搜索和启发式搜索。盲目搜索算法有宽度优先算法、深度优先算法（有界深度优先算法），启发式搜索算法有A算法、A*算法。我在本实验中，采用的是宽度优先（广度优先）算法，这种算法是按预定的控制策略进行，在搜素的过程中所获得的信息不用来改进控制策略。由于搜索总是按预定的路线进行，没有考虑问题本身的特性，这种缺乏问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索路径。通过这

9、次实验更加熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。因此，我对人工智能搜索有了更深的认识。 重庆交通大学计算机与信息学院验证性实验报告班 级： 软件开发 专业 2013 级 1 班 学 号： 631306050105 姓 名： 何昭霞 实验项目名称： 启发式搜索 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼） 指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 10 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的 理解和掌握A*算法。二、实验内容及要求（一

10、）实验内容在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。 （二）实验要求 用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、实验设备及软件 PC机一台、Visual Studio 2012编程软件四、设计方案 题目 启发式搜索A*算法 设计的主要思路根据任务要求，该实验我采用A*搜索算法。对于八数码问题的解决,首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵.由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通

11、过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。如果初始状态可以到达目标状态,常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。在这里就要用到启发式搜索启发中的估价是用估价函数表示的,如:f(n)=g(n)+h(n)其中f(n)是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。在此八数码问题中,显然g(n)就是从初始状态变换到当前状态所移动的步数

12、,估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数,即错位数。 1.状态的表示 在A*算法中，需要用到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，与数据结构中的链表相似，必须要有能指向下一个扩展节点的指针，以完成对open表中元素的索引。这里表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。其中DATA中包括的内容采用一个的二维数组s33表示当前状态的具体信息。而为了保证在搜索到目标状态后能够顺利复现寻优路径，当前状态的DATA中还应该包括一个指向其父节点的指针f

13、ather，这样，才能在达到目标状态后，通过指针father逐层回溯到初始状态，即复现寻优路径。2.启发函数的设计 根据A*算法的定义，启发函数应满足：h(n)<=h*(n)其中h*(n)表示从当前节点n到目标节点s_g的最优路径的实际代价。3. 规则库设计 0在某一位置时，能选择向左、向右、向上、向下移动中的哪几种策略进行移动，主要是由当前0所处位置（更具体地说是当前位置的行列号）和其祖父节点（为提高搜索效率，新扩展的节点应当至少不为其祖父节点）所决定的。当然，按照A*算法的思想，每扩展出一个新节点，都要判断其是否为有效子节点，不为有效子节点的不能加入到open表中。 主要功能使用C+

14、语言的相关知识，利用策略函数判断搜索，并使用A*算法减少搜索目标。五、主要代码#include"iostream"#include"stdlib.h"#include"conio.h"#define size 3using namespace std;/定义二维数组来存储数据表示某一个特定状态typedef int statussizesize;struct SpringLink;/定义状态图中的结点数据结构typedef struct Nodestatus data;/结点所存储的状态struct Node*parent;/指向结点

15、的父亲结点struct SpringLink*child;/指向结点的后继结点struct Node*next;/指向open或者closed表中的后一个结点int fvalue;/结点的总的路径int gvalue;/结点的实际路径int hvalue;/结点的到达目标的苦难程度NNode,*PNode;/定义存储指向结点后继结点的指针的地址typedef struct SpringLinkstruct Node*pointData;/指向结点的指针struct SpringLink*next;/指向兄第结点SPLink,*PSPLink;PNode open;PNode closed;/开

16、始状态与目标状态status startt=0,1,2,3,4,5,6,7,8;status target=1,4,2,3,5,8,6,7,0;/初始化一个空链表void initLink(PNode&Head)Head = (PNode)malloc(sizeof(NNode); Head->next = NULL; /判断链表是否为空 bool isEmpty(PNode Head) if(Head->next = NULL) return true; else return false; /从链表中拿出一个数据 void popNode(PNode &Head

17、 , PNode &FNode)if(isEmpty(Head) FNode = NULL; return; FNode = Head->next; Head->next = Head->next->next; FNode->next = NULL; /向结点的最终后继结点链表中添加新的子结点void addSpringNode(PNode &Head , PNode newData) PSPLink newNode = (PSPLink)malloc(sizeof(SPLink); newNode->pointData = newData;

18、 newNode->next = Head->child; Head->child = newNode; /释放状态图中存放结点后继结点地址的空间 void freeSpringLink(PSPLink &Head) PSPLink tmm; while(Head != NULL) tmm = Head; Head = Head->next; free(tmm); /释放open表与closed中的资源 void freeLink(PNode &Head) PNode tmn; tmn = Head; Head = Head->next; free

19、(tmn); while(Head != NULL) /首先释放存放结点后继结点地址的空间freeSpringLink(Head->child); tmn = Head; computeAllValue(udNewNode , theNode); /将本结点加入后继结点链表addNode(spring , udNewNode); /空的格子下边的格子向上移动if(row != 2) PNode duNewNode = (PNode)malloc(sizeof(NNode); statusAEB(duNewNode , theNode); changeAB(duNewNode->da

20、tarowcol , duNewNode->datarow + 1col); if(hasAnceSameStatus(duNewNode , theNode->parent) free(duNewNode);/与父辈相同，丢弃本结点 else duNewNode->parent = theNode; duNewNode->child = NULL; duNewNode->next = NULL; computeAllValue(duNewNode , theNode); /将本结点加入后继结点链表addNode(spring , duNewNode); /输出给

21、定结点的状态void outputStatus(PNode stat) for(int i = 0 i < 3 i+) for(int j = 0 j < 3 j+) cout << stat->dataij << " " cout << endl; /输出最佳的路径void outputBestRoad(PNode goal) int deepnum = goal->gvalue; if(goal->parent != NULL) outputBestRoad(goal->parent); cout

22、<< "第" << deepnum- << "层的状态：" << endl; outputStatus(goal); void AStar() PNode tmpNode;/指向从open表中拿出并放到closed表中的结点的指针PNode spring;/tmpNode的后继结点链PNode tmpLNode;/tmpNode的某一个后继结点PNode tmpChartNode; PNode thePreNode;/指向将要从closed表中移到open表中的结点的前一个结点指针bool getGoal

23、= false;/标识是否达到目标状态long numcount = 1;/记录从open表中拿出结点的序号initial();/对函数进行初始化initLink(spring);/对后继链表的初始化tmpChartNode = NULL; cout << "从open表中拿出的结点的状态及相应的值" << endl; while(!isEmpty(open) /从open表中拿出f值最小的元素,并将拿出的元素放入closed表中popNode(open , tmpNode); addNode(closed , tmpNode); cout <

24、< "第" << numcount+ << "个状态是：" << endl; outputStatus(tmpNode); cout << "其f值为：" << tmpNode->fvalue << endl; cout << "其g值为：" << tmpNode->gvalue << endl; cout << "其h值为：" << tmpNod

25、e->hvalue << endl; /如果拿出的元素是目标状则跳出循环if(computeHValue(tmpNode) = 0) getGoal = true; break; /产生当前检测结点的后继(与祖先不同)结点列表，产生的后继结点的parent属性指向当前检测的结点SpringLink(tmpNode , spring); /遍历检测结点的后继结点链表while(!isEmpty(spring) popNode(spring , tmpLNode); /状态在open表中已经存在，thePreNode参数在这里并不起作用if(inLink(tmpLNode , o

26、pen , tmpChartNode , thePreNode) addSpringNode(tmpNode , tmpChartNode); if(tmpLNode->gvalue < tmpChartNode->gvalue) tmpChartNode->parent = tmpLNode->parent; tmpChartNode->gvalue = tmpLNode->gvalue; tmpChartNode->fvalue = tmpLNode->fvalue; free(tmpLNode); /状态在closed表中已经存在else if(inLink(tmpLNode , closed , tmpChartNode , thePreNode) addSpringNode(tmpNode , tmpChartNode); if(tmpLNode->gvalue < tmpChartNode->gvalue) PNode commu; tmpChartNode->parent = tmpLNode->parent; tmpChartNode->gvalue = tmpLNode->gval