人工智能之迷宫互联网

一、 问题描述迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法。 图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)点，则向下移动一步左移 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) 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) then 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,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）也就是实际中的入口（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，则说明不存在路径。为了将搜索结果图形输出，则又设置了Mazepq=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的地址，否则返回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,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坐标点 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.top();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; 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(Nclosed(bi) if(a-g+1g) bi-g=a-g+1;bi-f=bi-g+h(bi);bi-parent=a;open.push(bi); void printmaze() /输出迷宫 cout (4,4) endl;for(int i=0;i7;i+) if(i=6)cout入口;elsecout ;if(i%2=0) for(int j=0;j7;j+) if(Mazeij=3)cout;else if(Mazeij=1)cout;else if(Mazeij=5)cout;else if(Mazeij=6) cout;elsecout ;if(i=0)cout出口;coutendl;else for(int j=0;j7;j+) if(Mazeij=1)cout; else if(Mazeij=7) cout;else if(Mazeij=8) cout;elsecout ; coutendl; cout (1,1)endlendl;void printpath(Data *a)/输出搜索结果 int b,c;stack q;while(!a-parent=NULL) q.push(a);b=(a-parent-x+a-x)/2; c=(a-parent-y+a-y)/2;if(a-parent-x=a-x) if(a-parent-ya-y) Mazebc=5;else Mazebc=6;else if(a-parent-xa-x) Mazebc=7;elseMazebc=8;a=a-parent;q.push(a);while(!q.empty()cout(y/2+1,x/2+1) ; q.pop();coutendlendl;printmaze(); int A() /A*算法 Data s=6,0,0,0,NULL;Data *n=&s; open.push(n);while(1) if(open.empty() cout不存在路径!x=0&n-y=6) cout最短路径长度为:fendlendl; cout最短路径为:;printpath(n);return 1; else open.pop(); closed.push(n); Expand(n); /扩展n节点sort(); /open中节点按照f值升序排列 void main()/主函数 cout迷宫如下图:endl;printmaze();A();四、 设计结果及分析（1） 实验结果（2）实验分析从上面的图中可以看出程序运行结果与分析结果一致，程序运行正确。五、 实验心得与体会通过本次课程设计的训练，增加了我学习算法的兴趣，对A*算法有了更深刻的理解，虽然还不是很明白其中的具体内容，但已发现算法分析与程序设计的乐趣，而且还熟练使用C语言编程的能力。虽然还有很多复杂的问题是我们的能力所不及的，但我相信通过一次次实际的训练操作会使我们的解决问题的能力一步步有所提高。这次程序设计让我们学到了好多知识，但也暴露了我们在程序设计中的不足。总之，所以我相信通过此次课程设计会提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础16技术发展