《人工智能之迷宫互联网》由会员分享，可在线阅读，更多相关《人工智能之迷宫互联网（16页珍藏版）》请在金锄头文库上搜索。
1、一、 问题描述迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法。 图1.1 迷宫示意图二、 设计原理图1.1为一简单迷宫示意图的平面坐标表示 。以平面坐标图来表示迷宫的通路时，问题的状态以所处的坐标位置来表示，即综合数据库定义为(x, y) | 1x, 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)点，则向下移
2、动一步左移 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) | XgXn | | YgYn | 当前节点n与目标节点间的坐标距离其中：( Xg, Yg) 目标节点g坐标 ( Xn, Yn )当前节点n坐标显然满足： h(n) h*(n)
3、 OPEN表节点排序 按照f 值 升序排列 如果f 值相同，则深度优先A*算法的搜索过程如下：1、OPEN(s)， f(s)=g(s)+h(s)2、LOOP：if OPEN( ) then EXIT(FAIL)3、n FIRST(OPEN)4、if GOAL(n) THEN EXIT(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中) if f(n,mk) f(mk) the
4、n f(mk) f(n,mk)，标记mk到n的指针(mk在 OPEN中) if f(n,ml) f(ml) then f(ml) f(n,ml)，标记ml到n的指针(ml在 CLOSED中)ADD(ml,OPEN)，把ml放回到OPEN中7、OPEN中的节点按照f值升序排列8、GO LOOPA*算法的搜索图示如图2.2所示。则其搜索结果如图2.3所示。 图2.3 迷宫搜索结果示意图三、 详细设计（1）数据结构设计为了在程序中表示迷宫图，定义了一个6*6的二维整型数组int Maze77=3,1,3,1,3,0,3, 0,4,1,4,1,4,1, 3,1,3,0,3,1,3, 1,4,1,4,1
5、,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没有意义。从这个二维整型数组抽象出来的迷宫如下所示： 每个坐标点的数据结构如下: struct Data int x; int y;int g; int f; struct Data *parent;其中x代表数组的第几行对应实际坐标的y值，y代表数组的第几列对应实际坐标的x值，g代表从入口到该坐标点的耗散值，f代表代表评价函数值，parent代表路径上的该坐标点的前一个坐标点。程序中对应入口坐标为（6，0
6、）也就是实际中的入口（1,1），实际中每走一步对应程序中是x+2或x-2或y+2或y-2。程序中对应的出口坐标为（0,6）实际对应着出口（4,4）。 实际中的h函数对应程序中的h(n) |x0|/2| y6 |/2。因为实际坐标与程序中坐标不对应，所以需要一个转换公式，如下:实际坐标的x值等于程序中坐标点的y值除以2再加1实际坐标的y值等于5减去程序中坐标点的x值除以2再减1判断两个坐标点a,b之间是否存在路径：p=(a-x+b-x)/2; q=(a-y+b-y)/2;如果Mazepq=1,则说明a，b之间存在路径，Mazepq=0，则说明不存在路径。为了将搜索结果图形输出，则又设置了Maze
7、pq=5，代表“”, Mazepq=6，代表“”，Mazepq=7，代表“”，Mazepq=8，代表“”。为了满足open表中节点如果f 值相同，则深度优先，使用一个栈来表示open表，closed表也是用一个栈来表示。（2）函数说明bool bound(Data *a)函数功能:判断一个坐标点是否越过边界，返回值bool值int h(Data *a)函数功能:h函数Data* Nopen(Data *a)函数功能:在open表中搜索结点a.若找到则返回结点a的地址，否则返回0Data* Nclosed(Data *a)函数功能: 在closed表中搜索结点a.若找到则返回结点a的地址，否则返
8、回0void sort()函数功能:对open表中节点按照f值升序排列void Expand(Data *a)函数功能: 扩展当前结点avoid printmaze()函数功能:输出迷宫void printpath(Data *a)函数功能:输出搜索结果int A()函数功能: A*算法void main()函数功能:主函数（3）详细程序设计#include#includeusing namespace std;int Maze77=3,1,3,1,3,0,3, 0,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,
9、4,1,4,1, 3,0,3,1,3,1,3;/3代表节点，1代表两个节点之间有线，0代表两个节点之间没有线，4无意义struct Dataint x;int y;int g;int f;struct Data *parent;/坐标点结构体stack open; /open表stack closed; /close表bool bound(Data *a) /边界函数 return (a-xx=0)&(a-yy=0); int h(Data *a) /h函数 return abs(a-x-0)/2)+abs(a-y-6)/2); Data* Nopen(Data *a)/在open表搜索a坐标
10、点 Data *b,*d;stack c;while(!open.empty() b=open.top();if(b-x=a-x&b-y=a-y) while(!c.empty() d=c.top(); c.pop(); open.push(d);return b;open.pop();c.push(b);while(!c.empty()d=c.top();c.pop();open.push(d);return 0;Data* Nclosed(Data *a) 在closed表搜索a坐标点 Data *b,*d;stack c;while(!closed.empty() b=closed.to
11、p();if(b-x=a-x&b-y=a-y) while(!c.empty()d=c.top();c.pop();closed.push(d);return b;closed.pop();c.push(b);while(!c.empty() d=c.top();c.pop();closed.push(d);return 0;void sort() 对open表中坐标点排序Data *p,*q,*r;stack c;int b=open.size();for(int i=0;ib;i+) p=open.top();open.pop();for(int j=i+1;jff)r=p;p=q;q=r
12、; open.push(q); c.push(p);while(!c.empty() q=c.top();c.pop();open.push(q); void Expand(Data *a)/扩展a坐标点 int p,q;Data *d;struct Data *b4;for(int i=0;ix=a-x+2;b0-y=a-y;b1-x=a-x;b1-y=a-y-2;b2-x=a-x-2;b2-y=a-y;b3-x=a-x;b3-y=a-y+2;for(i=0;ix+a-x)/2;q=(bi-y+a-y)/2;if(Mazepq=1) if(Nopen(bi)=0&Nclosed(bi)=0) bi-g=a-g+1;bi-f=bi-g+h(bi);bi-parent=a;open.push(bi);else if(Nopen(bi) d=Nopen(bi);if(a-g+1g) d-g=a-g+1;d-f=bi-g+h(bi);d-parent=a;else if(
