AI实验指导书-走迷宫

实验一走迷宫问题一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解走迷宫问题，理解求解流程和搜索顺序。二、实验原理：A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。三、实验环境1.VC6.0/C++/C2.走迷宫程序流程图四、实验内容1以走迷宫问题为例实际求解A*算法。2画出A*算法求解框图。3分析估价函数对搜索算法的影响。4分析A*算法的特点。五、实验步骤1.分析问题，定义估价函数。2.编写程序，实验算法。3.改变估价函数，比较不同估价函数对算法的影响。六、实验报告要求1

A*算法流程图和算法框图。2

试分析估价函数的值对搜索算法速度的影响。3

根据A*算法分析启发式搜索的特点。七、参考程序说明：该程序只作为参考程序，作为走迷宫问题的算法，从时间复杂度和空间复杂度考虑，它不是最优算法，但它利用了启发信息，能找到最短路径。同学们可以从时间复杂度上考虑写出更优的算法。函数调用说明：

1、

voidAddClosed(structGather

*des)

des为structGather*类型的结点；

该函数的功能是将des结点加到CLOSED集合中，无返回值。

2、

voidPartInit_Point(void)

无行参，无返回值。

该函数的功能是初始化PointP[]中的部分成员。

3、

voidAddOpen(structPointdes)

行参为structPoint类型，可以直接将P[i]作行参。

该函数的功能是将点des加到OPEN集合中。

4、

boolGoal(structGather*n)

行参为structGather*类型,返回值为bool型。

该函数的功能是判断n是不是目标结点。是返回TRUE,否返回FALSE;

５、

boolIsOpenEmpty(void)

返回值为bool型。OPEN集合为空，返回TRUE,否则返回FALSE;

６、

voidRemove(structGather*des)

des为structGather*类型的结点；

该函数的功能是将des从OPEN集合中删除。

７、

structGather*First(void)

返回structGather*类型的结点；

该函数的功能是取OPEN集合中存储的第一个有效结点。创建OPEN集合时，头结点未存有效结点。

８、

intInOPENorCLOSED(structPointR)

返回值为int型，行参为structPoint类型。用法InOPENorCLOSED(P[i])

该函数的功能是判断点R在OPEN集合，或者CLOSED集合，或者都不在

在OPEN中，返回0

在CLOSED中，返回1

都不在，返回2

9、

voidExpand(structGather*curr)

无返回值，行参为structPoint类型

该函数的功能是扩展当前结点curr。

10、

voidDrawMap(void)

画个草图。#include<iostream>usingnamespacestd;constintPointNum=16;//迷宫点的总数constintSideNum=18;//迷宫边的总数structPoint{intx;/*横坐标*/inty;/*纵坐标*/intF;/*评价函数值*/intH;/*当前点到目标点的横截距与纵截距之和*/intD;/*深度*/intindex;/*点的编号*/intpre;/*保存路径，作标志指针之用*/};structIndex{intfrom;/*边的起点*/intto;/*边的终点注：由于是无向图，from，to既是起点又是终点。*/};structGather{structPointpnode;structGather*next;};//存储点的信息共PointNum个点structPointP[PointNum]={{1,1,0,0,0,0,-1},{1,2,0,0,0,1,-2},{1,3,0,0,0,2,-2},{1,4,0,0,0,3,-2},{2,1,0,0,0,4,-2},{2,2,0,0,0,5,-2},{2,3,0,0,0,6,-2},{2,4,0,0,0,7,-2},{3,1,0,0,0,8,-2},{3,2,0,0,0,9,-2},{3,3,0,0,0,10,-2},{3,4,0,0,0,11,-2},{4,1,0,0,0,12,-2},{4,2,0,0,0,13,-2},{4,3,0,0,0,14,-2},{4,4,0,0,0,15,-2}};//存储边的信息共SideNum个边structIndexIn[SideNum]={{0,1},{1,2},{2,6},{3,7},{4,5},{4,8},{5,6},{5,9},{6,7},{7,11},{8,9},{8,12},{9,10},{10,11},{10,14},{12,13},{13,14},{14,15}};//OPEN,CLOSED集合中头结点不存数据，且设OPEN,CLOSED为指针类型的常量//确保OPEN,CLOSED两全局指针不被意外修改。structGather*constOPEN=newstructGather;structGather*constCLOSED=newstructGather;//将结点加到CLOSED集合中voidAddClosed(structGather*des){des->next=CLOSED->next;CLOSED->next=des;}//部分初始化voidPartInit_Point(void){for(inti=0;i<PointNum;i++){P[i].H=(4-P[i].x)+(4-P[i].y);}P[0].D=0;P[0].F=P[0].H+P[0].D;OPEN->next=NULL;CLOSED->next=NULL;}//将点加到OPEN集合中，插入，确保OPEN集合中的点是按照F值由小到大排序的voidAddOpen(structPointdes){structGather*q=OPEN,*r=NULL,*temp=newstructGather;temp->pnode=des;while((q->next!=NULL)&&(q->next->pnode.F<des.F)){q=q->next;}r=q->next;temp->next=r;q->next=temp;}///////////////////////////////////////////////////////////////////////////判断是否到达终点,到达则返回TrueboolGoal(structGather*n){if(n->pnode.index==15)//该迷宫(课本)的目标结点编号是15[自定义]returntrue;elsereturnfalse;}//判断Open集合是不是为空，空则返回TrueboolIsOpenEmpty(void){if(OPEN->next==NULL)returntrue;elsereturnfalse;}//将des结点从OPEN集合中删除voidRemove(structGather*des){structGather*p=OPEN,*q=NULL;while((p->next!=NULL)&&(p->next->pnode.index!=des->pnode.index)){p=p->next;}if(p->next==NULL)cout<<"ErroroccurswhendeletenodefromOpen!"<<endl;else{q=p->next;p->next=q->next;}}//取OPEN集合中存的第一个结点[注意：OPEN头结点未存数据]structGather*First(void){returnOPEN->next;}//判断点R在OPEN,CLOSED集合中，还是都不在intInOPENorCLOSED(structPointR){for(structGather*p=OPEN;p->next!=NULL;p=p->next){if(p->next->pnode.index==R.index)return0;//在OPEN中}for(p=CLOSED;p->next!=NULL;p=p->next){if(p->next->pnode.index==R.index)return1;//在CLOSED中}return2;//都不在}//扩展结点遇到的三种情况处理voidProcess(structPoint*A,structGather*curr){(*A).D++;(*A).F=(*A).D+(*A).H;if(InOPENorCLOSED(*A)==2)//如果A不在OPEN,CLOSED集合中{AddOpen(*A);//将A加到OPEN集合中(*A).pre=curr->pnode.index;//标志指针（游标）}if(InOPENorCLOSED(*A)==0)//如果A在OPEN集合中{structGather*r=OPEN;while((r->next!=NULL)&&(r->next->pnode.index!=(*A).index)){r=r->next;}if((*A).F<r->next->pnode.F){r->next->pnode.F=(*A).F;//修改OPEN集合中结点A的F值(*A).pre=curr->pnode.index;//标志指针（游标）}}if(InOPENorCLOSED(*A)==1)//如果A在CLOSED集合中{structGather*r=CLOSED;while((r->next!=NULL)&&(r->next->pnode.index!=(*A).index)){r=r->next;}if((*A).F<r->next->pnode.F){(*A).pre=curr->pnode.index;//标志指针（游标）AddOpen(*A);//将A重新放到OPEN集合中}}}//扩展当前结点currvoidExpand(structGather*curr){for(inti=0;i<SideNum;i++){if(In[i].from==curr->pnode.index){intt=In[i].to;Process(&P[t],curr);}//由于是无向图，可以由点from扩展到点to;同样可以由点to扩展到点fromif(In[i].to==curr->pnode.index){intt=In[i].from;Process(&P[t],curr);}}//endfor}//画初始的迷宫图voidDrawMap(void){cout<<"Theprimarygraphis:"<<endl<<endl;cout<<"()_____()_____()()"<<endl<<"||"<<endl <<"||"<<endl<<"()_____()_____()_____()"<<endl<<"|||"<<endl <<"|||"<<endl<<"()_____()_____()_____()"<<endl <<"||"<<endl <<"|