资源描述：
《人工智能之迷宫.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、问题描述迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法。图1.1迷宫示意图二、设计原理图1.1为一简单迷宫示意图的平面坐标表示。以平面坐标图来表示迷宫的通路时，问题的状态以所处的坐标位置来表示，即综合数据库定义为｛(x,y)
2、1≤x,y≤4｝，则迷宫问题归结为求解从(1,1)到(4,4)的最短路径。迷宫走法规定为向东、南、西、北前进一步，由此可得规则集简化形式如下。右移R1：if(x,y)then(x+1,y)如果当前在(x,y)点，则向右移动一步下移R2：if(x,y)then(x,y-1)如果当前在(x,y)点，则向下
3、移动一步左移R1:if(x,y)then(x-1,y)如果当前在(x,y)点，则向左移动一步上移R2：if(x,y)then(x,y+1)如果当前在(x,y)点，则向上移动一步给出其状态空间如图2.1所示为求得最佳路径，可使用A*算法。A*算法f函数定义f(n)＝g(n)＋h(n)设：每一步的耗散值为1（单位耗散值）定义：g(n)＝d(n)从初始节点s到当前节点n的搜索深度h(n)＝
4、Xg－Xn
5、＋
6、Yg－Yn
7、当前节点n与目标节点间的坐标距离其中：(Xg,Yg)目标节点g坐标(Xn,Yn)当前节点n坐标显然满足：h(n)≤h*(n)OPE
8、N表节点排序⑴按照f值升序排列⑵如果f值相同，则深度优先A*算法的搜索过程如下：1、OPEN＝(s)，f(s)=g(s)+h(s)2、LOOP：ifOPEN＝()thenEXIT(FAIL)3、n←FIRST(OPEN)4、ifGOAL(n)THENEXIT(SUCCESS)5、REMOVE(n,OPEN)，ADD(n,CLOSED)6、{mi﹜←EXPAND(n)①计算f(n,mi)=g(n,mi)+h(mi)，(自s过n，mi到目标节点的耗散值)②ADD(mj,OPEN)，标记mj到n的指针(mj不在OPEN和CLOSED中)③iff(
9、n,mk)＜f(mk)thenf(mk)←f(n,mk)，标记mk到n的指针(mk在OPEN中)④iff(n,ml)＜f(ml)thenf(ml)←f(n,ml)，标记ml到n的指针(ml在CLOSED中)ADD(ml,OPEN)，把ml放回到OPEN中7、OPEN中的节点按照f值升序排列8、GOLOOPA*算法的搜索图示如图2.2所示。则其搜索结果如图2.3所示。图2.3迷宫搜索结果示意图一、详细设计（1）数据结构设计①为了在程序中表示迷宫图，定义了一个6*6的二维整型数组intMaze[7][7]={{3,1,3,1,3,0,3},{0
10、,4,1,4,1,4,1},{3,1,3,0,3,1,3},{1,4,1,4,1,4,1},{3,0,3,1,3,0,3},{1,4,1,4,1,4,1},{3,0,3,1,3,1,3}};其中数字3代表坐标点，1代表两个坐标点之间存在路径，0代表两个坐标点之间不存在路径，数字4没有意义。从这个二维整型数组抽象出来的迷宫如下所示：②每个坐标点的数据结构如下:structData{intx;inty;intg;intf;structData*parent;};其中x代表数组的第几行对应实际坐标的y值，y代表数组的第几列对应实际坐标的x值，g代
11、表从入口到该坐标点的耗散值，f代表代表评价函数值，parent代表路径上的该坐标点的前一个坐标点。③程序中对应入口坐标为（6，0）也就是实际中的入口（1,1），实际中每走一步对应程序中是x+2或x-2或y+2或y-2。程序中对应的出口坐标为（0,6）实际对应着出口（4,4）。④实际中的h函数对应程序中的h(n)＝
12、x－0
13、/2＋
14、y－6
15、/2。⑤因为实际坐标与程序中坐标不对应，所以需要一个转换公式，如下:实际坐标的x值等于程序中坐标点的y值除以2再加1实际坐标的y值等于5减去程序中坐标点的x值除以2再减1⑥判断两个坐标点a,b之间是否存在路
16、径：p=(a->x+b->x)/2;q=(a->y+b->y)/2;如果Maze[p][q]==1,则说明a，b之间存在路径，Maze[p][q]==0，则说明不存在路径。为了将搜索结果图形输出，则又设置了Maze[p][q]==5，代表“←”,Maze[p][q]==6，代表“→”，Maze[p][q]==7，代表“↑”，Maze[p][q]==8，代表“↓”。⑦为了满足open表中节点如果f值相同，则深度优先，使用一个栈来表示open表，closed表也是用一个栈来表示。（2）函数说明boolbound(Data*a)函数功能:判断一个
17、坐标点是否越过边界，返回值bool值inth(Data*a)函数功能:h函数Data*Nopen(Data*a)函数功能:在open表中搜索结点a.若找到则返回结点a的地址，否则
