人工智能之迷宫参考模板

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所示1 / 17为求得最佳路径，可使用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)

3、 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(m

4、k) 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

5、,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、标为（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，则说明不存在路径

7、。为了将搜索结果图形输出，则又设置了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表中

8、搜索结点a.若找到则返回结点a的地址，否则返回0void sort()函数功能:对open表中节点按照f值升序排列void Expand(Data *a)函数功能: 扩展当前结点avoid printmaze()函数功能:输出迷宫void printpath(Data *a)函数功能:输出搜索结果int A()函数功能: A*算法void main()函数功能:主函数（3）详细程序设计#include<iostream>#include<stack>using namespace std;int Maze77=3,1,3,1,3,0,3, 0,4,1,4,1,4,1,

9、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<Data *> open; /open表stack<Data *> closed; /close表bool bound(Data *a) /边界函数 return (a->x<=6)&&(a-

10、>x>=0)&&(a->y<=6)&&(a->y>=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<Data *> c;while(!open.empty() b=open.top();if(b->x=a->x&&b->y=a->y) while(!c.empty() d=c.top();

11、 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<Data *> c;while(!closed.empty() b=closed.top();if(b->x=a->x&&b->y=a->y) while(!c.empty()d=c.top();c.pop();clos

12、ed.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<Data *> c;int b=open.size();for(int i=0;i<b;i+) p=open.top();open.pop();for(int j=i+1;j<b;j+)q=open.top();open.pop();if(q->f<p->f)r=p

13、;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;i<4;i+)bi=(struct Data*)malloc(sizeof(Data);b0->x=a->x+2;b0->y=a->y;b1->x=a->x;b1->y=a->y-2;b2->x=a->x-2;b2->

14、y=a->y;b3->x=a->x;b3->y=a->y+2;for(i=0;i<4;i+)if(bound(bi) p=(bi->x+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+1<d->

15、g) d->g=a->g+1;d->f=bi->g+h(bi);d->parent=a;else if(Nclosed(bi) if(a->g+1<bi->g) 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;i<7;i+) if(i=6)cout<<"入口&quo

16、t;elsecout<<" "if(i%2=0) for(int j=0;j<7;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<<"出口"cout<<en

17、dl;else for(int j=0;j<7;j+) if(Mazeij=1)cout<<"" else if(Mazeij=7) cout<<""else if(Mazeij=8) cout<<""elsecout<<" " cout<<endl; cout<<" (1,1)"<<endl<<endl;void printpath(Data *a)/输出搜索结果 int b,c;stack&

18、lt;Data *> 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->y>a->y) Mazebc=5;else Mazebc=6;else if(a->parent->x>a->x) Mazebc=7;elseMazebc=8;a=a->parent;q.push(a);while(!

19、q.empty()cout<<"("<<q.top()->y/2+1<<","<<5-(q.top()->x/2+1)<<") " q.pop();cout<<endl<<endl;printmaze(); int A() /A*算法 Data s=6,0,0,0,NULL;Data *n=&s; open.push(n);while(1) if(open.empty() cout<<"不存在路径!"<<end