资源描述：
《ai实验指导书-走迷宫》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解走迷宫问题，理解求解流程和搜索顺序。二、实验原理：A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达冃标节点的代价。三、实验环境1.VC6.O/C++/C2.走迷宫程序流程图四、实验内容1以走迷宫问题为例实际求解A*算法。2画岀A*算法求解框图。3
2、分析估价函数对搜索算法的影响。4分析A*算法的特点。五、实验步骤1.分析问题，定义估价函数。2.编写程序，实验算法。3.改变估价函数，比较不同估价函数对算法的影响。六、实验报告要求1A*算法流程图和算法框图。2试分析估价函数的值对搜索算法速度的影响。3根据A*算法分析启发式搜索的特点。七、参考程序说明：该程序只作为参考程序，作为走迷宫问题的算法，从吋间复杂度和空间复杂度考虑，它不是最优算法，但它利用了启发信息,能找到最短路径。同学们可以从时间复杂度上考虑写出更优的算法。函数调用说明：1、voidAddClosed(structGa
3、ther*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
4、是不是目标结点。是返回TRUE,否返回FALSE;5、boolIsOpenEmpty(void)返回值为bool型。OPEN集合为空，返回TRUE,否则返回FALSE;6、voidRemove(structGather*des)des为structGather*类型的结点；该函数的功能是将des从OPEN集合中删除。7、structGather*First(void)返回structGather*类型的结点；该函数的功能是取OPEN集合中存储的第一个有效结点。创建OPEN集合时，头结点未存有效结点。8、intInOPENorCLO
5、SED(structPointR)返回值为int型,行参为structPoint类型。用法InOPENorCLOSED(P[i])该函数的功能是判断点R在OPEN集合，或者CLOSED集合，或者都不在在OPEN屮，返回0在CLOSED中，返回1都不在，返回29、voidExpand(structGather*curr)无返回值，行参为structPoint类型该函数的功能是扩展当前结点curr010、voidDrawMap(void)画个草图。#includeusingnamespacestd;constint
6、PointNum=16;//迷宫点的总数constintSideNum=18;〃迷宫边的总数structPoint{intx;/*横坐标*/inty；/*纵坐标intF;/*评价函数值*/intH;/*当前点到目标点的横截距与纵截距之和引intD;/*深度*/intindex;/*点的编号*/intpre;/*保存路径，作标志指针之用*/｝；structIndex{Iintfrom;/*边的起点*/intto;/*边的终点注：由于是无向图，from,既是起点又是终点。*/structGatherpnode;*next;struct
7、PointstructGather}；〃存储点的信息共PointNum个点structPointPfPointNum]={{1,1,0,0,0,0,・l},{120,0,0,1,・2},{l,3,0,0,0,2,・2},{l,4,0,0,0,3,・2},{2丄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,l,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丄0,
8、0,0,12,・2},{4,2,0,0,0,13,-2},{4,3,(),0,(),14,・2},{4,4,0,0,0,15,-2}}；〃存储边的信息共SideNum个边structIndexInfSideNum]={{0,1},{1,2},{2,
